Side-Choosing Games Revisited
After 4 talks on side-choosing games in the summer 2014
(University of Erlangen-Nuernberg,
Technical University of Darmstadt,
ETH Zurich and Harvard)
and working on a paper on side-choosing games (with Ruiyang Xu),
we have refined our definition of the concept of
a side-choosing game.
The talk abstracts and slides are here:
Side-choosing games model debating where each binary debate
must have a winner and a loser. The debating mechanism
can vary. What is important that the social choice theory
of side-choosing games can be based on the game results
which are tables based on tables with columns:
Winner, Loser, Proponent, Opponent, rProponent, rOpponent.
We call those tables SCG-tables.
rProponent and rOpponent are the runtime roles into which
the players might be forced (devil's advocates).
The SCG-tables can be simplified to only having the columns:
Winner, Loser, Forced.
The SCG-tables must satisfy some simple rules, like Winner != Loser, etc.
Are SCG-Tables Enough?
Why do we need more than just those outcome tables?
We want to have an organizational principle to organize
a group of motivated people and their interactions will
produce the SCG-tables. We are looking for a generic
game that captures the idea of side-choosing and that
can be readily specialized for many practical situations
to produce SCG-tables.
Using Combinatorial Games
brought us to draw-free combinatorial games as a good starting point.
Combinatorial game theory has a long history and there are many
interesting solved combinatorial games. Starting with combinatorial games
needs less machinery than the perfect-information extensive form games
and people can easily relate to games like chess and many know about chess
puzzles which are draw-free.
The side-choosing games are about studying a game position,
choosing a side (Proponent or Opponent)
on that position (can you guarantee a win? can you guarantee
to prevent a win for the adversary?)
Then the game is played to determine whose side-choice is supported.
This involves details on how to make the side choice (e.g., is it
simultaneous?) and how to deal devil's advocate assignments.
Side-choosing Games: Informal Definition
Therefore, a side-choosing game is a triple (G,SC,AA), consisting of a
two-person, draw-free, combinatorial game G; SC is a side-choice configuration and AA is an agreement algorithm assigning the devil's advocate choice.
We call SC a configuration because the choices are made by the players.
AA however, is an algorithm which will dictate the players when to play devil's advocate.
The important component is the combinatorial game G; SC and AA offer variation possibilities to define the side-choosing games. We will use simple instances of SC and AA for our side-choosing games.
For SC we use simultaneous design-time decisions.
For AA we use an unbiased coin to determine the player be forced first.
In the second game, the other player is forced. So there are two games
played under the default choice for AA.
Note that with those default choices, the side-choosing game is not a combinatorial game.
A side-choosing game is an abstraction of the following interesting scenario:
There is a game position with an unknown solution where both players
need to find functions (winning strategies)
satisfying certain requirements. The two players
prepare interesting inputs for those functions which will challenge
the other player to find good functions but also reveal details about one's own
Side-choosing games are about finding winning strategies for the underlying
There are two kinds side-choosing games as noted by
Jason Hartline during my talk at Harvard:
Those with succinct winning strategies and those with long winning strategies.
Side-choosing games coming from logical formulas and their semantic games
sometimes have a succinct winning strategies. An example is the NIM game
or Product Stress Testing.