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: http://www.ccs.neu.edu/home/lieber/talks/summer-2014/

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

Our journey 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.

Default Choices

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 functions. Side-choosing games are about finding winning strategies for the underlying combinatorial game.

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.