Applied and computational mathematics

Social choice theory

Studies how individual preferences combine into collective decisions, including voting systems.

IntuitionThree friends, three favorite restaurants, and no fair way to pick one

Ann prefers sushi to pizza to tacos. Bob prefers pizza to tacos to sushi. Cara prefers tacos to sushi to pizza. Ask which restaurant the group of three prefers, comparing two at a time by majority vote: a majority (Ann and Cara) prefers sushi to pizza; a majority (Ann and Bob) prefers pizza to tacos; but a majority (Bob and Cara) also prefers tacos to sushi. The group's preference cycles — sushi beats pizza beats tacos beats sushi — even though every individual person has a perfectly consistent ranking. Social choice theory studies exactly this gap between individually rational preferences and collectively rational decisions, and asks how far it can be closed.

Three voters, three candidates: every voter (left) is linked to every candidate (right), because each voter must rank all of them. Even with only

3

voters and

3

candidates, there are already

(3!)^3 = 216

possible combinations of individual rankings for a social choice rule to handle consistently.

Formally, each voter $i$ reports a preference order — a ranking of the alternatives from most to least favored. A social welfare function $F$ takes the whole profile of individual rankings and outputs a single social ranking; a social choice function takes the profile and outputs a single winner. Both kinds of rules need to handle every logically possible profile, not just convenient ones, which is exactly what makes the restaurant example above a genuine problem rather than a fluke.

UndergraduateAggregation rules and Arrow's four conditions

Definition: Social welfare function and the majority relation

A social welfare function $F$ maps every profile of individual preference orders $(\succ_1, \dots, \succ_n)$ to a single social preference order $\succ$ . The majority relation is the natural candidate: declare $a \succ b$ socially exactly when a strict majority of voters rank $a$ above $b$ . As the restaurant example showed, the majority relation can fail to be transitive — it can cycle instead of ranking the alternatives from best to worst.

a \succ b \iff \#\{i : a \succ_i b\} > \#\{i : b \succ_i a\}

Arrow asked: is there any rule, majority or otherwise, that always outputs a transitive social ranking while satisfying a short list of minimal fairness conditions? Unrestricted domain: the rule must work for every possible profile of individual rankings. Weak Pareto: if every voter ranks $a$ above $b$ , so must society. Independence of irrelevant alternatives (IIA): the social ranking of $a$ versus $b$ depends only on how individuals rank $a$ versus $b$ , not on where some third alternative $c$ sits. Non-dictatorship: no single voter's preferences always determine the social ranking regardless of everyone else.

Three voting rules, and where each one runs into trouble
Rule	How the winner is chosen	Always picks the Condorcet winner?	Strategy-proof?
Plurality (most first-place votes)	Each voter names one favorite; most votes wins	No	No
Borda count	Rank of $n$ alternatives gives $n-1, n-2, \dots, 0$ points; highest total wins	No	No
Pairwise majority (Condorcet method)	Compare every pair head-to-head by majority vote	Yes, when one exists	No

\text{Borda}(a) = \sum_{i=1}^{n} \big(m - \text{rank}_i(a)\big)

AdvancedTwo impossibility theorems

Theorem: Arrow's Impossibility Theorem

If there are at least $3$ alternatives, the only social welfare function satisfying Unrestricted Domain, Weak Pareto, and Independence of Irrelevant Alternatives is a dictatorship: some single voter $i$ such that the social ranking always equals voter $i$ 's own ranking.

Why is it true?

Pareto and IIA sound modest — surely some clever, non-dictatorial rule could satisfy both while still producing a coherent ranking. Arrow's theorem shows this intuition is wrong: whenever there are $3$ or more alternatives, the two conditions together already force all of the aggregation power onto a single voter, once transitivity is also required.

Proof

Sketch (pivotal voter argument). Fix three alternatives $a, b, c$ . Call $a$ "extreme" in a profile if every voter ranks $a$ either at the very top or the very bottom of their own list, with arbitrary rankings among the others. A short argument using Weak Pareto and IIA — moving other alternatives one at a time past $a$ and checking that doing so cannot be blocked without violating Pareto or letting a ranking depend on where $a$ sits — shows that whenever $a$ is extreme for every voter, society must also rank $a$ at the very top or the very bottom of its own ranking.

Start from the profile where every voter ranks $a$ at the bottom; by Weak Pareto, society ranks $a$ at the bottom too. Now let voters switch, one by one in a fixed order, to ranking $a$ at the top, keeping $a$ extreme at every step. By the extremal fact above, at each step society's ranking of $a$ is still either top or bottom, and Pareto forces it to be top once everyone has switched. So there is a first voter, call them $n^\ast$ , whose switch flips the social ranking of $a$ from bottom to top — the pivotal voter for $a$ .

Next, show $n^\ast$ is decisive between $b$ and $c$ too — not just about $a$ . Build a new profile where $n^\ast$ ranks $b$ above $a$ above $c$ , other voters who came before $n^\ast$ in the switching order rank $a$ at the top (so their relative ranking of $b, c$ can be set freely), and the rest rank $a$ at the bottom. Comparing this profile to the two profiles used to define pivotality, IIA implies society ranks $b$ above $a$ (from the top-of- $a$ side) and $a$ above $c$ (from the bottom-of- $a$ side), hence $b$ above $c$ by transitivity — exactly matching $n^\ast$ 's own ranking of $b$ versus $c$ , regardless of how anyone else ranks them.

Repeating this argument for every pair of alternatives shows $n^\ast$ 's preference always determines society's preference: $n^\ast$ is a dictator. This contradicts Non-Dictatorship, so no rule can satisfy all of Unrestricted Domain, Weak Pareto, and IIA without also being dictatorial.

Theorem: The Gibbard–Satterthwaite Theorem

Let a social choice function pick a single winner from at least $3$ alternatives, for every possible profile of voter rankings, in such a way that every alternative can actually win for some profile (onto). If the function is strategy-proof — no voter can ever get a better outcome (according to their true ranking) by reporting a false ranking — then it must be a dictatorship: some voter's top choice is always the winner.

Why is it true?

Ranked-choice systems are often sold as resistant to strategic voting. Gibbard–Satterthwaite says the opposite is essentially unavoidable: as soon as a rule picks a single winner from $3$ or more alternatives, is defined for every profile, lets every alternative win sometimes, and is not a dictatorship, there is guaranteed to be some situation where some voter benefits from lying about their preferences.

Proof

Sketch (reduction to Arrow's theorem). First, a monotonicity lemma: if alternative $a$ wins at some profile, and the profile changes only by some voters moving $a$ higher in their own ranking (without otherwise reordering the other alternatives), $a$ must still win. Otherwise a voter whose sincere ranking is the "before" profile could misreport as the "after" profile to push $a$ from losing to winning, or vice versa — either way, contradicting strategy-proofness for someone.

Next, use the choice function to build a derived social ranking for each profile: declare $a$ above $b$ in the derived ranking exactly when $a$ would still win after every alternative other than $a$ and $b$ is deleted from every voter's ballot, leaving a straight two-way race. Ontoness and strategy-proofness of the original choice function, together with the monotonicity lemma, can be used to check that this derived ranking satisfies Unrestricted Domain, Weak Pareto, and Independence of Irrelevant Alternatives as a social welfare function.

By Arrow's Impossibility Theorem, since there are at least $3$ alternatives, this derived social ranking must be dictatorial: some voter $i$ 's ranking always equals the derived social ranking.

Finally, check that this same voter $i$ 's top choice is always the winner of the original social choice function: since the derived ranking puts $i$ 's favorite alternative above every other alternative, and the derived ranking tracks who wins pairwise comparisons, $i$ 's favorite must be the overall winner at every profile. So the original strategy-proof, onto social choice function is dictated by voter $i$ .

AdvancedReal-World Applications and Worked Examples

Social choice theory shapes real institutions: national election commissions choose between plurality, ranked-choice, and proportional systems knowing exactly which manipulation risks and paradoxes each one accepts; committees and juries that rank candidates or proposals by Borda count or pairwise comparison inherit the same trade-offs; and recommender systems and AI alignment researchers now treat combining many users' or many AI raters' preferences into a single ranking as a social choice problem in disguise, inheriting Arrow's and Gibbard–Satterthwaite's warnings along with it.

Example: Finding the Borda count winner

Three voters rank three candidates $X, Y, Z$ as follows. Voter 1: $X \succ Y \succ Z$ . Voter 2: $Y \succ Z \succ X$ . Voter 3: $Y \succ X \succ Z$ . With $m = 3$ candidates, a first-place vote earns $2$ points, second place earns $1$ point, and last place earns $0$ points. Who wins by Borda count?

Solution

Tally $X$ 's points: Voter 1 ranks $X$ first ( $2$ points), Voter 2 ranks $X$ last ( $0$ points), Voter 3 ranks $X$ second ( $1$ point). Total: $2 + 0 + 1 = 3$ .

Tally $Y$ 's points: Voter 1 ranks $Y$ second ( $1$ point), Voter 2 ranks $Y$ first ( $2$ points), Voter 3 ranks $Y$ first ( $2$ points). Total: $1 + 2 + 2 = 5$ .

Tally $Z$ 's points: Voter 1 ranks $Z$ last ( $0$ points), Voter 2 ranks $Z$ second ( $1$ point), Voter 3 ranks $Z$ last ( $0$ points). Total: $0 + 1 + 0 = 1$ .

$Y$ has the highest total, $5$ points, so $Y$ wins by Borda count — even though $Y$ is nobody's unanimous top choice, it is consistently ranked near the top by everyone.

Example: A voter who benefits from lying, under plurality rule

Under plurality rule (each voter names one favorite; most votes wins), suppose $45$ voters truly prefer $A \succ B \succ C$ , $40$ voters truly prefer $B \succ C \succ A$ , and $15$ voters truly prefer $C \succ B \succ A$ . If everyone votes for their true favorite, who wins, and can any of the $15$ voters in the last group get a better outcome by voting for someone other than their true favorite $C$ ?

Solution

If everyone votes sincerely: $A$ gets $45$ votes, $B$ gets $40$ votes, $C$ gets $15$ votes. $A$ has the most votes and wins.

But the $15$ voters who truly prefer $C \succ B \succ A$ rank $A$ last. From their point of view, $A$ winning is the worst possible outcome.

Suppose instead those $15$ voters insincerely vote for $B$ , their second choice, instead of $C$ . The tally becomes $A$ : $45$ , $B$ : $40 + 15 = 55$ , $C$ : $0$ . Now $B$ wins.

Since these $15$ voters truly rank $B$ above $A$ ( $B \succ_i A$ for each of them), switching their vote from their sincere favorite $C$ to $B$ changed the outcome from their worst option ( $A$ ) to a better one ( $B$ ) — exactly the kind of profitable misrepresentation that Gibbard–Satterthwaite guarantees must exist for any non-dictatorial rule with $3$ or more alternatives.

Research frontier as of 2026

As of 2026, computational social choice is one of the most active branches of the field: instead of asking whether manipulation is possible in principle, researchers study how computationally hard it is, building on Bartholdi, Tovey, and Trick's 1989 observation that some voting rules make finding a beneficial manipulation NP-hard in the number of candidates, so that strategy-proofness can be traded for strategy-hardness even when Gibbard–Satterthwaite forbids the former. A second active direction studies richer input formats than strict rankings — approval voting, ranked-choice with ties, and quadratic voting — asking which impossibility results survive and which relax once voters can express intensity, not just order. A third direction, driven by applications to AI, treats the alignment of language models with many human raters' preferences (as in reinforcement learning from human feedback) as a social choice problem in disguise, importing Arrow-style axioms and asking which aggregation methods best resist the manipulation and inconsistency that classical social choice theory predicts. Open questions include characterizing exactly which restricted domains of preferences (beyond the classical single-peaked case) escape Arrow's theorem, and finding aggregation rules with provably small worst-case "distortion" relative to unobserved cardinal preferences.

Three voters rank candidates $P, Q$ : Voter 1: $P \succ Q$ . Voter 2: $P \succ Q$ . Voter 3: $Q \succ P$ . By the majority relation, what is the social ranking of $P$ versus $Q$ ?

With $4$ candidates, a first-place vote is worth how many Borda points, using the convention that last place is worth $0$ points?

Arrow's Impossibility Theorem shows that, with $3$ or more alternatives, no social welfare function can satisfy Unrestricted Domain, Weak Pareto, Independence of Irrelevant Alternatives, AND:

According to the Gibbard–Satterthwaite theorem, which voting rule (choosing one winner from $3$ or more candidates, defined for every profile, letting every candidate win sometimes) can guarantee that NO voter ever benefits from insincere voting?

References

Kenneth J. Arrow (1950). A Difficulty in the Concept of Social Welfare · DOI:10.1086/256963
Allan Gibbard (1973). Manipulation of Voting Schemes: A General Result · DOI:10.2307/1914083
Amartya Sen (1970). Collective Choice and Social Welfare