Freaky unfairness

benelliott12 Jan 2011 10:08 UTC
28 points
10 comments2 min readLW linkArchive

In Freaky Fairness the author discusses the problem of multi-player game theory problems where all players have access to each-other’s source code. He gives an algorithm called Freaky Fairness, and makes the claim that ‘all players run Freaky Fairness’ is both a Strong Nash Equilibrium and a Pareto Optimum. Unfortunately, as far as I can tell, this claim is false.

For reference, the algorithm of Freaky Fairness works as follows:

  1. Calculate the security values in mixed strategies for all subsets of players.

  2. Divide all other players into two groups: those whose source code is an exact copy of Freaky Fairness (friends), and everyone else (enemies).

  3. If there are no enemies: build a Shapley value from the computed security values of coalitions; play my part in the outcome that yields the highest total sum in the game; give up some of the result to others so that the resulting allocation agrees with the Shapley value.

  4. If there are enemies: play my part in the outcome that brings the total payoff of the coalition of all enemies down to their security value.

Now consider the following simple game for three players:

  1. Each player chooses one player to nominate.

  2. They can nominate themselves but they don’t have to.

  3. If a player gets nominated by at least two players (possibly including themselves) then they win the game and receive $300

  4. If every player gets nominated exactly once then nobody gets anything.

Conventional competitive game theory notes that each player has a dominant strategy of nominating themselves, and so nobody gets anything. Since the game potentially offers an $300 prize there is room for improvement here. Lets see how Freaky Fairness does:

  • The empty coalition and all coalitions with only one player have a security value of 0.

  • All coalitions with at least two players have a security value of $300 (this is independent of whether you use the alpha method, the beta method or mixed strategies to calculate security values).

  • The Shapley values work out at $100 to each player (this is trivial by symmetry but can be worked out the long way if you feel like it).

  • If all players run Freaky Fairness then they will choose one of their number, nominate them and then that player will then share out the money evenly.

If any one player deviates then the other two will split the money between themselves to ensure that this one player gets nothing, so far so good. Unfortunately if two players deviate they is nothing the remaining Freaky Fairness player can do to ensure they don’t each walk away with $150, which is more than they get by sticking to Freaky Fairness.

Why does the proof given in the original article fail here? The proof assumes that the Shapley method gives every coalition at least their security value, which unfortunately it doesn’t manage in this case. This is not a problem that can be fixed by a better method of sharing, as it should be fairly obvious that there is no way to share a quantity of money between three people such that any two of them get all of it.

Freaky Fairness is still a very impressive algorithm. If we define a class of ‘nice games’ as games where there exists a way of sharing out the winnings such that every coalition receives at least its security value, then Freaky Fairness works on all these games so long as Shapley does (where Shapley fails you can easily modify FF to find a real solution). We now just need to consider the class of ‘nasty games’, such as the one above. (For those more familiar with co-operative game theory, nice games are those which have a non-empty core, nasty games are those which do not).

Note: I was quite surprised that none of the smart people in the comments section of the original article noticed this, which leads me to think it’s quite possibly wrong. Any criticism is welcome.

benelliott12 Jan 2011 10:08 UTC
28 points
10 comments2 min readLW linkArchive