Proof of Theorem 5.1 — a pure Nash equilibrium with forces
ProvedCompDesign.thm_5_1_zero_casecompensation-designp2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchypure-nash-equilibriumsubmodular-functions
Throughout, is the set of agents, the budget, the private costs, and a value function satisfying Assumption 3.1: , monotone () and submodular ( whenever and ). The marginal-contribution payment is if and , and otherwise (8); agent 's utility is if and otherwise.
Assume moreover for every agent , and let (4). If is a pure Nash equilibrium of with , then
This disposes of the zero-value equilibria in the proof of Theorem 5.1, so that the bound holds at them too.
Formalization Note OPT is the published CompDesignBFM.OPT, a maximum over the budget-feasible sets.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_CompDesignBFM_IsMonotoneSF import Definitions.Def_CompDesignBFM_IsSubmodularSF import Definitions.Def_CompDesignBFM_IsPNE import Definitions.Def_CompDesignBFM_OPT open CompDesignBFM
Formal statement
namespace CompDesign
/-- Zero-value equilibria, proof of Theorem 5.1, §5.1, p.27 (PDF 30) of Anagnostides et al., *Compensation Design*, arXiv:2607.14438 (version of November 3, 2026, sha256 3d305d4d…):
if a pure Nash equilibrium `S` of `Γ^mc` has `v(S) = 0`, then `OPT = 0`.
**Formalization Note.** Assumption 3.1, `B > 0`, `c ≥ 0` and `c_i < B` for every agent (which the proof
of Theorem 5.1 uses) are binders. `OPT` is (4), `max {v(T) : ∑_{i∈T} c_i ≤ B}`. -/
theorem thm_5_1_zero_case {n : ℕ} (v : Finset (Fin n) → ℝ) (B : ℝ) (c : Fin n → ℝ) (hB : 0 < B)
(hv0 : v ∅ = 0) (hm : IsMonotoneSF v) (hs : IsSubmodularSF v) (hc : ∀ j, 0 ≤ c j)
(hcB : ∀ j, c j < B) (S : Finset (Fin n)) (hS : IsPNE v B c S) (hzero : v S = 0) :
OPT v B c = 0 := 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 5.1, §5.1, p.27 (PDF 30)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.