gpa_eq54_false
Eq. (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 every 0/1 matrix e the maximum of u*(σ) - h(σ) over the simplex equals (1/k) times the maximum of u* over the cube. On the path with three vertices the left side is 5/6 and the right side is 2/3.
Statement
open Finset in theorem gpa_eq54_false : ¬ (∀ (k : ℕ) (e : Fin k → Fin k → ℝ), (∀ i j, e i j = 0 ∨ e i j = 1) → ∀ (L R : ℝ), IsGreatest (gpa_lhsSet e) L → IsGreatest (gpa_rhsSet e) R → L = R / (k : ℝ))
- Corrects
- Generalized Principal-Agency: Contracts, Information, Games and Beyond, WINE 2024 (arXiv:2209.01146v2), Section 5.3, Eq. (5.4) in the proof of Theorem 5 (max over the simplex of u* - h equals (1/k) max over the cube of u*): false; on the 3-vertex path the two sides are 5/6 and 2/3
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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_rhsSetThe set of values u*(x) over the cube (right side of Eq. (5.4), before dividing by k).
- gpa_adjMat_zero_oneThe adjacency matrix is a 0/1 matrix, as required in Section 5.3 of arXiv:2209.01146.
- 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_rhs_isGreatestExact 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).
- 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 ≤…
- gpa_path3The path 0 - 2 - 1 on three vertices.
- gpa_path3_indepIn the path 0 - 2 - 1, {0, 1} is a maximum independent set.
Read back from the Lean
The theorem asserts the negation of the following statement:
For every natural number $k$, every matrix $e : \text{Fin } k \to \text{Fin } k \to \mathbb{R}$ whose entries are all in $\{0, 1\}$ (i.e., $\forall i, j, e(i, j) = 0 \lor e(i, j) = 1$), and all real numbers $L$ and $R$:
if $L$ is the greatest element of gpa_lhsSet e and $R$ is the greatest element of gpa_rhsSet e, then $L = R / k$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
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/-- Eq. (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 every 0/1 matrix `e` the maximum of `u*(σ) - h(σ)` over the simplex equals `(1/k)` times the maximum of `u*` over the cube. On the path with three vertices the left side is `5/6` and the right side is `2/3`. -/theorem gpa_eq54_false : ¬ (∀ (k : ℕ) (e : Fin k → Fin k → ℝ), (∀ i j, e i j = 0 ∨ e i j = 1) → ∀ (L R : ℝ), IsGreatest (gpa_lhsSet e) L → IsGreatest (gpa_rhsSet e) R → L = R / (k : ℝ)) := by intro h obtain ⟨hI, hmax⟩ := gpa_path3_indep have hc : ({0, 1} : Finset (Fin 3)).card = 2 := by decide have hL := gpa_lhs_isGreatest gpa_path3 {0, 1} hI hmax (by rw [hc]; norm_num) (by rw [hc]; norm_num) have hR := gpa_rhs_isGreatest gpa_path3 {0, 1} hI hmax have hlt := gpa_eq54_fails_of_indep gpa_path3 {0, 1} hI hmax (by rw [hc]) (by rw [hc]; norm_num) _ _ hL hR have := h 3 (gpa_adjMat gpa_path3) (gpa_adjMat_zero_one gpa_path3) _ _ hL hR linarith