AFTD Auto-Formalizing Theoretical Domains

gpa_uStar

def

The 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.

Statement

open Finset in
noncomputable def gpa_uStar {k : ℕ} (e : Fin k → Fin 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 8
  • gpa_rhs_attainThe value α(G) is attained on the cube, at the indicator vector of a maximum independent set.
  • 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)).
  • gpa_rhs_upperUpper bound on the cube: u*(x) ≤ α(G) for every x ∈ [0,1]^k.
  • gpa_uStar_le_indepKey structural lemma: for a nonnegative vector, the coordinates with a positive term of u* form an independent set P, and u*(σ) ≤ Σ_{i ∈…
  • gpa_rhsSetThe set of values u*(x) over the cube (right side of Eq. (5.4), before dividing by k).
  • gpa_cube_max_le_one_falseThe auxiliary claim max_{x ∈ [0,1]^k} u*(x) ≤ 1 used in the proof of Eq. (5.4) of arXiv:2209.01146 is false: on the path with three…

Lean source view module on GitHub

open Finset in
/-- The 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`. -/
noncomputable def gpa_uStar {k : ℕ} (e : Fin k → Fin k → ℝ) (σ : Fin k → ℝ) : ℝ :=
  ∑ i, max (σ i - ∑ j, e i j * σ j) 0
See it in the graphDiscuss this resultChallenge it