HEXAGONbeta

Deferred Acceptance in Lean for Finite Strict Preference Markets

Primarily AI-generated textHuman understanding: some partscs.DS — Data Structures and Algorithmscs.LO — Logic in Computer Science

Contributed by Arthur ↗, David Barros Hulak ↗, Ruy J. G. B. de Queiroz ↗

SubmitterArthur

Version 1 / Sep 30, 2026 / CC BY 4.0

Abstract

We describe a Lean 4 development of men-proposing deferred acceptance for finite one-to-one markets with complete strict preferences and optional partners. The two sides may have different cardinalities; the principal theorems assume a nonempty receiving side. A proposal-set measure proves termination of a specified, classically chosen run. Reachability invariants establish consistency of the resulting partner maps, stability, and the fact that a rejected proposal cannot be a stable-achievable partnership. The public optimality theorem is conditional on a man receiving a partner; an internal lemma separately excludes stable-achievable partners for men unmatched at quiescence. We give mathematical proofs corresponding to the source architecture, identify the precise theorem interface, and separate fresh source inspection from the repository's reported build and axiom audit. This is an exposition of a pinned formalization of classical results, with no claim of new matching theory or priority of formalization.

Provenance statement

GPT-6.1 was used through Codex to prepare this primarily AI-generated exposition. The pinned repository metadata separately records formalization assistance from GPT-6-Luna through Codex. The manuscript describes the public Lean artifact at https://github.com/Arthur742Ramos/gale-shapley-lean/tree/f5f34f68a0e38441cdf5632adde5420d5fe0021e. Source inspection and the repository's reported build and axiom audit are distinguished; no fresh Lean build is claimed. Automated checks do not establish a level of human understanding. The submitting contributor reports that some parts have been checked and understood by a human.

Tools used

Lean
LeanVersion 4.35.0-rc2
OpenAI
CodexVersion GPT-6.1
OpenAI
CodexVersion GPT-6-Luna (repository-reported formalization assistance)

References

  1. Avigad, Jeremy; de Moura, Leonardo; Kong, Soonho; Ullrich, Sebastian. Theorem Proving in Lean 4. \urlhttps://lean-lang.org/theorem_proving_in_lean4/Axioms-and-Computation/. Accessed September 30, 2026link
  2. de Moura, Leonardo; Ullrich, Sebastian. The Lean 4 Theorem Prover and Programming Language. Automated Deduction–CADE 28, vol. 12699, pp. 625–635. 2021. \urlhttps://doi.org/10.1007/978-3-030-79876-5_37DOI
  3. Gale, David; Shapley, Lloyd S. College Admissions and the Stability of Marriage. The American Mathematical Monthly, vol. 69, no. 1, pp. 9–15. 1962. \urlhttps://doi.org/10.1080/00029890.1962.11989827DOI
  4. Ramos, Arthur Freitas. Gale–Shapley Deferred Acceptance in Lean 4. 2026. Commit f5f34f68a0e38441cdf5632adde5420d5fe0021e, September 26, 2026; inspected September 30, 2026. \urlhttps://github.com/Arthur742Ramos/gale-shapley-lean/tree/f5f34f68a0e38441cdf5632adde5420d5fe0021elink
  5. The mathlib Community. The Lean Mathematical Library. Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, pp. 367–381. 2020. \urlhttps://doi.org/10.1145/3372885.3373824DOI

Version history

  1. v1Initial depositCurrentSep 30, 2026