AFTD Auto-Formalizing Theoretical Domains

gpa_eq54_false

theoremverifiederratum

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

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
See it in the graphDiscuss this resultChallenge it