Main Result 2 — strict better responses of terminate at pure Nash equilibria, each with
ProvedCompDesign.main_result_2Throughout, 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).
Main Result 2, in the precise form of Theorems 4.1 and 5.1. Let . For any monotone submodular value function, in the game induced by the marginal contribution rule:
- every sequence of strict better responses terminates (no infinite sequence in which each is a strict better response from );
- has a pure Nash equilibrium;
- every pure Nash equilibrium satisfies ;
- .
In particular every pure Nash equilibrium satisfies : the principal secures a constant fraction of the full-information optimum without knowing any cost.
Formalization Note λ is written l and enters as any with and for all . A ratio bound is written .
Differences from the source:
- generalization: Main Result 2 as printed: a pure Nash equilibrium exists, and OPT/v(S) ≤ (2−λ)/(1−λ) for every one → adds termination of every strict better-response sequence and the sharper constant 1 + κ(λ); reason: these are the clauses of Theorems 4.1 and 5.1, which the paper gives as the precise versions of Main Result 2; the printed claim follows from clauses 2–4
- 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
- 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: OPT/v(S) ≤ (2 − λ)/(1 − λ) = 2 + o_λ(1) → OPT ≤ (1 + κ(l)) v(S) and 1 + κ(l) ≤ (2 − l)/(1 − l), no asymptotic clause; reason: the ratio bound and the limit 2 as λ → 0 follow from the two explicit inequalities
- encoding: every sequence of strict better responses terminates → there is no f : ℕ → Finset (Fin n) with a strict better response from f t to f (t+1) for every t; reason: a sequence terminates iff it is not infinite; this is the standard well-foundedness formulation
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_IsStrictImprovement import Definitions.Def_CompDesign_kappa open CompDesignBFM
namespace CompDesign
/-- Main Result 2, §1.2.1, p.5 (PDF 8) of Anagnostides et al., *Compensation Design*, arXiv:2607.14438 (version of November 3, 2026, sha256 3d305d4d…), in the precise form of Theorem 4.1 (p.17) and
Theorem 5.1 (p.27). Let `λ = max_i c_i/B < 1`. For any monotone submodular value function, in the game
induced by the marginal contribution rule every sequence of strict better responses terminates, a pure
Nash equilibrium exists, and every pure Nash equilibrium `S` satisfies
`OPT ≤ (1 + κ(λ)) v(S)` with `1 + κ(λ) ≤ (2 − λ)/(1 − λ)`; so `OPT/v(S) ≤ (2 − λ)/(1 − λ) = 2 + o_λ(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`. A price-of-anarchy bound `ρ` is written
`OPT ≤ ρ v(S)` for every pure Nash equilibrium `S`, with no ratio. Termination is the absence of an
infinite strict-better-response sequence. Assumption 3.1, `B > 0` and `c ≥ 0` are the standing
assumptions of §3.1. -/
theorem main_result_2 {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) :
(¬ ∃ f : ℕ → Finset (Fin n), ∀ t, IsStrictImprovement v B c (f t) (f (t + 1))) ∧
(∃ S : Finset (Fin n), IsPNE v B c S) ∧
(∀ 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.