gpa_cost
def
The convex signal cost of arXiv:2209.01146, Section 5.3: h(σ) = max{‖σ‖_∞ - 1/k, 0} (the norm on Fin k → ℝ is the sup norm).
Statement
noncomputable def gpa_cost {k : ℕ} (σ : Fin k → ℝ) : ℝ
- Defined in
- Generalized Principal-Agency: Contracts, Information, Games and Beyond, WINE 2024 (arXiv:2209.01146v2), Section 5.3 (proof of Theorem 5) and Appendix 13.2, Eq. (5.4); formalized by the operator (Claude), 2026-10-05
- Verified
- 05 Oct 2026
- Axioms
- none listed
- Used by 3
- gpa_lhs_attainThe bound 1 - 1/α + 1/k is attained on the simplex, by the uniform distribution on a maximum independent set I (1 ≤ |I| ≤ k).
- gpa_lhs_upperUpper bound on the simplex: u*(σ) - h(σ) ≤ 1 - 1/α + 1/k for every σ ∈ Δ_k, where α ≥ 1 bounds every independent set.
- gpa_lhsSetThe set of values u*(σ) - h(σ) over the simplex (left side of Eq. (5.4)).
Lean source view module on GitHub
/-- The convex signal cost of arXiv:2209.01146, Section 5.3: `h(σ) = max{‖σ‖_∞ - 1/k, 0}` (the norm on `Fin k → ℝ` is the sup norm). -/ noncomputable def gpa_cost {k : ℕ} (σ : Fin k → ℝ) : ℝ := max (‖σ‖ - 1 / (k : ℝ)) 0