A Lean Formalization of Roberts Theorem on Unrestricted Valuations
Version 1 / Sep 30, 2026 / CC BY 4.0
Abstract
We describe a Lean 4 formalization of the finite unrestricted-domain version of Roberts theorem. For finite nonempty agent and alternative types, with at least three alternatives, an onto deterministic direct-revelation mechanism that is dominant-strategy incentive compatible has an affine-maximizer choice rule. Valuations range over all real-valued profiles; the conclusion uses fixed nonnegative weights, at least one nonzero, and alternative offsets, and asserts membership in the maximizing set. The development follows the modular proof route: taxation and weak monotonicity, perturbation-based tie-breaking to strong monotonicity, no-veto range analysis, affine prices for two agents, and induction through fixed-report slices. We explain the proved tie-set transport lemma, the construction of fresh payments for the tie-broken rule, and the transfer back to arbitrary ties. A version-pinned account distinguishes the proved library from statement-only comparator placeholders and separates source inspection from executable checks. This is an exposition of a classical result and its formal artifact, with no claim of mathematical novelty or formalization priority.
Provenance statement
Tools used
- Lean
- LeanVersion 4.35.0-rc2
- OpenAI
- CodexVersion GPT-6.1
- OpenAI
- CodexVersion GPT-6-Luna (repository-reported formalization assistance)
References
- Dobzinski, Shahar; Nisan, Noam. A Modular Approach to Roberts' Theorem. Algorithmic Game Theory, SAGT 2009, vol. 5814, pp. 14–23. 2009. \urlhttps://doi.org/10.1007/978-3-642-04645-2_3DOI
- Lavi, Ron; Mu'alem, Ahuva; Nisan, Noam. Towards a Characterization of Truthful Combinatorial Auctions. Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 574–583. 2003. \urlhttps://doi.org/10.1109/SFCS.2003.1238230DOI
- Palomar Registry. Mechanical verification of submission ujjeis5lup8v. 2026. Completed successfully September 27, 2026; submitted source revision 61bd2b9075588716550bcd3ac9bc68f7392e823f; not mathematical peer review
- Ramos, Arthur Freitas. Local verification record in the Roberts packaging commit. 2026. September 27, 2026; project-reported local checks, not external review
- Ramos, Arthur Freitas. roberts-theorem-lean: a Lean formalization of Roberts theorem. 2026. Pinned source inspected September 30, 2026; Lean and Mathlib v4.35.0-rc2
- Roberts, Kevin W. S. The characterization of implementable choice rules. Aggregation and Revelation of Preferences, pp. 321–349. 1979