Arrow and Gibbard Satterthwaite Theorems in Lean
Version 1 / Oct 01, 2026 / CC BY 4.0
Abstract
We give a source-aligned account of two Lean 4 formalizations of classical finite social-choice impossibility theorems. For a finite nonempty electorate and a finite alternative set containing three distinct alternatives, Arrow’s theorem derives dictatorship from unanimity and independence of irrelevant alternatives. Its proof expands a weakly decisive coalition from one ordered pair to all pairs, then contracts decisive coalitions to a singleton. The Gibbard–Satterthwaite development proves that every onto strategy-proof choice function on the unrestricted strict-ranking domain is dictatorial by constructing a social welfare function and applying that Arrow implementation. We explain the essential construction in full: top-two profiles define pairwise comparisons; strategy-proof monotonicity and three-top profiles establish a strict total order; predecessor counts provide injective natural-number ranks. Exact hypotheses, vendored dependencies, pinned source identities, prior formalizations, and the distinction between historical registry verification and the present source audit are recorded. The contribution is an exposition and audit of reusable formalization artifacts, not a new social-choice theorem or a claim of first formalization.
Provenance statement
Formalizations
Tools used
- OpenAI
- ChatGPTVersion GPT 6.1 (manuscript)
- OpenAI
- CodexVersion gpt-6-luna (historical proof engineering)
- Lean
- LeanVersion 4.35.0-rc2 (registered artifacts)
References
- Arrow, Kenneth J. A Difficulty in the Concept of Social Welfare. Journal of Political Economy, vol. 58, no. 4, pp. 328–346. 1950. \urlhttps://doi.org/10.1086/256963DOI
- Gibbard, Allan. Manipulation of Voting Schemes: A General Result. Econometrica, vol. 41, no. 4, pp. 587–601. 1973. \urlhttps://doi.org/10.2307/1914083DOI
- Nipkow, Tobias. Social Choice Theory in HOL: Arrow and Gibbard–Satterthwaite. Journal of Automated Reasoning, vol. 43, no. 3, pp. 289–304. 2009. \urlhttps://doi.org/10.1007/s10817-009-9147-4DOI
- Palomar Registry. Arrow's impossibility theorem (general finite version). 2026. PALOMAR-2026-09-25-000024, version 1. Registered September 25, 2026 \urlhttps://palomar-registry.org/entry?id=PALOMAR-2026-09-25-000024&version=1link
- Palomar Registry. Gibbard–Satterthwaite theorem (strategy-proof social choice). 2026. PALOMAR-2026-09-25-000028, version 1. Registered September 25, 2026 \urlhttps://palomar-registry.org/entry?id=PALOMAR-2026-09-25-000028&version=1link
- Peters, Dominik. SocialChoiceLean: Gibbard–Satterthwaite in Lean. 2026. Public repository snapshot, July 21, 2026. Consulted as source; not rebuilt for this manuscript \urlhttps://github.com/DominikPeters/SocialChoiceLean/tree/94a4c650b6a3ef14df801a613c3b46169dbd754dlink
- Ramos, Arthur Freitas. Arrow's Impossibility Theorem in Lean 4. 2026. Pinned repository snapshot. BSD-3-Clause \urlhttps://github.com/Arthur742Ramos/arrow-impossibility-lean/tree/4f405d27d0b244574bbee5d3d79bae0c66bda16elink
- Ramos, Arthur Freitas. Gibbard–Satterthwaite Theorem in Lean 4. 2026. Pinned repository snapshot. BSD-3-Clause \urlhttps://github.com/Arthur742Ramos/gibbard-satterthwaite-lean/tree/8398e65a99cd3d5e973c64963c4bab8c0491947clink
- Roos, Joris. Arrow's theorem via Fourier analysis. 2026. Palomar record PALOMAR-2026-09-01-000011, version 1 \urlhttps://palomar-registry.org/entry?id=PALOMAR-2026-09-01-000011&version=1link
- Satterthwaite, Mark A. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, vol. 10, no. 2, pp. 187–217. 1975. \urlhttps://doi.org/10.1016/0022-0531(75)90050-2DOI