Proof of Theorem 4.1 — any terminal state is a pure Nash equilibrium
ProvedCompDesign.thm_4_1_terminal_is_pnecompensation-designp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1price-of-anarchypure-nash-equilibriumsubmodular-functions
Let be any set function, any budget and any costs, and consider the game with utilities for and otherwise. If is terminal, that is, no agent has a strict better response from , then is a pure Nash equilibrium in the sense of Definition 3.1:
Together with termination, this gives the existence part of Theorem 4.1.
Formalization Note The pure Nash equilibrium is the published CompDesignBFM.IsPNE, which is Definition 3.1 for .
Differences from the source:
- generalization: Assumption 3.1, B > 0, c ≥ 0 and max_i c_i < B (the standing assumptions and the hypothesis of Theorem 4.1) → no hypotheses on v, B, c; reason: the implication from terminal to Definition 3.1 is a rewriting of the two cases of a switch and uses none of them; the paper's setting is an instance
Preamble
import Mathlib import Definitions.Def_CompDesignBFM_IsPNE import Definitions.Def_CompDesign_IsStrictImprovement open CompDesignBFM
Formal statement
namespace CompDesign
/-- Terminal states are equilibria, proof of Theorem 4.1, §4.1, p.17 (PDF 20) of Anagnostides et al., *Compensation Design*, arXiv:2607.14438 (version of November 3, 2026, sha256 3d305d4d…):
a set `S` from which no agent has a strict better response in `Γ^mc` is a pure Nash equilibrium
(Definition 3.1, p.14).
**Formalization Note.** The implication holds for every `v`, `B` and `c`, so the standing
assumptions are not binders. -/
theorem thm_4_1_terminal_is_pne {n : ℕ} (v : Finset (Fin n) → ℝ) (B : ℝ) (c : Fin n → ℝ)
(S : Finset (Fin n)) (h : ∀ S' : Finset (Fin n), ¬ IsStrictImprovement v B c S S') :
IsPNE v B c S := by sorry
end CompDesign
Source
Anagnostides, Bhawalkar, Liaw, Mehta, Paes Leme, Teng, Velegkas, Zheng, Compensation Design, arXiv:2607.14438 (version of November 3, 2026, sha256 3d305d4d…), proof of Theorem 4.1, §4.1, p.17 (PDF 20)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.