Theorem C.1 — targeted implementation (58): the pure Nash equilibria are exactly and every CCE is supported on
ProvedCompDesign.Supplement.theorem_C_1algorithmic-game-theorycompensation-designp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1price-of-anarchy
Throughout, is the set of agents, the budget and the private costs. Let be a target set with bonuses () such that (57), and let if and otherwise (58).
Theorem C.1 (Targeted implementation with outsider exclusion). Suppose for every . Under the rule (58),
- a set is a pure Nash equilibrium if and only if ;
- every coarse correlated equilibrium is supported on : for every .
When costs are known, any target set, for instance the output of an approximation algorithm for non-monotone submodular maximization, can be implemented exactly.
Differences from the source:
- generalization: every pure Nash equilibrium is exactly T → S is a pure Nash equilibrium iff S = T; reason: adds that T is an equilibrium, which the proof shows (T is the unique dominant profile); the forward direction is the source's claim
- encoding: supported on the single set T → μ(S) = 0 for every S ≠ T; reason: the support of a weight function
Preamble
import Mathlib import Definitions.Def_CompDesign_Supplement_IsPNEOf import Definitions.Def_CompDesign_Supplement_IsCCEOf import Definitions.Def_CompDesign_Supplement_targetedPay set_option autoImplicit false
Formal statement
namespace CompDesign.Supplement
/-- Theorem C.1 (Targeted implementation with outsider exclusion), App. C, p.71 (PDF 74) of Anagnostides et al., *Compensation Design*, arXiv:2607.14438 (version of November 3, 2026,
sha256 3d305d4d…).
Suppose that every non-target agent has strictly positive cost: `c_i > 0` for all `i ∉ T`. Under the
payment rule (58), every pure Nash equilibrium is exactly `T`. Moreover, every coarse correlated
equilibrium is supported on the single set `T`.
**Formalization Note.** The target `T` comes with bonuses `b_i > 0` (`i ∈ T`) satisfying (57),
`∑_{i∈T} (c_i + b_i) ≤ B`. The first clause is stated as an equivalence (`S` is a pure Nash
equilibrium iff `S = T`), since the proof shows `T` is the unique dominant profile. "Supported on `T`"
is `μ(S) = 0` for every `S ≠ T`. No value function is involved. -/
theorem theorem_C_1 {n : ℕ} (B : ℝ) (hB : 0 < B) (c : Fin n → ℝ) (hc : ∀ i, 0 ≤ c i)
(T : Finset (Fin n)) (b : Fin n → ℝ) (hb : ∀ i ∈ T, 0 < b i)
(hbud : ∑ i ∈ T, (c i + b i) ≤ B) (hout : ∀ i, i ∉ T → 0 < c i) :
(∀ S : Finset (Fin n), IsPNEOf (targetedPay T c b) c S ↔ S = T) ∧
∀ μ : Finset (Fin n) → ℝ, IsCCEOf (targetedPay T c b) c μ → ∀ S, S ≠ T → μ S = 0 := by sorry
end CompDesign.Supplement
Source
Anagnostides, Bhawalkar, Liaw, Mehta, Paes Leme, Teng, Velegkas, Zheng, Compensation Design, arXiv:2607.14438 (version of November 3, 2026, sha256 3d305d4d…), Theorem C.1, App. C, p.71 (PDF 74)