AFTD Auto-Formalizing Theoretical Domains

gpa_rhs_isGreatest

theoremverifiedoriginal

Exact value of the right side of Eq. (5.4) of arXiv:2209.01146 (before the factor 1/k): max_{x ∈ [0,1]^k} u*(x) = α(G).

Statement

open Finset in
theorem gpa_rhs_isGreatest {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]
    (I : Finset (Fin k)) (hI : gpa_indep G I) (hmax : ∀ S, gpa_indep G S → S.card ≤ I.card) :
    IsGreatest (gpa_rhsSet (gpa_adjMat G)) (I.card : ℝ)
Related work
operator (Claude), 2026-10-05: counterexample to Eq. (5.4) of 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); for 0/1 adjacency matrices of a graph with independence number alpha, the simplex side equals 1 - 1/alpha + 1/k and the cube side equals alpha/k; smallest witness the 3-vertex path (5/6 vs 2/3); found by a search agent, checked by the Lean kernel
Verified
05 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • gpa_adjMatThe 0/1 matrix e of arXiv:2209.01146, Section 5.3 (taken from the maximum-independent-set instances of the cited convex-maximisation…
  • gpa_rhsSetThe set of values u*(x) over the cube (right side of Eq. (5.4), before dividing by k).
  • gpa_indepAn independent set of the graph G.
  • gpa_rhs_upperUpper bound on the cube: u*(x) ≤ α(G) for every x ∈ [0,1]^k.
  • gpa_rhs_attainThe value α(G) is attained on the cube, at the indicator vector of a maximum independent set.
Used by 2
  • 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

open Finset in/-- Exact value of the right side of Eq. (5.4) of arXiv:2209.01146 (before the factor `1/k`): `max_{x ∈ [0,1]^k} u*(x) = α(G)`. -/theorem gpa_rhs_isGreatest {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]    (I : Finset (Fin k)) (hI : gpa_indep G I) (hmax : ∀ S, gpa_indep G S → S.card ≤ I.card) :    IsGreatest (gpa_rhsSet (gpa_adjMat G)) (I.card : ℝ) := by  refine ⟨?_, ?_⟩  · obtain ⟨hmem, hval⟩ := gpa_rhs_attain G I hI    exact ⟨_, hmem, hval⟩  · rintro v ⟨x, hx, rfl⟩    exact gpa_rhs_upper G I.card hmax x hx
See it in the graphDiscuss this resultChallenge it