AFTD Auto-Formalizing Theoretical Domains

gpa_lhsSet

def

The set of values u*(σ) - h(σ) over the simplex (left side of Eq. (5.4)).

Statement

def gpa_lhsSet {k : ℕ} (e : Fin k → Fin k → ℝ) : Set ℝ
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
Built on 3
  • gpa_uStarThe principal's utility of arXiv:2209.01146, Section 5.3: u*(σ) = Σ_i max{σ_i - Σ_j e_{ij} σ_j, 0} for a 0/1 matrix e.
  • gpa_costThe convex signal cost of arXiv:2209.01146, Section 5.3: h(σ) = max{‖σ‖_∞ - 1/k, 0} (the norm on Fin k → ℝ is the sup norm).
  • gpa_simplexThe probability simplex Δ_k.
Used by 3
  • gpa_lhs_isGreatestExact value of the left side of Eq. (5.4) of arXiv:2209.01146 on the independent-set instances: max_{σ ∈ Δ_k} u*(σ) - h(σ) = 1 - 1/α(G) +…
  • gpa_eq54_falseEq. (5.4) in the proof of Theorem 5 (hardness of costly information acquisition) of arXiv:2209.01146 is false: it is not true that for…
  • gpa_eq54_fails_of_indepEq. (5.4) of arXiv:2209.01146 (max_{Δ_k} (u* - h) = (1/k) max_{[0,1]^k} u*) fails on every graph whose independence number α satisfies 2 ≤…

Lean source view module on GitHub

/-- The set of values `u*(σ) - h(σ)` over the simplex (left side of Eq. (5.4)). -/
def gpa_lhsSet {k : ℕ} (e : Fin k → Fin k → ℝ) : Set ℝ :=
  (fun σ => gpa_uStar e σ - gpa_cost σ) '' gpa_simplex k
See it in the graphDiscuss this resultChallenge it