AFTD Auto-Formalizing Theoretical Domains

gpa_cube_max_le_one_false

theoremverifiederratum

The auxiliary claim max_{x ∈ [0,1]^k} u*(x) ≤ 1 used in the proof of Eq. (5.4) of arXiv:2209.01146 is false: on the path with three vertices the maximum is 2.

Statement

open Finset in
theorem gpa_cube_max_le_one_false :
    ¬ (∀ (k : ℕ) (e : Fin k → Fin k → ℝ), (∀ i j, e i j = 0 ∨ e i j = 1) →
        ∀ x : Fin k → ℝ, x ∈ gpa_cube k → gpa_uStar e x ≤ 1)
Corrects
Generalized Principal-Agency: Contracts, Information, Games and Beyond, WINE 2024 (arXiv:2209.01146v2), Section 5.3 / Appendix 13.2: the auxiliary claim max over [0,1]^k of u* <= 1 used to derive Eq. (5.4) is false (value 2 on the 3-vertex path)
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • 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_uStarThe principal's utility of arXiv:2209.01146, Section 5.3: u*(σ) = Σ_i max{σ_i - Σ_j e_{ij} σ_j, 0} for a 0/1 matrix e.
  • gpa_cubeThe unit cube [0,1]^k.
  • gpa_adjMat_zero_oneThe adjacency matrix is a 0/1 matrix, as required in Section 5.3 of arXiv:2209.01146.
  • gpa_rhs_attainThe value α(G) is attained on the cube, at the indicator vector of a maximum independent set.
  • 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

It is not the case that for every natural number $k$, every matrix $e : \mathrm{Fin}\ k \to \mathrm{Fin}\ k \to \mathbb{R}$ whose entries are all in $\{0, 1\}$, and every vector $x : \mathrm{Fin}\ k \to \mathbb{R}$ in gpa_cube k, gpa_uStar e x ≤ 1.

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/-- The auxiliary claim `max_{x ∈ [0,1]^k} u*(x) ≤ 1` used in the proof of Eq. (5.4) of arXiv:2209.01146 is false: on the path with three vertices the maximum is `2`. -/theorem gpa_cube_max_le_one_false :    ¬ (∀ (k : ℕ) (e : Fin k → Fin k → ℝ), (∀ i j, e i j = 0 ∨ e i j = 1) →        ∀ x : Fin k → ℝ, x ∈ gpa_cube k → gpa_uStar e x ≤ 1) := by  intro h  obtain ⟨hI, _⟩ := gpa_path3_indep  obtain ⟨hmem, hval⟩ := gpa_rhs_attain gpa_path3 {0, 1} hI  have := h 3 (gpa_adjMat gpa_path3) (gpa_adjMat_zero_one gpa_path3) _ hmem  rw [hval] at this  have hc : ({0, 1} : Finset (Fin 3)).card = 2 := by decide  rw [hc] at this  norm_num at this
See it in the graphDiscuss this resultChallenge it