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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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σ