(24) — at an equilibrium with ,
ProvedCompDesign.eq_24compensation-designp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-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 write . Let be a pure Nash equilibrium of with . Then for every set ,
Applied to an optimal budget-feasible set , the vector is feasible in the definition (20) of , which gives Theorem 5.1.
Differences from the source:
- generalization: T = S* ∈ arg max{v(T) : ∑_{i∈T} c_i ≤ B} → every set T; reason: (24) combines (23) with the union bound and uses neither the optimality nor the budget feasibility of S*; S* is an instance
Preamble
import Mathlib import Definitions.Def_CompDesignBFM_IsMonotoneSF import Definitions.Def_CompDesignBFM_IsSubmodularSF import Definitions.Def_CompDesignBFM_IsPNE open CompDesignBFM
Formal statement
namespace CompDesign
/-- Display (24), 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…):
for a pure Nash equilibrium `S` of `Γ^mc` with `v(S) > 0`, and `x_i = c_i/B`,
`v(T) ≤ v(S) (1 + ∑_{i∈T∖S} x_i/(1 − x_i))`.
**Formalization Note.** The paper states (24) for an optimal set `T = S*`; it is stated for every set
`T`. Assumption 3.1, `B > 0`, `c ≥ 0` and `c_i < B` for every agent are binders. -/
theorem eq_24 {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) (hpos : 0 < v S)
(T : Finset (Fin n)) :
v T ≤ v S * (1 + ∑ i ∈ T \ S, (c i / B) / (1 - c i / B)) := 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, eq. (24), p.27 (PDF 30)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.