AFTD Auto-Formalizing Theoretical Domains

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
See it in the graphDiscuss this resultChallenge it