Theorem 5.1 —
ProvedCompDesign.theorem_5_1Throughout, 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.
Let (4) and let be the cost concentration term (20).
Theorem 5.1 (Pure Nash equilibrium PoA bound). Let . The game induced by the marginal contribution payment rule (8) satisfies
Explicitly:
- every pure Nash equilibrium of satisfies ;
- .
In particular, as , every pure Nash equilibrium attains value at least . This is the price-of-anarchy half of Main Result 2: a cost-oblivious rule guarantees about half of the full-information optimum.
Formalization Note λ is written l and enters as any with and for all . A price-of-anarchy bound is written as for every pure Nash equilibrium .
Differences from the source:
- encoding: λ = max_i c_i/B → any l with 0 ≤ l < 1 and c_i ≤ l·B for every i; reason: the paper's λ is the least such l and κ(l) and (2−l)/(1−l) are nondecreasing in l, so the case l = max_i c_i/B is the paper's statement; for n = 0 the max is undefined and the claim is trivial
- reading: Theorem 5.1 prints only λ = max_i c_i/B → hypothesis l < 1; reason: the bound (2−λ)/(1−λ) is undefined at λ = 1 and negative beyond, κ(λ) is infinite for λ ≥ 1, the proof uses c_i < B, and Main Result 2, which Theorem 5.1 makes precise, assumes λ < 1
- encoding: κ(λ) = max over finite families (20) → kappa l = sSup over families x : Fin m → ℝ, every m; reason: for 0 ≤ l < 1 the set is nonempty and bounded above, so sSup is its supremum, which Claim 5.1 shows is attained
- encoding: PoA_PNE ≤ ρ, a supremum of ratios OPT/v(S) with +∞ when OPT > 0 = v(S) (5) → OPT ≤ ρ · v(S) for every pure Nash equilibrium S; reason: equivalent to the ratio bound for every instance, including the +∞ convention, and avoids division
- encoding: "in particular, as λ → 0, every pure Nash equilibrium attains value at least (1/2 − o(1))OPT" → no separate clause; reason: it follows from the explicit clauses OPT ≤ (1+κ(l))v(S) ≤ ((2−l)/(1−l))v(S), since (1−l)/(2−l) → 1/2
import Mathlib import Definitions.Def_CompDesignBFM_IsMonotoneSF import Definitions.Def_CompDesignBFM_IsSubmodularSF import Definitions.Def_CompDesignBFM_IsPNE import Definitions.Def_CompDesignBFM_OPT import Definitions.Def_CompDesign_kappa open CompDesignBFM
namespace CompDesign
/-- Theorem 5.1 (Pure Nash equilibrium PoA bound), §5.1, p.27 (PDF 30) of Anagnostides et al., *Compensation Design*, arXiv:2607.14438 (version of November 3, 2026, sha256 3d305d4d…).
Let `λ = max_{i∈N} c_i/B`. The game `Γ^mc` induced by the marginal contribution payment rule (8)
satisfies `PoA_PNE ≤ 1 + κ(λ) ≤ (2 − λ)/(1 − λ)`.
**Formalization Note.** `λ` is written `l` and enters as any `l` with `0 ≤ l < 1` and `c_i ≤ l B` for
all `i`; the paper's `λ = max_i c_i/B` is the least such `l`, and `κ` is monotone in `l`. `λ < 1` is
the regime of Main Result 2, without which the right-hand side is undefined. `PoA_PNE ≤ ρ` is written as
`OPT ≤ ρ v(S)` for every pure Nash equilibrium `S`, which is (5) without the ratio. The sentence "as
`λ → 0`, every pure Nash equilibrium attains value at least `(1/2 − o(1)) OPT`" follows from the two
explicit clauses. Assumption 3.1, `B > 0` and `c ≥ 0` are the standing assumptions of §3.1. -/
theorem theorem_5_1 {n : ℕ} (v : Finset (Fin n) → ℝ) (B : ℝ) (c : Fin n → ℝ) (hB : 0 < B)
(hv0 : v ∅ = 0) (hm : IsMonotoneSF v) (hs : IsSubmodularSF v) (hc : ∀ i, 0 ≤ c i)
(l : ℝ) (hl0 : 0 ≤ l) (hl1 : l < 1) (hcl : ∀ i, c i ≤ l * B) :
(∀ S : Finset (Fin n), IsPNE v B c S → OPT v B c ≤ (1 + kappa l) * v S) ∧
1 + kappa l ≤ (2 - l) / (1 - l) := by sorry
end CompDesign
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.