% Copyright (c) 2026 Arthur Freitas Ramos, David Barros Hulak, % and Ruy J. G. B. de Queiroz. % This manuscript source is licensed CC BY 4.0: % https://creativecommons.org/licenses/by/4.0/ \documentclass[11pt]{amsart} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage[a4paper,margin=29mm]{geometry} \usepackage{amsmath,amssymb,amsthm} \usepackage{booktabs,array} \usepackage{microtype} \usepackage{xurl} \usepackage[hidelinks]{hyperref} \hypersetup{ pdftitle={Deferred Acceptance in Lean for Finite Strict Preference Markets}, pdfauthor={Arthur Freitas Ramos; David Barros Hulak; Ruy J. G. B. de Queiroz}, pdfsubject={Expository note on a Lean formalization of deferred acceptance}, pdfkeywords={stable matching, deferred acceptance, Gale-Shapley, Lean 4, formal verification} } \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\decl}[1]{\nolinkurl{#1}} \newcommand{\source}[2]{\href{https://github.com/Arthur742Ramos/gale-shapley-lean/blob/f5f34f68a0e38441cdf5632adde5420d5fe0021e/#1}{#2}} \newcommand{\none}{\bot} \newcommand{\held}{h} \newcommand{\proposed}{P} \newcommand{\stable}{\operatorname{Stable}} \newcommand{\ach}{\operatorname{Ach}} \newcommand{\step}{\operatorname{step}} \newcommand{\quiet}{\operatorname{Quiet}} \newcommand{\N}{\mathbb{N}} \title[Deferred acceptance in Lean]{Deferred Acceptance in Lean for Finite Strict Preference Markets} \author{Arthur Freitas Ramos} \author{David Barros Hulak} \author{Ruy J. G. B. de Queiroz} \thanks{Author ORCID identifiers: Arthur Freitas Ramos, \href{https://orcid.org/0009-0003-3568-0325}{0009-0003-3568-0325}; David Barros Hulak, \href{https://orcid.org/0009-0002-8056-1774}{0009-0002-8056-1774}; Ruy J. G. B. de Queiroz, \href{https://orcid.org/0000-0003-1482-0977}{0000-0003-1482-0977}.} \thanks{Copyright 2026 the authors. This manuscript is licensed under \href{https://creativecommons.org/licenses/by/4.0/}{Creative Commons Attribution 4.0 International (CC BY 4.0)}.} \date{September 30, 2026} \subjclass[2020]{91B68, 68V20} \keywords{Stable matching, deferred acceptance, Gale--Shapley theorem, Lean 4, Mathlib} \begin{document} \begin{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. \end{abstract} \maketitle \section{Introduction} Gale and Shapley introduced deferred acceptance as a way to construct stable allocations from two-sided preferences \cite{galeshapley1962}. This note explains a Lean 4 development of the one-to-one, men-proposing procedure. The contribution of the note is an explicit correspondence between a mathematical argument and the definitions, invariants, and theorem statements in the source. The underlying existence and proposing-side optimality results are classical. We make no novelty or first-formalization claim. The development uses Lean 4 \cite{lean4} and Mathlib \cite{mathlib2020}. Throughout, ``men'' and ``women'' are the source's names for the proposing and receiving sides; they carry no further mathematical meaning. The model permits unequal side sizes and unmatched participants, while regarding every partner as preferable to being unmatched. Its scope is therefore narrower than models with ties, unacceptable partners, or many-to-one capacities. Every source reference in this note is pinned to the repository \cite{gsrepo} at commit \begin{center} \small\decl{f5f34f68a0e38441cdf5632adde5420d5fe0021e}. \end{center} This was also the repository's main-branch head when inspected on September 30, 2026. The present note does not extend the formalization beyond that revision. Sections 2--5 explain the mathematics; Section 6 identifies the formal interface; Sections 7--8 state the evidence, limitations, and preparation provenance. \section{The finite market model} Let $M$ and $W$ be finite types with decidable equality, and assume $W\ne\varnothing$. No assumption $|M|=|W|$ is imposed, and the principal theorems do not require $M\ne\varnothing$. A profile $p$ assigns to each $m\in M$ a decidable strict preference relation $\succ_m$ on $W$, and to each $w\in W$ a decidable strict preference relation $\succ_w$ on $M$. Both are irreflexive, transitive, and total on distinct elements. Thus, for example, $v\ne w$ implies $v\succ_m w$ or $w\succ_m v$. These are the fields of \source{GS/Basic.lean}{\decl{Profile}}. For a type $X$, write $X_\none$ for its optional extension, where $\none$ denotes being unmatched and $x\in X$ denotes a present partner. The source uses \texttt{Option X}, \decl{none}, and \texttt{some x}. Extend comparison of a real partner with an optional current partner by \[ w\succ_m^* a\quad\Longleftrightarrow\quad \begin{cases} \text{true},&a=\none,\\ w\succ_m v,&a=v\in W, \end{cases} \] and analogously for $m\succ_w^* b$. This is exactly the convention in \decl{prefersM} and \decl{prefersW}; there is no separate acceptability predicate. \begin{definition}[Matching and stability] A matching consists of maps $\mu_M:M\to W_\none$ and $\mu_W:W\to M_\none$ satisfying \begin{equation}\label{eq:inverse} \mu_M(m)=w\quad\Longleftrightarrow\quad\mu_W(w)=m. \end{equation} A pair $(m,w)$ blocks $\mu$ if \[ w\succ_m^*\mu_M(m)\quad\text{and}\quad m\succ_w^*\mu_W(w). \] The matching is stable if it has no blocking pair. A partner $w$ is stable-achievable for $m$, written $\ach_p(m,w)$, if there exists a stable matching $\mu$ with $\mu_M(m)=w$. \end{definition} The two directions in \eqref{eq:inverse} are stored as the fields \decl{inv1} and \decl{inv2} of \decl{Matching}. They imply that no agent has two partners. Since all partners are acceptable in the above sense, stability also rules out having both an unmatched man and an unmatched woman. This last observation is a mathematical consequence of the definition, not an additional theorem in the three-result public interface. \section{Proposal states and finite termination} \subsection{The specified step} A proposal state is $s=(\held,\proposed)$, where $\held:W\to M_\none$ records each woman's held proposer and $\proposed\subseteq M\times W$ records all proposals made so far. The structure \decl{DAState} does not itself require consistency of holders; that property is proved for states reachable from the initial state $s_0=(w\mapsto\none,\varnothing)$. A man is active in $s$ when no woman holds him and there is at least one woman to whom he has not proposed. If there is an active man, the function \decl{DA_step} selects one using classical choice. His next proposal is to his most-preferred member of \[ U_s(m)=\{w\in W:(m,w)\notin\proposed\}. \] The lemma \decl{exists_prefM_maximal} proves existence of such a maximal member of every nonempty finite set by induction on the set. Strict totality and transitivity justify its characterization as preferred to every distinct remaining member. The function \decl{nextWoman} chooses that member, and \decl{nextWoman_maximal} supplies this specification. Suppose the selected proposal is $(m,w)$. If $\held(w)=\none$, the woman holds $m$. If $\held(w)=q$, she holds $m$ exactly when $m\succ_w q$ and otherwise retains $q$. All other holders stay unchanged, and \begin{equation}\label{eq:insert} \proposed' = \proposed\cup\{(m,w)\},\qquad (m,w)\notin\proposed. \end{equation} If there is no active man, the step returns \decl{none} and makes no transition. A state is quiescent when its set of active men is empty. The detailed specifications \decl{DA_step_proposal_info} and \decl{DA_step_held_info} isolate these facts from the implementation. The update uses an optional-holder default, \texttt{getD m}, so an initially unheld woman also acquires $m$ even though $m\not\succ_w m$. All subsequent proofs use the specifications rather than assuming an informal algorithm silently has these properties. \subsection{The decreasing measure and the run} Put $N=|M\times W|=|M|\,|W|$ and define \[ T(s)=N-|\proposed|\in\N. \] Because $\proposed$ is a finite set of pairs, $|\proposed|\le N$. By \eqref{eq:insert}, each successful step increases its cardinality by exactly one. Hence $T(s')