A majority coalition can lose a symmetric zero-sum game
Just a neat little result I found when thinking about Jessica’s recent post.
For n players, let ai be the action of player i and si(a1,a2,...an) 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}
si(a1,a2,...an) = sp(i)(ap(1),ap(2),...ap(n))
The game is zero-sum if the sum of the si 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.
Amusingly enough, a variation of this game occurs in a manga called Liar Game, where it’s called Minority Rule. If you’re curious, they start playing the game here, and you don’t really need to read anything before that. It’s an enjoyable read.
Agreed that Liar Game is a fun read.
I would like to see more crossposted from Intelligent Agent Foundations Forum.
I do that quite often (though this, ironically, isn’t a crosspost).
Nice result!
I think I can simplify your example. Put five people in a room and tell each to pick a mate. Then everyone who isn’t in a mutual pair (there will be at least one such person) pays a dollar to everyone else. The game is clearly symmetric and zero-sum, and any two players can pick each other and defeat the other three in total. It even works if picking happens visibly in any order. It also seems to generalize in the same way, by asking people to divide into groups of m instead of pairs.
That’s basically what I was aiming at, but that game isn’t symmetric according to the definition (eg if player 3 chooses player 2, then a permutation of 1 and 2 should end up with them choosing the old player 1). That’s because there’s no “internal” permutation within the action (so a_p(1) means “the action player p(1) had chosen”, not “the action player p(1) had chosen, updated according to permutation p if the action involve pointing at specific other players” .
My clunky setup essentially tries to do your idea without needing to have actions that point at other players.
I see. Yeah, it seems easy to prove that my game can’t be made symmetric by your definition. Players 1 and 2 can’t pair off, because there’s nothing stopping player 3 from submitting the same action as player 2.
Here’s another simple example that seems to work under your definition. Each of five people must pick either red or blue. That divides them into two unequal groups. Then everyone in the bigger group pays a dollar to everyone in the smaller group, unless there’s only one group, in which case nothing happens. The winning strategy for a team of two is to pick different colors.
You can generalize it as well, by making people choose one of m colors and then having everyone in the smallest group receive a dollar from everyone else. If the number of people isn’t divisible by m, then a team of m can win by choosing different colors.
I think that works, and is much simpler.
I see you’ve edited the post to use my solution. Cool! But I think this remark of yours no longer applies:
Let’s say the duumvirate chooses (red, blue) and the triumvirate chooses (red, blue, blue). Now who’s the hapless third member of the triumvirate that’s being preyed upon? Feel free to add a metaphor :-)
About politics, it’s interesting that the version with picking mates feels more “cutthroat” than the version with choosing colors. I guess the reason is that in the mate-picking game, the gains are spread out and the losses are concentrated (a Nash equilibrium has only r losers who pay everyone else), while in the color-choosing game the losses are spread out more (a Nash equilibrium has r(q+2) losers), which makes it feel more “safe” to a risk-averse person.
You could make it even more “safe” by designating only one of the least popular colors as winning (e.g. the lowest numbered one), so nobody has to feel less fortunate than the majority. Or you could make it more “cutthroat” and designate only one of the most popular colors as losing, which would ensure that losses can be concentrated to a minority. I think both would work for any n≥5, like your original result.
That said, I think your result was already enough to make the fraction of winners arbitrarily large or small as n grows, so this is just a fun distraction :-)
That still applies. The duumvriate chooses (red, blue) and split the loss and gain. Two of the ex-triumvirate also choose (red, blue) and agree to split the loss and gain between themselves only. The last member to the triumvirate is now left out in the cold: whatever they choose, they lose, and they take the whole loss, while both other pairs gain.
It’s interesting that the example with picking mates feels very political, with people callously discarding others to profit from them, but the example with colors doesn’t feel political at all. The last person to pick a color isn’t any worse off than the majority. I guess concentrating gains and spreading losses is more merciful than concentrating losses and spreading gains.
I see. Yeah, it seems easy to prove that my game can’t be made symmetric by your definition. (If player 1 and player 2′s mutual pairing must happen independently from their identities and also from the actions of everyone else, there’s nothing stopping player 3 from submitting the same action as player 2.) I wonder if the definition I was implicitly using is studied anywhere...
Interesting case! It does seem to depend on a the perhaps-unusual condition that the game itself punishes the majority of players for being a majority.
But “majority” is an incorrect description of the losing coalition Really “odd” is the right description, which happens to be a majority in some cases, and not others. In the 7-player game, the 4-player majority coalition “wins” and the 3-player minority “loses”.
In the larger game, coalitions which are an integral multiple of m can guarantee a “win”, others cannot.