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.

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.

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

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.

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.