Side-Choosing Games for Human Computation and Education
Joint work with Ahmed Abdelmeged.
Background
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)
http://www.ccs.neu.edu/home/lieber/evergreen/specker/scg-home.html
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.
Definition
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.
Examples
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.
Intuition
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.