AFTD Auto-Formalizing Theoretical Domains

gpa_lhs_isGreatest

theoremverifiedoriginal

Exact 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) + 1/k.

Statement

open Finset in
theorem gpa_lhs_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)
    (hne : 1 ≤ I.card) (hk : I.card ≤ k) :
    IsGreatest (gpa_lhsSet (gpa_adjMat G)) (1 - 1 / (I.card : ℝ) + 1 / (k : ℝ))
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_lhsSetThe set of values u*(σ) - h(σ) over the simplex (left side of Eq. (5.4)).
  • gpa_indepAn independent set of the graph G.
  • gpa_lhs_upperUpper bound on the simplex: u*(σ) - h(σ) ≤ 1 - 1/α + 1/k for every σ ∈ Δ_k, where α ≥ 1 bounds every 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).
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 left side of Eq. (5.4) of arXiv:2209.01146 on the independent-set instances: `max_{σ ∈ Δ_k} u*(σ) - h(σ) = 1 - 1/α(G) + 1/k`. -/theorem gpa_lhs_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)    (hne : 1 ≤ I.card) (hk : I.card ≤ k) :    IsGreatest (gpa_lhsSet (gpa_adjMat G)) (1 - 1 / (I.card : ℝ) + 1 / (k : ℝ)) := by  refine ⟨?_, ?_⟩  · obtain ⟨σ, hσ, hval⟩ := gpa_lhs_attain G I hI hne hk    exact ⟨σ, hσ, hval⟩  · rintro v ⟨σ, hσ, rfl⟩    exact gpa_lhs_upper G I.card hne hmax σ hσ
See it in the graphDiscuss this resultChallenge it