Theorem 3 -- IR and efficiency are incompatible
OpenFreeReplExchange.Supplement.theorem_3algorithmic-game-theorygraph-theorymechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1theoretical-computer-science
There is a general-utility instance with five agents and two goods on which no exchange protocol satisfies individual rationality and efficiency simultaneously:
Efficiency is the published desideratum and therefore includes MIC. Individual rationality compares an agent's accept-all utility when she participates with her utility from the exchanges conducted in her absence.
Differences from the source:
- encoding: five agents and two goods → agents
Fin 5and goodsFin 2; reason: finite index encoding with exactly the source cardinalities - encoding: exchange protocol in the standing model →
IsExchangeProtocol; reason: makes the standing protocol rules explicit without changing the protocol class
Preamble
import Mathlib import Definitions.Def_FreeReplExchange_Supplement_IsExchangeProtocol set_option autoImplicit false
Formal statement
namespace FreeReplExchange.Supplement
/-- Theorem 3, Yang--Kandasamy, *Pairwise Exchanges of Freely Replicable Goods with Negative
Externalities*, arXiv:2603.12403 (held version, sha256 3ae07967...), p. 23 (PDF p. 25): there is a
five-agent, two-good general-utility instance on which no exchange protocol satisfies individual
rationality and efficiency simultaneously.
**Formalization Note.** The published `IsEfficient` includes MIC, exactly as Desideratum 6 does;
`IsIR` is the participation-comparison notion, not comparison with the initial allocation. -/
theorem theorem_3 :
∃ (x0 : Fin 5 → Fin 2 → Bool) (U : Fin 5 → Fin 5 → Fin 2 → ℝ), SignCond U ∧
∀ M : Protocol (Fin 5) 2, IsExchangeProtocol x0 M →
¬ (IsIR x0 U M ∧ IsEfficient x0 U M) := 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 3, p.23 (PDF p.25)