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