% Copyright (c) 2026 Arthur Freitas Ramos, David Barros Hulak, % and Ruy J. G. B. de Queiroz. Manuscript source 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{microtype} \usepackage{needspace} \usepackage{xurl} \usepackage[hidelinks]{hyperref} \hypersetup{pdftitle={A Lean Formalization of Myerson-Satterthwaite Impossibility for Continuous Bilateral Trade}, pdfauthor={Arthur Freitas Ramos; David Barros Hulak; Ruy J. G. B. de Queiroz}, pdfsubject={Exact statement and proof of a registered continuous bilateral-trade impossibility formalization}, pdfkeywords={Myerson-Satterthwaite, bilateral trade, Bayesian incentive compatibility, Lean 4, formal verification}} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\ind}{\mathbf{1}} \newcommand{\decl}[1]{{\small\nolinkurl{#1}}} \newcommand{\source}[2]{\href{https://github.com/Arthur742Ramos/myerson-satterthwaite-lean/blob/f4dae9744e26a499679e4b8a7aeb9d82dd3f11ee/#1}{#2}} \title[Myerson-Satterthwaite impossibility in Lean]{A Lean Formalization of Myerson-Satterthwaite Impossibility for Continuous Bilateral Trade} \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. Licensed under \href{https://creativecommons.org/licenses/by/4.0/}{Creative Commons Attribution 4.0 International (CC BY 4.0)}.} \date{October 1, 2026} \subjclass[2020]{Primary 91B26; Secondary 68V20} \keywords{Myerson-Satterthwaite theorem, bilateral trade, Bayesian incentive compatibility, envelope theorem, budget balance, Lean 4, Mathlib} \begin{document} \begin{abstract} We present a source-grounded account of a Lean 4 formalization of the Myerson-Satterthwaite impossibility theorem for continuous bilateral trade. Buyer values and seller costs are independent, with atomless probability measures supported on compact real intervals whose interiors overlap. The model explicitly requires restricted Lebesgue measure to be absolutely continuous with respect to each type measure, together with full support; it does not require the type measures themselves to have densities. Under allocation and transfer measurability and integrability conditions, the registered theorem excludes the simultaneous satisfaction of almost-sure ex post efficiency, Bayesian incentive compatibility at every admissible type and report, interim individual rationality, and weak ex ante budget balance. The proof derives envelope identities from incentive inequalities, identifies the efficient allocation almost everywhere, and uses a layer-cake representation to show that the required information rents strictly exceed efficient surplus. We explain the analytic steps, their Lean declarations, and the verification evidence for the exact Palomar-registered source revision. This is an exposition of a classical result and an existing formal artifact, without a claim of mathematical novelty or formalization priority. \end{abstract} \maketitle \raggedbottom \section{Mathematical context and scope} Myerson and Satterthwaite's bilateral-trade theorem concerns a buyer and a seller who privately know their respective valuations for a single indivisible object. Their 1983 paper characterizes incentive-compatible, individually rational trading mechanisms and establishes an impossibility of ex post efficient trade without outside subsidies under overlapping independent type distributions \cite{myerson1983}. The present paper explains the continuous-type impossibility result implemented in the Lean repository \cite{ramos2026}, rather than the original paper's complete characterization or its optimal-mechanism constructions. The formal artifact uses Lean 4 \cite{lean4} and Mathlib \cite{mathlib2020}. Its central declaration is \decl{MS.Palomar.myersonSatterthwaite}. It is registered as \href{https://palomar-registry.org/entry?id=PALOMAR-2026-09-26-000002&version=1}{Palomar entry PALOMAR-2026-09-26-000002, version 1} \cite{palomar2026}. All implementation descriptions in this paper refer to the registered commit, not to an evolving default branch. The main mathematical obstruction is an accounting inequality. Incentive compatibility forces interim utilities to accumulate information rents. Efficiency fixes the associated interim trade probabilities. When type intervals overlap, the sum of the resulting rent terms is strictly greater than the expected efficient surplus. Individual rationality prevents the mechanism from offsetting this excess by charging negative utility to its boundary types, while weak ex ante budget balance prevents financing the excess with an expected outside subsidy. The formal proof makes explicit several conditions sometimes suppressed in an informal statement: the direction of absolute continuity between measures, sectionwise measurability and integrability, the almost-everywhere meaning of efficiency, and the quantification of incentive constraints at all types, including endpoints. These details determine what the checked theorem says. Our contribution here is an auditable exposition of that statement and its proof architecture. We do not infer priority from the existence of a registry entry or claim that the development covers every version of bilateral-trade impossibility. \section{The exact model} \label{sec:model} \subsection{Types and distributions} The buyer's value is $v\in I_B=[a_1,b_1]$ and the seller's cost is $c\in I_S=[a_2,b_2]$. The source assumes \begin{equation}\label{eq:overlap} a_10$ for every open set $O$ meeting $(a_1,b_1)$, and similarly $\nu(O)>0$ whenever $O$ meets $(a_2,b_2)$. These full-support clauses are retained in the formal model and are used directly in the strict-positivity argument. As a mathematical observation, \eqref{eq:ac} already implies these clauses: any such open intersection has positive Lebesgue measure. Nevertheless, ordinary topological full support alone is not a substitute for \eqref{eq:ac} in the registered statement. In particular, the theorem is not restricted to type measures possessing densities. An atomless mixture of a positive-weight uniform distribution on an interval and a singular probability measure on the same interval can satisfy these conditions without being absolutely continuous with respect to Lebesgue measure. This observation illustrates the assumptions; the repository does not supply a formal construction of that example. \subsection{Allocation, transfers, and interim quantities} The direct mechanism consists of real-valued functions $q,t_b,t_c:\R^2\to\R$. At a report pair $(v,c)$, $q(v,c)$ is the probability of trade, $t_b(v,c)$ is the payment collected from the buyer, and $t_c(v,c)$ is the payment delivered to the seller. Transfers may be signed. On $I_B\times I_S$, the source requires $0\le q\le1$ pointwise. It assumes that $q$ is almost-everywhere strongly measurable under $\pi$, and that each buyer section $q(v,\cdot)$ for $v\in I_B$ and each seller section $q(\cdot,c)$ for $c\in I_S$ is almost-everywhere strongly measurable under the respective opposing type measure. Both transfers are integrable under $\pi$. In addition, every relevant interim section is integrable: $t_b(v,\cdot)$ under $\nu$ for each $v\in I_B$, and $t_c(\cdot,c)$ under $\mu$ for each $c\in I_S$. These section hypotheses are stronger than merely having section integrability for almost every type. They ensure that the all-type incentive and participation inequalities use genuine finite integrals. Allocation sections are integrable by their measurability, boundedness, and the probability-measure assumptions. The four global definitions in \source{MS/Defs.lean}{\decl{MS/Defs.lean}} are the following Bochner integrals, with scalar values: \begin{align} Q(v)&=\int q(v,c)\,d\nu(c),& R(c)&=\int q(v,c)\,d\mu(v),\label{eq:qr}\\ U(v)&=\int\bigl(vq(v,c)-t_b(v,c)\bigr)\,d\nu(c),& W(c)&=\int\bigl(t_c(v,c)-cq(v,c)\bigr)\,d\mu(v). \label{eq:uw} \end{align} Their names are \decl{interimQ}, \decl{interimR}, \decl{interimU}, and \decl{interimW}. For an implementation instance \decl{D : MSData}, the corresponding derived definitions are \decl{D.Q}, \decl{D.R}, \decl{D.U}, and \decl{D.W}. \subsection{Efficiency, incentives, participation, and budget} Ex post efficiency is required almost surely on the two strict-order regions: \begin{equation}\label{eq:eff} q=1\quad\pi|_{\{c0. \end{equation} \end{proposition} \begin{proof} Support containment gives $H(t)=0$ for $t\le a_2$ and for $t\ge b_1$. Thus the first integral in \eqref{eq:bch} can start at $\ell$, and the second can end at $r$. Splitting the integrals at these endpoints shows \[ \int_\ell^{b_1}H+\int_{a_2}^{r}H-\int_{a_2}^{b_1}H =\int_\ell^r H. \] For $t\in(\ell,r)$, full support assigns positive seller probability to costs strictly below $t$ and positive buyer probability to values strictly above $t$. Hence $H(t)>0$ throughout that nonempty open interval. Since $H$ is nonnegative and integrable, its integral there is strictly positive. \end{proof} The positivity claim is \decl{MSData.H_pos}; the exported strict inequality is \decl{MSData.BC_gt_S}. The equality in \eqref{eq:rentgap} is established inside the latter proof as a local intermediate fact. No density, hazard rate, or division by a density is needed in this argument. \section{The accounting contradiction} \begin{proof}[Proof of Theorem~\ref{thm:ms}] Product integrability and Fubini identify the expected interim utilities with the expectations of the realized utilities in \eqref{eq:uw}. Adding the buyer and seller identities, and using efficiency, gives \begin{align} \E_\mu[U]+\E_\nu[W] &=\E_\pi[(v-c)q]-\bigl(\E_\pi[t_b]-\E_\pi[t_c]\bigr)\notag\\ &=S-\bigl(\E_\pi[t_b]-\E_\pi[t_c]\bigr)\le S.\label{eq:accounting} \end{align} The last inequality is weak ex ante budget balance. On the other hand, \eqref{eq:expected-rents} and endpoint IR imply \[ \E_\mu[U]+\E_\nu[W] =U(a_1)+W(b_2)+B+C\ge B+C>S, \] contradicting \eqref{eq:accounting}. \end{proof} This is the organization of \decl{MSData.MS_impossible} in \source{MS/Main.lean}{\decl{MS/Main.lean}}. Before the accounting step, the source derives integrability of $vq$, $cq$, the realized utilities, and the transfer difference. Compact support bounds the type coordinates, and the allocation range bounds $q$. The final contradiction uses only $U(a_1)\ge0$ and $W(b_2)\ge0$ from the stronger all-type participation hypotheses. The registered theorem nevertheless retains all-type interim IR; a separate minimized-assumption theorem is not provided. The same calculation displays the required expected subsidy for any efficient BIC and interim-IR candidate if budget balance is dropped: \begin{equation}\label{eq:subsidy} \E_\pi[t_c]-\E_\pi[t_b] =U(a_1)+W(b_2)+B+C-S \ge\int_\ell^r H(t)\,dt>0. \end{equation} This is an explanatory rearrangement of the proved identities, not a separately exported subsidy theorem or a formal construction attaining the lower bound. \section{Formal organization and semantic boundaries} The development separates mathematical data from its public registry interface. \decl{MSData} is a structure containing the endpoints, measures, rules, and hypotheses. The internal lemmas can therefore use a single argument $D$ without repeatedly unpacking the entire model. The public proposition \decl{MS.IsModel} expresses the same data as a conjunction, while \decl{MS.Overlap} isolates the four interval inequalities. The public impossibility theorem is a wrapper around the internal contradiction. The implementation has five substantive modules, totaling 1,441 lines at the registered revision. \decl{MS/Defs.lean} supplies the model and interim definitions. \decl{MS/Envelope.lean} derives monotonicity, Lipschitz continuity, envelope formulas, and expected rents. \decl{MS/Efficiency.lean} supplies the null-diagonal argument, efficient interim allocations, layer-cake formula, and strict rent gap. \decl{MS/Main.lean} performs the final accounting, and \decl{MS/Palomar.lean} exposes the selected theorem. Appendix~\ref{app:guide} gives a concise declaration map. \subsection{Why integrability is explicit} Mathlib's Bochner integral is a total operation, so an expression involving an integral alone does not establish the analytic conditions expected in economic notation. The product and section hypotheses prevent the model from relying on the totalized integral's value for a nonintegrable transfer. Bounded measurable allocation sections provide finite trade probabilities; compact support then controls the value and cost terms. The source repeatedly supplies integrability proofs when applying linearity or Fubini, rather than treating these operations as unrestricted algebraic rewrites. Another important boundary is the coexistence of two notions of almost-everywhere equality. Efficiency is expressed under $\pi$, whereas the envelope and rent formulas use Lebesgue interval integrals. The domination assumptions connect these notions only after taking sections, as explained in Section~\ref{sec:gap}. Full support supplies strict positivity, while atomlessness removes ties and the distinction between open and closed threshold sets. These are distinct roles, even though some distribution hypotheses logically imply others. \subsection{What the theorem does not formalize} The registered result concerns independent atomless types on finite, overlapping intervals and real quasi-linear utilities. It does not formalize correlated types, atomic or finite-discrete type models, unbounded supports, risk aversion, multiple objects, or multiple traders. It also does not establish the revelation principle, characterize all implementable allocations, construct an optimal inefficient mechanism, or prove attainability of the subsidy bound \eqref{eq:subsidy}. The impossibility applies to randomized allocations because $q$ may take any value in $[0,1]$ before efficiency is imposed. Its efficiency requirement is almost sure, its incentive and participation constraints are interim and all-type, and its budget constraint is ex ante and weak. Pointwise efficient mechanisms or pointwise balanced mechanisms satisfying the remaining hypotheses are included as stronger special cases; the development does not independently formalize those implications. \section{Artifact provenance and verification evidence} \label{sec:verification} \subsection{The registered revision} The Palomar record \cite{palomar2026} identifies the repository \decl{Arthur742Ramos/myerson-satterthwaite-lean}, with commit \begin{center} \decl{f4dae9744e26a499679e4b8a7aeb9d82dd3f11ee}. \end{center} It records Lean \decl{v4.35.0-rc2} and Mathlib revision \begin{center} \decl{065356127b1dc0016f66b7283ce0ce2c4055aa55}. \end{center} The committed \decl{lake-manifest.json} pins the dependencies. The source repository and its metadata attribute the formalization to Arthur Freitas Ramos and license the code under BSD-3-Clause. This manuscript is distributed under CC BY 4.0; the two licenses govern different artifacts. \decl{Challenge.lean} declares the selected statement and six definitions using only Mathlib imports. It contains one deliberate statement \decl{sorry}, used as the target specification for comparison. \decl{Solution.lean} imports the implementation, whose five substantive modules contain no proof holes. The permitted axioms listed in the registered comparator configuration are \decl{propext}, \decl{Classical.choice}, and \decl{Quot.sound}. The deliberate challenge hole is not an implementation proof and is not presented as one. \subsection{Historical checks and present inspection} The registry's archived \href{https://data.palomar-registry.org/evidence/PALOMAR-2026-09-26-000002-v1/cce3d9405c5f2c5820dffd591aabd7bf89f1763a04fe3cd3117f210cddc2604e/mechanical-report.json}{mechanical report} has status \decl{pass}, stage \decl{complete}, and verification timestamp 2026-09-26 02:28:25 UTC. It records a successful solution build and Comparator acceptance by the Lean default kernel, \decl{nanoda}, and \decl{con-ron}. The associated \href{https://github.com/PalomarRegistry/PalomarSubmission/actions/runs/36211565961}{workflow run} is linked in the record. These are historical verification results for the pinned source, not newly executed checks performed for this paper. For the present exposition, the pinned source files and archived report were inspected. The downloaded challenge and solution SHA-256 values match those in the registered record; the archived report's SHA-256 value also matches its recorded digest. A fresh Lean compilation or Comparator run was not performed during manuscript preparation. The present audit supports the account of the source and its archived evidence; it does not turn that archival evidence into a claim of fresh execution. The record's automated review has outcome \decl{neutral} and specifically warns that the \decl{MS.IsModel} docstring mentions positive densities although the definition has the domination conditions \eqref{eq:ac}. This paper follows the actual definition. The source's README and formalization metadata also say that no density requirement is imposed. Registration, mechanical checking, and review are distinct evidence; none alone proves that an informal paraphrase faithfully states the formal theorem. \subsection{AI assistance} The repository's \decl{formalization.yaml} reports AI assistance by \decl{gpt-6-luna} through the Codex CLI for historical proof engineering. OpenAI GPT-6.1 assisted with drafting this manuscript, inspecting the registered source, organizing the proof exposition, and editorial and consistency checks. AI assistance is not authorship, and the manuscript authors are responsible for its claims. The registered mechanical verification evidence concerns the formal artifact; it does not certify this prose or imply that the authors independently checked every proof step by hand. \section{Conclusion} The registered formalization proves a continuous bilateral-trade impossibility under an explicit measure-theoretic model. Its proof connects incentive inequalities to absolutely continuous utility envelopes, then connects almost-sure efficiency to Lebesgue rent integrals through the domination of Lebesgue measure by the type measures. A positive overlap integral measures the excess of the forced information rents over efficient surplus, yielding a contradiction with participation and expected budget balance. The source and its archived verification evidence make this argument inspectable at a fixed revision, while the distinction between the formal statement and its informal presentation remains part of the verification boundary. \appendix \section{Guide to the checked declarations} \label{app:guide} All names below have prefix \decl{MSData.} unless another prefix is shown. The links point to files at the registered commit. \begin{description} \item[Model and interface.] \source{MS/Defs.lean}{\decl{MSData}} stores all hypotheses. \source{MS/Palomar.lean}{\decl{MS.IsModel}} is the public conjunction; \decl{MS.Palomar.myersonSatterthwaite} returns \decl{False} from it. \item[Envelope analysis.] \source{MS/Envelope.lean}{\decl{Q_mono}, \decl{R_anti}, \decl{U_lip}, \decl{W_lip}} derive monotonicity and Lipschitz bounds. \decl{U_envelope}, \decl{W_envelope}, \decl{EU_eq}, and \decl{EW_eq} give \eqref{eq:uenv}--\eqref{eq:expected-rents}. \item[Efficiency and surplus.] \source{MS/Efficiency.lean}{\decl{diag_null}, \decl{q_ae_ind}, \decl{Q_ae}, \decl{R_ae}} identify efficient allocations and interim probabilities. \decl{B_eq}, \decl{C_eq}, \decl{S_layercake}, and \decl{eff_payoff} give \eqref{eq:bch}--\eqref{eq:effpayoff}. \item[Strictness and contradiction.] \source{MS/Efficiency.lean}{\decl{H_pos}, \decl{BC_gt_S}} establish the positive rent gap. \source{MS/Main.lean}{\decl{MS_impossible}} combines it with expected-utility accounting and endpoint IR. \end{description} \section{A uniform-distribution illustration} For independent uniform types on $[0,1]$, one has $H(t)=t(1-t)$ on that interval. Therefore \[ S=\int_0^1 t(1-t)\,dt=\frac16, \qquad B=C=\frac16, \qquad B+C-S=\frac16. \] The expected rent requirements are twice the efficient surplus before adding nonnegative endpoint utilities. Any efficient BIC and interim-IR candidate under these assumptions must therefore have expected subsidy at least $1/6$ by \eqref{eq:subsidy}. This calculation illustrates the general proof; it is not an additional Lean theorem in the repository, and it does not assert the construction of an attaining mechanism. \bibliographystyle{amsplain} \bibliography{references} \end{document}