§5.1 —
ProvedCompDesign.kappa_lecompensation-designp2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchypure-nash-equilibriumsubmodular-functions
Let be the cost concentration term (20). For ,
This is the "immediate upper bound" stated after (20); it is what turns the constant of Theorem 5.1 into .
Formalization Note λ is written l.
Differences from the source:
- reading: κ(λ) ≤ 1/(1−λ), with λ = max_i c_i/B ≪ 1 (no range printed) → hypotheses 0 ≤ l and l < 1; reason: the right-hand side is undefined at λ = 1 and negative beyond, and κ(λ) is infinite for λ ≥ 1; λ ≥ 0 because costs are nonnegative, and Main Result 2 assumes λ < 1
Preamble
import Mathlib import Definitions.Def_CompDesign_kappa
Formal statement
namespace CompDesign /-- The upper bound `κ(λ) ≤ 1/(1 − λ)` stated after (20), §5.1, p.26 (PDF 29) of Anagnostides et al., *Compensation Design*, arXiv:2607.14438 (version of November 3, 2026, sha256 3d305d4d…). **Formalization Note.** `λ` is a Lean keyword and is written `l`. The hypothesis `0 ≤ l < 1` is the range where (20) is finite (Main Result 2 assumes `λ < 1`). -/ theorem kappa_le (l : ℝ) (hl0 : 0 ≤ l) (hl1 : l < 1) : kappa l ≤ 1 / (1 - l) := 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…), §5.1, after eq. (20), p.26 (PDF 29)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.