Theorem 1 -- NIC and stability are incompatible
OpenFreeReplExchange.Supplement.theorem_1algorithmic-game-theorygraph-theorymechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1theoretical-computer-science
There is a general-utility instance with two agents and three goods on which no exchange protocol is both Nash incentive compatible and stable:
Here ranges over terminating protocols satisfying the paper's standing proposal rules, and NIC and stability are the published desiderata.
Differences from the source:
- encoding: two agents and three goods → agents
Fin 2and goodsFin 3; reason: finite index encoding with exactly the source cardinalities - encoding: exchange protocol in the standing model →
IsExchangeProtocol; reason: makes the section's termination, well-formedness, rejection, and nontrivial-proposal 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 1, Yang--Kandasamy, *Pairwise Exchanges of Freely Replicable Goods with Negative
Externalities*, arXiv:2603.12403 (held version, sha256 3ae07967...), p. 19 (PDF p. 21): there is a
two-agent, three-good general-utility instance on which no exchange protocol is both Nash incentive
compatible and stable.
**Formalization Note.** `Fin 2` and `Fin 3` encode the exact cardinalities. "Exchange protocol"
includes the standing protocol rules in `IsExchangeProtocol`; NIC and stability are the published
desiderata without alteration. -/
theorem theorem_1 :
∃ (x0 : Fin 2 → Fin 3 → Bool) (U : Fin 2 → Fin 2 → Fin 3 → ℝ), SignCond U ∧
∀ M : Protocol (Fin 2) 3, IsExchangeProtocol x0 M →
¬ (IsNIC x0 U M ∧ IsStable 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 1, p.19 (PDF p.21)