Arrow's impossibility theorem
ProvedAGT.arrow_theoremAggregating rankings over three or more alternatives under unanimity and independence of irrelevant alternatives forces a dictator — Arrow's impossibility theorem (Theorem 9.3 of Algorithmic Game Theory). Let have more than two alternatives and let there be finitely many, and at least one, voters. Every social welfare function — every aggregator carrying preference profiles to social preferences that are again strict total orders — satisfying
- unanimity: on each identical profile the social preference is , and
- independence of irrelevant alternatives: the social comparison of with depends only on the voters' comparisons of with ,
has a dictator: a voter such that on every profile the social preference coincides with 's.
A note on the hypotheses. matches the book's setting of voters; it is not needed for truth — with zero voters the identical-profile unanimity is already unsatisfiable over three or more alternatives (the empty profile would have to coincide with every strict total order at once), so that case is vacuous either way. Unanimity is the book's identical-profile form (Definition 9.2); combined with IIA it yields the pairwise form ("if all voters rank above , so does society") that the proof uses. enters as ; with two alternatives majority rule is a counterexample, so the bound is sharp.
import Definitions.Def_agt_social
namespace AGT
/-- **Theorem 9.3 of *Algorithmic Game Theory* (Arrow)**: every social
welfare function over more than two alternatives that satisfies unanimity
and independence of irrelevant alternatives is a dictatorship.
`Nonempty ι` pins the statement to the book's setting of `n ≥ 1` voters.
(It is not needed for truth: with zero voters and `|A| ≥ 3` the
identical-profile unanimity below is already unsatisfiable — the empty
profile would have to agree simultaneously with every strict total
order — so that case is vacuous either way.) Unanimity is the book's
identical-profile form (Definition 9.2); together with IIA it yields the
pairwise form used in the proof. -/
theorem arrow_theorem {A ι : Type*} [Fintype A] [Fintype ι] [Nonempty ι]
(hA : 2 < Fintype.card A) (F : (ι → A → A → Prop) → A → A → Prop)
(hF : IsSWF F) (huna : SWFUnanimity F) (hiia : SWFIIA F) :
∃ i : ι, SWFDictator F i := by
sorry
end AGTRead-back
What the Lean code literally says, in plain math · claude-fable-5
Read-back: arrow_theorem
Setup. Fix two arbitrary types: a type of alternatives and a type of voters. Three typeclass hypotheses are assumed:
- is finite (
Fintype A); - is finite (
Fintype ι); - is nonempty (
Nonempty ι).
There is one explicit cardinality hypothesis: , i.e. there are strictly more than two alternatives (so at least ; combined with finiteness, ). No decidability assumption is used by the theorem (a DecidableEq ι hypothesis appears in the surrounding definition file, but only after the definitions this theorem uses, and the theorem statement itself does not carry it).
Throughout, a profile is any family where each is a binary relation on (an arbitrary function ; no properties are built into the type). The predicate " is a preference profile" means: for every voter , the relation is a strict total order on in Mathlib's sense (IsStrictTotalOrder), i.e. is
- trichotomous: for all , or or ;
- irreflexive: for no does hold;
- transitive.
The object . Let be any function taking a family of binary relations on (one per voter — not necessarily a preference profile; is total on all such families) and returning a single binary relation on . Three hypotheses are assumed about :
-
is a social welfare function (
IsSWF F): for every preference profile (every a strict total order), the output relation is itself a strict total order on . Nothing is assumed about the value of on families that are not preference profiles. -
Unanimity, in the constant-profile form (
SWFUnanimity F): for every single relation on that is a strict total order, and for all ,
That is: on a profile in which every voter holds the identical order , the social order coincides exactly (as a biconditional on every ordered pair, including pairs with ) with . This is the only form of unanimity assumed — it constrains only on constant profiles. It is not the Pareto condition: no assumption is made that unanimous agreement on a single pair within a non-constant profile forces .
- Independence of irrelevant alternatives (
SWFIIA F): for all preference profiles and (both consisting of strict total orders) and all : if every voter satisfies (agreement is required only on the single ordered pair , not explicitly on ), then
Conclusion. There exists a voter (plain existence — no uniqueness is claimed) who is a dictator in the following strong sense (SWFDictator F i): for every preference profile (every coordinate a strict total order) and all ,
That is, on every preference profile the social order returned by is identical, pair by pair, to voter 's own order — not merely that 's strict preferences are respected in one direction, but a full biconditional on every ordered pair.
Edge cases made explicit.
- The hypotheses are non-vacuous only when strict total orders on exist and is inhabited; both are guaranteed here ( finite hence linearly orderable, assumed nonempty). If were empty the conclusion would be false, so
Nonempty ιis load-bearing. - With the two-alternative case (where majority rule famously satisfies the analogous conditions) is excluded, as are .
- All biconditionals quantify over all ordered pairs, including diagonal pairs (where irreflexivity forces both sides false) and both orientations , .
- 's behavior on families that fail to be preference profiles is completely unconstrained by every hypothesis and by the conclusion.
Confirmed by the mission captain (proposal self-audit).