(22)–(23) — at an equilibrium, for
ProvedCompDesign.eq_22_23compensation-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 . Let be a pure Nash equilibrium of with and let . Since does not prefer to opt in, and ,
and, with ,
This bounds the relative marginal gain of every absent agent at an equilibrium; summing it over an optimal set gives Theorem 5.1.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_CompDesignBFM_IsMonotoneSF import Definitions.Def_CompDesignBFM_IsSubmodularSF import Definitions.Def_CompDesignBFM_IsPNE open CompDesignBFM
Formal statement
namespace CompDesign
/-- Displays (22) and (23), 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…).
Let `S` be a pure Nash equilibrium of `Γ^mc` with `v(S) > 0` and `i ∉ S`. Since `i` does not prefer
to opt in and `c_i < B`,
`v(S ∪ {i}) ≤ v(S) B/(B − c_i)` and `v(S ∪ {i}) − v(S) ≤ v(S) c_i/(B − c_i)` (22), and with
`x_i = c_i/B`, `v(S ∪ {i}) − v(S) ≤ x_i/(1 − x_i) · v(S)` (23).
**Formalization Note.** Assumption 3.1, `B > 0`, `c ≥ 0` and `c_i < B` for every agent are binders. -/
theorem eq_22_23 {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)
(i : Fin n) (hi : i ∉ S) :
(v (insert i S) ≤ v S * (B / (B - c i)) ∧ v (insert i S) - v S ≤ v S * (c i / (B - c i))) ∧
v (insert i S) - v S ≤ (c i / B) / (1 - c i / B) * v 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 5.1, §5.1, eqs. (22)–(23), p.27 (PDF 30)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.