Social choice: Arrow and Gibbard-Satterthwaite

🗳️

Three friends vote on where to eat, and each pairwise vote has a majority winner, yet there is no overall winner: the group prefers Thai to Italian, Italian to sushi, and sushi to Thai. Majority rule, the fairest thing imaginable, can eat itself.

Turning individual rankings into a group ranking sounds like bookkeeping. It is not. Majority rule can cycle, and two theorems show the trouble is fundamental: no rule aggregates unrestricted rankings without giving up one of Arrow’s conditions, and no deterministic rule that selects among three or more options is both non-dictatorial and fully strategy-proof.

From earlier lessons

Two quick ones before we start.

A preference ranking is transitive if preferring A to B and B to C implies...

A rule is strategy-proof if no voter can gain by...

Predict, then play

Three voters, three options. Each pairwise contest is decided by majority. Tap a voter to change their ranking and look for an overall winner.

Why did that happen?

Take a guess, then reveal the reason

Each individual has a perfectly sensible, transitive ranking. But majorities are made of different people in each pairwise contest, so the group’s “preference” need not be consistent. There is no contradiction in any voter; the intransitivity is a property of aggregation itself. Once you see that majority rule can cycle, you start to suspect that no aggregation rule can be perfectly well-behaved, and Arrow proved exactly that.

The math

Take rankings $A\!>\!B\!>\!C$ , $B\!>\!C\!>\!A$ , $C\!>\!A\!>\!B$ . Pairwise: $A$ beats $B$ (voters 1 and 3), $B$ beats $C$ (voters 1 and 2), $C$ beats $A$ (voters 2 and 3). The social preference cycles, so there is no Condorcet winner.

Definition, Arrow and Gibbard-Satterthwaite

Arrow’s theorem: with three or more alternatives, no rule turning individual rankings into a complete, transitive social ranking can satisfy unrestricted domain, unanimity (Pareto), independence of irrelevant alternatives, and non-dictatorship at once. Gibbard-Satterthwaite: with unrestricted strict rankings and three or more alternatives, any deterministic, onto rule that is strategy-proof (no voter ever gains by misreporting) must be a dictatorship. Together they show why the stated conditions cannot all hold at once.

Strategic voting follows. Suppose plurality with $45\%$ for $A$ , $30\%$ for $B$ , $25\%$ for $C$ , where the $C$ -voters prefer $B$ to $A$ . Voting sincerely elects $A$ . But if the $C$ -voters switch to $B$ , then $B$ wins with $55\%$ , an outcome they prefer. The rule is manipulable, exactly as Gibbard-Satterthwaite predicts.

Work it out

A cycle, then a manipulation

The cycle. Count each pairwise contest in the profile above. $A$ vs $B$ : voters 1 and 3 rank $A$ higher, so $A$ wins $2$ to $1$ . $B$ vs $C$ : voters 1 and 2 prefer $B$ , so $B$ wins. $C$ vs $A$ : voters 2 and 3 prefer $C$ , so $C$ wins. The social preference is $A > B > C > A$ : a cycle, no winner.

The manipulation. Under plurality with shares $45/30/25$ for $A/B/C$ , sincere voting elects $A$ . The $25\%$ who rank $C$ first but prefer $B$ to $A$ can desert $C$ and vote $B$ . Now $B$ has $30 + 25 = 55\%$ and wins, which those voters prefer to $A$ . A non-dictatorial rule was manipulated, illustrating Gibbard-Satterthwaite.

Key idea

Aggregating preferences is not neutral bookkeeping. Majority rule can cycle, no rule escapes Arrow’s conditions without a dictator, and no deterministic, onto rule over three or more options is fully strategy-proof on unrestricted rankings.

Check yourself

Check yourselfapply

Why does the profile A>B>C, B>C>A, C>A>B have no Condorcet winner?

Check yourselfanalyse

What does Arrow's theorem actually claim?

Check yourselfbrings back: dominance

Under plurality, C-voters who prefer B to A abandon C and vote B to change the winner. In strategic terms, what are they doing?

Sources

Arrow, K. J. (1951). Social Choice and Individual Values. Wiley.
Gibbard, A. (1973). Manipulation of voting schemes: a general result. Econometrica, 41(4), 587-601.
Satterthwaite, M. A. (1975). Strategy-proofness and Arrow's conditions. Journal of Economic Theory, 10(2), 187-217.