AFTD Auto-Formalizing Theoretical Domains

gpa_uStar_le_indep

lemmaverified

Key structural lemma: for a nonnegative vector, the coordinates with a positive term of u* form an independent set P, and u*(σ) ≤ Σ_{i ∈ P} σ_i.

Statement

open Finset in
lemma gpa_uStar_le_indep {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]
    (σ : Fin k → ℝ) (hσ : ∀ i, 0 ≤ σ i) :
    ∃ P : Finset (Fin k), gpa_indep G P ∧
      gpa_uStar (gpa_adjMat G) σ ≤ ∑ i ∈ P, σ i
Source
step towards gpa_eq54_false / gpa_eq54_fails_of_indep (Generalized Principal-Agency: Contracts, Information, Games and Beyond, WINE 2024 (arXiv:2209.01146v2), Sec. 5.3, Eq. (5.4))
Verified
06 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_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_indepAn independent set of the graph G.
  • gpa_nbr_nonnegNeighbour sums are nonnegative for nonnegative vectors.
  • gpa_nbr_geA single neighbour's coordinate is bounded by the neighbour sum.
Used by 2
  • gpa_lhs_upperUpper bound on the simplex: u*(σ) - h(σ) ≤ 1 - 1/α + 1/k for every σ ∈ Δ_k, where α ≥ 1 bounds every independent set.
  • gpa_rhs_upperUpper bound on the cube: u*(x) ≤ α(G) for every x ∈ [0,1]^k.

Lean source view module on GitHub

open Finset in/-- Key structural lemma: for a nonnegative vector, the coordinates with a positive term of `u*` form an independent set `P`, and `u*(σ) ≤ Σ_{i ∈ P} σ_i`. -/lemma gpa_uStar_le_indep {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]    (σ : Fin k → ℝ) (hσ : ∀ i, 0 ≤ σ i) :    ∃ P : Finset (Fin k), gpa_indep G P ∧      gpa_uStar (gpa_adjMat G) σ ≤ ∑ i ∈ P, σ i := by  classical  let P : Finset (Fin k) := univ.filter (fun i => 0 < σ i - ∑ j, gpa_adjMat G i j * σ j)  refine ⟨P, ?_, ?_⟩  · intro i hi j hj hadj    simp only [P, Finset.mem_filter, Finset.mem_univ, true_and] at hi hj    have a1 := gpa_nbr_ge G σ hσ i j hadj    have a2 := gpa_nbr_ge G σ hσ j i hadj.symm    linarith  · unfold gpa_uStar    rw [← Finset.sum_filter_add_sum_filter_not univ      (fun i => 0 < σ i - ∑ j, gpa_adjMat G i j * σ j)]    have h2 : ∑ i ∈ univ.filter (fun i => ¬ (0 < σ i - ∑ j, gpa_adjMat G i j * σ j)),        max (σ i - ∑ j, gpa_adjMat G i j * σ j) 0 = 0 := by      apply Finset.sum_eq_zero      intro i hi      simp only [Finset.mem_filter, Finset.mem_univ, true_and, not_lt] at hi      exact max_eq_right hi    rw [h2, add_zero]    apply Finset.sum_le_sum    intro i hi    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hi    rw [max_eq_left hi.le]    have := gpa_nbr_nonneg G σ hσ i    linarith
See it in the graphDiscuss this resultChallenge it