#
Side Choosing Games (SCG)

Joint work with Ahmed Abdelmeged
##
Context

We have developed a new kind of games,
called side-choosing games, as a foundation
for human computation systems for complex tasks,
like solving computational problems.
We have developed an axiomatic treatment
of the ranking functions for sets of side-choosing games.
A key axiom is the collusion-resilience axiom
which has a strong influence on the structure of
ranking algorithms mapping debate results to rankings
of the debaters.
The main structure of our system,
is that we have owners who define labs
with problems and prices to win.
Each lab has participants who debate each other
about the problem of the lab.
In order to be good in the debates you must
have a good solution to the problem.
The best debaters have the best solutions to the problem
and will win the prize.

The side-choosing games take place during the debates in a lab.
Each lab is based on an extensive form game,
without ties. We
choose a legal position p as the start position.

##
Side-Choosing Game

The first move in the side-choosing game
is a simultaneous move during
which both debaters choose their
side on position p.
There are two sides to choose: the Verifier or
Falsifier side. The Verifier side says that
I am guaranteed to win when playing the extensive form
game from position p.
The Falsifier side says that I am guranteed to prevent
my opponent from winning when playing the extensive
form game from position p.
If the debaters choose opposite sides,
we play the extensive form game from position p and
determine the winner and loser.
The outcome for two debaters x and y
will be one of the following rows.
W is the winner column and L is the loser column.

W L Forced
x y none
y x none

If both debaters choose the same side,
we play two extensive form games from p,
introducing the notion of a forced debater
or of a devil's advocate.
The first game has x forced and the
outcome will be one of the following rows.
W L Forced
x y x
y x x

The second game has y forced and the
outcome will be one of the following rows.
W L Forced
x y y
y x y

Because money is at stake it is important that
we care for guaranteed collusion resilience.
Collusion is when a debater, who is not in control,
has his ranking changed behind his back.
This can happen when debaters lose (although
they could win) to help their colluding
friends. The concept of forced debaters is crucial
for defining and enforcing collusion resilience.

For more details:
Side-Choosing Games

Karl Lieberherr, March, 2014