A majority coalition can lose a symmetric zero-sum game

post by Stuart_Armstrong · 2017-01-26T12:13:49.380Z · LW · GW · Legacy · 13 comments

Contents

  Larger games
None
13 comments

Just a neat little result I found when thinking about Jessica's recent post.

For n players, let a_i be the action of player i and s_i(a₁,a₂,...a_n) the reward of player i as a function of the actions of all players. Then the game is symmetric if for any permutation p:{1,...n}→{1,...n}

s_i(a₁,a₂,...a_n) = s_p(i)(a_p(1),a_p(2),...a_p(n))

The game is zero-sum if the sum of the s_i is always zero. Assume players can confer before choosing their actions.

Then it is possible for a majority coalition to strictly lose a zero-sum game, even in a deterministic game where they get to see their opponents' moves before choosing their own.

This seems counter-intuitive. After all, if one coalition has M players, the other has m players, with m<M, and there are no other players, how can the M players lose? Couldn't just m of the M players behave exactly as the smaller coalition, thus getting the same amount in expectation? The problem is the potential loses endured by the remaining M-m players.

For an example, consider the following 5 player colour game (it's a much simplified version of the game I came up with previously, proposed by cousin_it). Each player chooses one of two colour, blue or red. Then the players that selected the least commonly chosen colour(s) are the winners; the others are the losers. The losers pay 1 each, and this is split equally between the winners.

Then consider a coalition of three players, the triumvirate. The remaining two players - the duumvirate - choose different colours, red and blue. What can the triumvirate then do? If they all chose the same colour - say blue - then they all lose -1, and the duumvriate loses -1 (from its member that chose blue) and gains 4/1 (for the member that chose red). If they split - say 2 blue, 1 red - then the ones that chose blue lose -1, while the duumveriate loses -1 (from its member that chose blue) and gains 3/2 > 1 (from the member that chose red).

So the duumvriate can always win against the triumvirate.

Of course, it's possible for two members of the triumvirate to create a second duumvirate that will profit from the hapless third member. Feel free to add whatever political metaphor you think this fits.

 

Larger games

Variations of this game can make Jessica's theorem 2 sharp. Let the minority coalition be of size m (the majority coalition is of size M = n-m = qm+r for some unique q and 0≤r<m). The actions are choosing from m colours; apart from that the game is the same as before. And, as before, the members of the minority coalition each choose a different colour.

Then an m-set is a collection of players that each chose a different colour. Split the players into as many disjoint m-sets as possible, with the minority coalition being one of them - say this gives q'+1 m-sets. There are r' remaining players from the majority coalition.

Note that we can consider that any loss from a member of an m-set is spread among the remaining members. That's because all winners are members of m-sets, and players that choose the same colour are interchangeable. So we can assign the loss from the member of an m-sets as being an equivalent gain to the other members. Thus the m-sets only profit from the r' remaining players. And this profit is spread equally among the winners - hence equally among the m-sets.

Thus the majority coalition has a loss of r'/(q'+1), and minimises its loss by minimising r' and maximising q' - hence by setting q'=q and r'=r. Under these circumstances, the minority coalition wins r/(q+1) in total.

Adding 1 to the reward of each player, then dividing all rewards by n, gives the unit-sum game in Jessica's theorem.

13 comments

Comments sorted by top scores.