Side-Choosing Games for Human Computation and Education

Joint work with Ahmed Abdelmeged.


We studied side-choosing games as an abstraction of semantic games for different kinds of logics such as predicate logic and independence friendly-logic. Our application area is human computation for formal science problems and teaching formal science topics and modeling scientific communities. One key contribution is to use the players to evaluate each other, significantly lifting the burden on the administrator of the competition, or the teacher. In a class room setting we use a debating terminology instead of a gaming terminology. The students debate claims in some formal science topic and try to push each other into contradictions in the sense of Socrates. The Scientific Community Game (SCG) which we have studied over the last few years, is based on side-choosing games. SCG was the breeding ground for the idea of side-choosing games.

Our goal was a systematic study of ranking functions for side-choosing games that map beating functions to rankings with the purpose to find the strong players. The strong players tend to choose the correct side and tend to defend it when they are challenged.

Fundamental Contributions

The fundamental innovations we introduce are (1) we lift the nice properties of binary side-choosing games to tournaments of side-choosing games and (2) we systematically exploit the notion of side-choosing to achieve collusion resilience. It is critical that the players choose a side for a position, either as a verifier or falsifier. Regarding (1), a binary side-choosing game requires that the players be distinguished (one plays the role of verifier, the other the role of falsifier). We generalize from two players to n players and remove the requirement that the players be distinguished. Regarding (2), we answer the question: why is side-choosing important. Without side-choosing, if the players are dictated which side to defend, there is no concept of forcing which is very important for assigning blame and finding the strong players. For example, with the concept of forcing, we can avoid of having two forced players play against each other. Games where both are forced are useless regarding finding the strong players.

In side-choosing games, a player is never underestimated. A player never loses a side-choosing game without making a mistake. A player has a chance to never lose. A player has also a chance to ensure that the opponent is not overestimated by providing challenging moves to the opponent. These statements hold for games with two distinguished players, one a verifier, the other a falsifier. We generalize to n players as described above.


We study a new kind of two-person game, called a side-choosing game. We start from an extensive-form two-person game and allow any position in the extensive form game to become the start position of the game (instead of the standard start position). The first move of the players is to decide whether this position is winning for them: they take the verifier or falsifier side. The game outcome will tell who is right. If both players choose the same side, we play two games where the players alternately take the devil's advocate position (they have to play in forced position).

It is correct to demerit a non-forced loser of a side-choosing game because the loser must have either picked the wrong side or did not play according to the winning strategy that he claimed to have.

More formally, we view a two person game in extensive form to have a non-empty set V of positions with a partition V1 union V2 union T = V, where Vi is the set of positions controlled by player i (i = 1 or 2) and T is the set of terminal positions. For each non-terminal position there is a set of actions available at v. When executing the action we reach another position (transition mapping).

We visualize the extensive form game as an oriented tree where the root is the initial game position. The nodes are positions and the edges correspond to the transitions. Paths from the root represent a specific game execution. We assume that those paths are finite.


As a first example, take chess and use an intricate position as the start position. Some players think they can win as white (verifier) and others, playing as black, think they can prevent white from winning in that position (falsifier).

As a second example: choose a logic with semantic games and consider its sentences. They define algorithms through the functions that are needed to successfully win the semantic games. The side-choosing games (= semantic games) will tell which players have good algorithms for choosing their side (whether the sentence is true or false) and for defending the sides they have chosen.

Collusion-Resilient Ranking Functions

We use side-choosing games in tournaments involving a set of players. They collectively develop a "theory" about the positions that can be won. Axiomatic studies of ranking functions for games are well-known. But not for side-choosing games which are a new concept.

We have developed a theory about collusion-resilient ranking of side-choosing games. We prove that a specific mapping of beating functions to rankings is collusion-resistant. We show that this mapping has a property called LFB which any ranking function which satisfies a given set of desirable properties must have. This theoretical result has useful applications in Human Computation.


Collusion-resilience has the intuition described below. First a few preliminaries: x <= y means that player x is ranked weakly better than player y. We say that a player x controls a game if x either wins or had a guaranteed opportunity to win (was non-forced). In a side-choosing game there is at least one of the two players in control: the winner.

If x <= y and y plays more games that x cannot control, then we still have x <= y. In addition, if !(y <= x) (x is strictly better than y) then x remains strictly better than y when more games, that x cannot control, are added.

In order to improve your rank against a specific player you cannot get help from friends who might lose on purpose to help you.

Related Work: Independence of Irrelevant Alternatives (IIA)

See Ahmed Abdelmeged's dissertation for the complete development.

References: Games in extensive form by Zielonka. Theory of ranking systems, Stanford, Technion, 2008.