AFTD Auto-Formalizing Theoretical Domains

gpa_lhs_upper

lemmaverified

Upper bound on the simplex: u*(σ) - h(σ) ≤ 1 - 1/α + 1/k for every σ ∈ Δ_k, where α ≥ 1 bounds every independent set.

Statement

open Finset in
lemma gpa_lhs_upper {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]
    (a : ℕ) (ha : 1 ≤ a) (hα : ∀ S, gpa_indep G S → S.card ≤ a)
    (σ : Fin k → ℝ) (hσ : σ ∈ gpa_simplex k) :
    gpa_uStar (gpa_adjMat G) σ - gpa_cost σ ≤ 1 - 1 / (a : ℝ) + 1 / (k : ℝ)
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 6
  • 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_costThe convex signal cost of arXiv:2209.01146, Section 5.3: h(σ) = max{‖σ‖_∞ - 1/k, 0} (the norm on Fin k → ℝ is the sup norm).
  • gpa_simplexThe probability simplex Δ_k.
  • gpa_indepAn independent set of the graph G.
  • gpa_uStar_le_indepKey structural lemma: for a nonnegative vector, the coordinates with a positive term of u* form an independent set P, and u*(σ) ≤ Σ_{i ∈…
Used by 1
  • 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) +…

Lean source view module on GitHub

open Finset in/-- Upper bound on the simplex: `u*(σ) - h(σ) ≤ 1 - 1/α + 1/k` for every `σ ∈ Δ_k`, where `α ≥ 1` bounds every independent set. -/lemma gpa_lhs_upper {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]    (a : ℕ) (ha : 1 ≤ a) (hα : ∀ S, gpa_indep G S → S.card ≤ a)    (σ : Fin k → ℝ) (hσ : σ ∈ gpa_simplex k) :    gpa_uStar (gpa_adjMat G) σ - gpa_cost σ ≤ 1 - 1 / (a : ℝ) + 1 / (k : ℝ) := by  obtain ⟨hnn, hsum⟩ := hσ  obtain ⟨P, hP, hle⟩ := gpa_uStar_le_indep G σ hnn  set M := ‖σ‖ with hM  have hcoord : ∀ i, σ i ≤ M := fun i => by    have := norm_le_pi_norm σ i    rw [Real.norm_eq_abs, abs_of_nonneg (hnn i)] at this    exact this  -- Σ_P σ ≤ 1  have hP1 : ∑ i ∈ P, σ i ≤ 1 := by    rw [← hsum]    exact Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ P)      (fun i _ _ => hnn i)  -- Σ_P σ ≤ a M  have hM0 : 0 ≤ M := norm_nonneg σ  have hPa : ∑ i ∈ P, σ i ≤ (a : ℝ) * M := by    have h1 : ∑ i ∈ P, σ i ≤ ∑ _i ∈ P, M := Finset.sum_le_sum (fun i _ => hcoord i)    have h2 : (P.card : ℝ) ≤ a := by exact_mod_cast hα P hP    simp at h1    nlinarith  have hcost : M - 1 / (k : ℝ) ≤ gpa_cost σ := le_max_left _ _  have haR : (1 : ℝ) ≤ a := by exact_mod_cast ha  have hapos : (0 : ℝ) < a := by linarith  by_cases hcase : 1 ≤ (a : ℝ) * M  · -- M ≥ 1/a    have hMa : 1 / (a : ℝ) ≤ M := by      rw [div_le_iff₀ hapos]; linarith    linarith  · replace hcase := not_le.mp hcase    -- u* - h ≤ aM - M + 1/k = (a-1)M + 1/k ≤ (a-1)/a + 1/k    have hkey : ((a : ℝ) - 1) * M ≤ 1 - 1 / (a : ℝ) := by      have hMlt : M < 1 / (a : ℝ) := by        rw [lt_div_iff₀ hapos]; linarith      have : ((a : ℝ) - 1) * M ≤ ((a : ℝ) - 1) * (1 / a) :=        mul_le_mul_of_nonneg_left hMlt.le (by linarith)      have e : ((a : ℝ) - 1) * (1 / a) = 1 - 1 / (a : ℝ) := by field_simp      linarith    nlinarith
See it in the graphDiscuss this resultChallenge it