### Summary on Cabal Equilibria and Voting

Last year I introduced cabal equilibria. This post is a summary of my research on cabal equilibria and election methods. Since this is just a short summary, I’m going to skip over any caveats about exact ties in elections.

In any game, a cabal equilibrium is a strategy profile in which no set C of players can simultaneously change strategies in such a way that at least one member of C benefits and no member of C is worse off. Every cabal equilibrium is a Nash equilibrium, but the reverse is not true. For example, in the prisoner’s dilemma, the Nash equilibrium is for both players to defect. This is not a cabal equilibrium, because if both players changed their strategy to cooperate, then both players would benefit. Thus, the prisoner’s dilemma has no cabal equilibria.

The cabal equilibria in elections are particularly interesting, and are related to the notion of a Condorcet winner. In a ranked voting method, a Condorcet winner is a candidate A such that, for any other candidate B, more than half of the voters ranked A higher than B. Of course, the existence and identity of the Condorcet winner (as defined above) depends on how the voters actually vote, not on their true preferences, so for our discussion it’s important to define a *pure Condorcet winner* as any candidate A such that, for any other candidate B, more than half of the voters *actually prefer* A to B.

Before I can give my first result, I have to define an election method criterion. An election method is *weakly majority-controllable* if any majority of voters can cooperate to dictate the outcome of the election, assuming that they already know how the remaining voters are voting. Plurality voting, range voting, all Condorcet voting methods, instant-runoff voting, and the Borda count are all weakly majority-controllable.

My first result is that in any weakly majority-controllable election method, a cabal equilibrium will always elect a pure Condorcet winner.

This is quite easy to see: if an election selects some candidate A who is not a pure Condorcet winner, then there must be some other candidate B whom a majority prefers to A. Since the election is weakly majority-controllable, that majority could change their votes to force B to be elected. That majority has just benefited by changing strategies, so the original election must not have been a cabal equilibrium. Thus any election which does not elect a pure Condorcet winner is not a cabal equilibrium; by contraposition, any cabal equilibrium elects a pure Condorcet winner.

Now let’s define a *strongly majority-controllable* election method as one in which a majority can control the outcome of the election in which they have to choose their strategies *first*, even if some members of the majority betray the majority afterwards (as long as it remains a majority). The Borda count is not strongly majority-controllable, but all of the other election methods I mentioned above are.

My second result is that in any strongly majority-controllable election method, the existence of a pure Condorcet winner guarantees the existence of a cabal equilibrium, so this is a partial converse of the first result.

To see this, suppose A is a pure Condorcet winner. Then there is some way that the electorate could vote that guarantees that A will be elected, even if some minority were to change strategies.

Now suppose that there exists a set C of voters that can change their strategies in a way that is beneficial for them. In order for there to be any benefit, the outcome of the election must be changed. No minority of voters has the power to change the outcome, so C must be a majority, and since they consider the change beneficial, none of them may prefer A to the new election outcome. But then A is not a pure Condorcet winner – contradiction.

The Borda count is not strongly majority-controllable, so the existence of a pure Condorcet winner does not guarantee that there is a cabal equilibrium. Here’s an example:

The preferences of the voters are:

5: A > B > C

4: C > B > A

A is the pure Condorcet winner, but the majority cannot simultaneously guard against B and C. For example, if 3 of the majority vote ABC and 2 vote ACB, then the minority can all vote BCA to elect B. Thus there is no cabal equilibrium.

In Hay voting, there are no cabal equilibria except in some degenerate cases. Since every cabal equilibrium is a Nash equilibrium, the only thing that *might* be a cabal equilibrium is the Nash equilibrium in which each voter votes his or her true preferences. If there exist two players whose utility functions are not scalar multiples of each other, then they can cooperate by each transferring some voting mass between a pair of candidates between which they are relatively indifferent.

Similarly in random ballot, the Nash equilibrium is for each voter to vote for his or her favorite candidate. If there’s a pair of voters who most prefer A and B respectively, but who would choose some compromise C over a coin toss between A and B, then they can cooperate by switching their votes to C.

In both of the above examples, there’s a way for two players can cooperate to get a result that is better than the Nash equilibrium, but now each player has an incentive to betray the other and vote their original choice. This mirrors the Prisoner’s Dilemma, which also has no cabal equilibrium.

I’d like to find an election method where cabal equilibria are likely to exist even with a very large number of candidates, but such a method could not be weakly majority-controllable because the probability of a pure Condorcet winner vanishes as the number of candidates increases (assuming random preferences). This is what I’m thinking about now.