Theorem 2 -- DSIC and stability are incompatible under ESC
OpenFreeReplExchange.Supplement.theorem_2algorithmic-game-theorygraph-theorymechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1theoretical-computer-science
There is an ESC instance with four agents and two goods on which no exchange protocol is both dominant-strategy incentive compatible and stable:
DSIC quantifies over arbitrary strategy profiles of the other agents; it is not the Nash condition in which the others accept everything.
Differences from the source:
- encoding: four agents and two goods → agents
Fin 4and 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 2, Yang--Kandasamy, *Pairwise Exchanges of Freely Replicable Goods with Negative
Externalities*, arXiv:2603.12403 (held version, sha256 3ae07967...), p. 20 (PDF p. 22): there is a
four-agent, two-good ESC instance on which no exchange protocol is both dominant-strategy
incentive compatible and stable.
**Formalization Note.** DSIC quantifies over arbitrary strategies of all other agents, not merely
their accepting policies. -/
theorem theorem_2 :
∃ (x0 : Fin 4 → Fin 2 → Bool) (U : Fin 4 → Fin 4 → Fin 2 → ℝ)
(β : Fin 4 → Fin 4 → ℝ), IsESC U β ∧
∀ M : Protocol (Fin 4) 2, IsExchangeProtocol x0 M →
¬ (IsDSIC 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 2, p.20 (PDF p.22)