Theorem 15 -- M3 is Pareto-efficient in X under LEC
OpenFreeReplExchange.Supplement.theorem_15algorithmic-game-theorygraph-theorymechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1theoretical-computer-science
Suppose an ESC coalition has aggregate competition for every agent. If every agent participates and follows the accepting policy, then M3's terminal allocation is Pareto-efficient in the exchange-outcome class .
The conclusion is only relative to , not the larger class ; Pareto efficiency in is the paper's Conjecture 1.
Differences from the source:
- encoding: a nonempty finite set of agents with the paper's fixed order and finitely many goods → a nonempty finite linearly ordered type
Aand goodsFin m; reason: exact finite representation used by the published base mission, with nonemptiness made explicit because the source proof chooses a minimizing agent - encoding: all agents participate and accept → participating set
Finset.univand profileacceptAll; reason: exact Lean representation of the source conditions - generalization: M3 with the paper's fixed global exchange order → M3 for every injective rank on exchanges; reason: the argument uses only that the global order is fixed and total, and every source order is such a rank
- generalization: every good is initially held by at least one agent as the paper's WLOG convention → no initial-coverage hypothesis; reason: the proof of Theorem 15 does not use coverage, and the Lean claim specializes to every source instance
Preamble
import Mathlib import Definitions.Def_FreeReplExchange_Supplement_IsExchangeProtocol set_option autoImplicit false
Formal statement
namespace FreeReplExchange.Supplement
/-- Theorem 15, Yang--Kandasamy, *Pairwise Exchanges of Freely Replicable Goods with Negative
Externalities*, arXiv:2603.12403 (held version, sha256 3ae07967...), p. 41 (PDF p. 43): under ESC
and low externality competition, when every agent participates and accepts, the allocation produced
by M3 is Pareto-efficient among the MIC exchange outcomes `X`.
**Formalization Note.** Participation is `Finset.univ` and the strategy profile is `acceptAll`.
The conclusion is only relative to `X`; no Pareto-efficiency claim is made for the larger class `Y`.
The injective rank is the published global tie order. -/
theorem theorem_15 {A : Type*} [Fintype A] [LinearOrder A] [Nonempty A] {m : ℕ}
(x0 : A → Fin m → Bool) (U : A → A → Fin m → ℝ) (β : A → A → ℝ)
(rk : Exchange A m → ℕ) (hrk : Function.Injective rk)
(hESC : IsESC U β) (hLEC : IsLEC β) :
ParetoEfficientIn U (exchangeOutcomes x0 U Finset.univ)
(xInf x0 (M3 x0 U rk) Finset.univ acceptAll) := by sorry
end FreeReplExchange.Supplement
Source
Yang--Kandasamy, Pairwise Exchanges of Freely Replicable Goods with Negative Externalities, arXiv:2603.12403 (held version, sha256 3ae07967...), Theorem 15, p.41 (PDF p.43)