AFTD Auto-Formalizing Theoretical Domains

condorcet_optimized_all_triple_policy_lower_bound

theoremverified

On the same explicit eight-vertex relation, allow every three-element subset of each root's out-neighborhood, including nonprivate triples. Every nonnegative occupation scheme satisfying triple stationarity has an induced acyclic subset of at least32/101 of its total vertex weight, in homogeneous form. This remains strictly larger than the available unrestricted weight bound5/16 but below one half; it excludes equality of these optimization problems, not strict-half feasibility.

Statement

theorem condorcet_optimized_all_triple_policy_lower_bound
    (x : Fin 8 → Finset (Fin 8) → ℝ) (w : Fin 8 → ℝ)
    (hx : ∀ a, ∀ J ∈ condorcet_policy_gap_all_family a, 0 ≤ x a J)
    (hw : ∀ a, w a = ∑ J ∈ condorcet_policy_gap_all_family a, x a J)
    (hflow : ∀ b, 3 * w b = ∑ a, ∑ J ∈ condorcet_policy_gap_all_family a,
      if b ∈ J then x a J else 0) :
    ∃ A : Finset (Fin 8),
      WellFounded (fun a b : {a : Fin 8 // a ∈ A} =>
        condorcet_minimal_private_relation a.val b.val) ∧
      32 * (∑ a, w a) ≤ 101 * (∑ a ∈ A, w a)
Source
IN-372 supporting method diagnostic for OP-19. Integer audit experiment9221 and exploratory LP9219. Standard finite LP weak duality; no novelty or research advance is claimed. The original strict election statement remains unchanged.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

We establish that any nonnegative occupation scheme satisfying triple stationarity on this eight-vertex relation contains an induced acyclic subset carrying at least 32/101 of the total vertex weight. The proof uses linear programming duality via condorcet_stationary_action_dual_acyclic_mass, certified by explicit vertex potentials, six candidate sets, and integer coefficients summing to 101. The validity of the dual inequality and the acyclicity of each candidate set (via strictly increasing rankings) are verified by finite computation.

  1. The dual inequality holds over the integers for every vertex and admissible triple automation

    For every vertex a among the 8 vertices and every 3-element subset J of its out-neighborhood, the integer potential inequality holds: 32 plus the potential sum on J is at most the sum of coefficients covering a plus three times the potential of a. Because all structures are finite, this is verified exhaustively by decide.

    line 20

            3 * condorcet_policy_gap_all_potential a := by decide
  2. The assigned rankings strictly increase along every edge in each candidate set automation

    For each of the six candidate sets, whenever there is a directed edge between two vertices in the set, the ranking assigned to the source is strictly less than the ranking assigned to the target. This finite combinatorial check is discharged by decide.

    line 26

      decide
  3. The relation induced on each candidate set is well-founded, and therefore acyclic

    We pull back the well-founded order on ℕ along the integer ranking function using measure. By condorcet_policy_gap_all_order_check, every step of the induced relation strictly increases this rank, so the relation is well-founded.

    lines 31–34

    uses measure, condorcet_policy_gap_all_order_check

      refine (measure (fun a : {a : Fin 8 // a ∈ condorcet_policy_gap_all_sets j} =>
        condorcet_policy_gap_all_orders j a.val)).wf.mono ?_
      intro a b hab
      exact condorcet_policy_gap_all_order_check j a b a.property b.property hab
  4. The dual inequality holds over the real numbers for all vertices and triples

    Given a vertex a and an admissible triple J, we cast the pre-verified integer dual inequality condorcet_policy_gap_all_dual_check into the real numbers using exact_mod_cast.

    lines 46–52

    uses condorcet_policy_gap_all_dual_check

      have hdual : ∀ a : Fin 8, ∀ J ∈ condorcet_policy_gap_all_family a,
          (32 : ℝ) + (∑ b ∈ J, (condorcet_policy_gap_all_potential b : ℝ)) ≤
            (∑ j : Fin 6, if a ∈ condorcet_policy_gap_all_sets j then
              (condorcet_policy_gap_all_coeff j : ℝ) else 0) +
            3 * (condorcet_policy_gap_all_potential a : ℝ) := by
        intro a J hJ
        exact_mod_cast condorcet_policy_gap_all_dual_check a J hJ
  5. There exists a candidate set satisfying the duality weight bound automation

    We invoke the stationary flow LP duality lemma condorcet_stationary_action_dual_acyclic_mass with parameters m = 8 vertices, k = 6 candidate sets (verifying 0 < 6 with decide), the policy x, weight w, vertex potentials, candidate sets, coefficients, and constant c = 32. Nonnegativity of the coefficients is supplied by Nat.cast_nonneg. This yields an index j such that 32 ∑ w(a) ≤ (∑ d_i) ∑_{a ∈ A_j} w(a).

    lines 53–58

    uses condorcet_stationary_action_dual_acyclic_mass, Nat.cast_nonneg

      obtain ⟨j,hj⟩ := condorcet_stationary_action_dual_acyclic_mass 8 6 (by decide)
        condorcet_policy_gap_all_family x w
        (fun a => (condorcet_policy_gap_all_potential a : ℝ))
        condorcet_policy_gap_all_sets
        (fun j => (condorcet_policy_gap_all_coeff j : ℝ)) 32
        (fun j => Nat.cast_nonneg _) hx hw hflow hdual
  6. The sum of the dual coefficients equals 101 over the reals automation

    The integer coefficients [23, 12, 12, 12, 15, 27] sum to 101, verified computationally by decide and cast to ℝ by exact_mod_cast.

    lines 59–61

      have hsumN : (∑ j : Fin 6, condorcet_policy_gap_all_coeff j) = 101 := by decide
      have hsumR : (∑ j : Fin 6, (condorcet_policy_gap_all_coeff j : ℝ)) = 101 := by
        exact_mod_cast hsumN
  7. The chosen candidate set is acyclic and carries at least 32/101 of the total weight

    Substituting the coefficient sum of 101 into the duality inequality yields 32 ∑ w(a) ≤ 101 ∑_{a ∈ A_j} w(a). By condorcet_policy_gap_all_acyclic, the candidate set A_j is acyclic, providing the desired witness A.

    lines 62–63

    uses condorcet_policy_gap_all_acyclic

      rw [hsumR] at hj
      exact ⟨_, condorcet_policy_gap_all_acyclic j, hj⟩
condorcet_policy_gap_all_dual_check
A finite verification by exhaustive computation that for every vertex a and every triple J in its out-neighborhood family, 32 plus the sum of potentials on J is at most the sum of coefficients covering a plus three times the potential of a.
condorcet_policy_gap_all_order_check
A finite verification by exhaustive computation that for each candidate set, any edge of the relation strictly increases the integer rank assigned to the vertices.
measure
Constructs a well-founded relation on a type by pulling back the standard ordering on ℕ along a given ranking function.
condorcet_stationary_action_dual_acyclic_mass
General linear programming duality lemma for stationary triple flows: if a nonnegative policy satisfies stationarity and a dual potential inequality with constant c and candidate sets weighted by coefficients d, then at least one candidate set carries at least a c / (∑ d) fraction of the total vertex weight.
Nat.cast_nonneg
The coercion of any natural number into an ordered semiring is nonnegative.
condorcet_policy_gap_all_acyclic
The induced subrelation on each of the six candidate sets is well-founded, hence acyclic, as certified by a strictly increasing integer ranking.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

open Finsetopen scoped BigOperatorsset_option maxHeartbeats 20000000set_option maxRecDepth 20000def condorcet_policy_gap_all_family (a : Fin 8) : Finset (Finset (Fin 8)) :=  (univ.powersetCard 3).filter (fun J => ∀ b ∈ J, condorcet_minimal_private_relation a b)def condorcet_policy_gap_all_sets : Fin 6 → Finset (Fin 8) :=  ![{3,4},{0,1,2,3,5},{1,2,6},{1,5,6},{2,5,6},{0,7}]def condorcet_policy_gap_all_coeff : Fin 6 → ℕ := ![23,12,12,12,15,27]def condorcet_policy_gap_all_potential : Fin 8 → ℕ := ![0,0,0,0,4,0,0,3]def condorcet_policy_gap_all_orders : Fin 6 → Fin 8 → ℕ :=  ![![0,0,0,1,0,0,0,0], ![4,3,2,0,0,1,0,0], ![0,1,0,0,0,0,2,0],    ![0,0,0,0,0,2,1,0], ![0,0,2,0,0,1,0,0], ![0,0,0,0,0,0,0,1]]theorem condorcet_policy_gap_all_dual_check : ∀ a : Fin 8,    ∀ J ∈ condorcet_policy_gap_all_family a,      32 + (∑ b ∈ J, condorcet_policy_gap_all_potential b) ≤        (∑ j : Fin 6, if a ∈ condorcet_policy_gap_all_sets j then          condorcet_policy_gap_all_coeff j else 0) +        3 * condorcet_policy_gap_all_potential a := by decidetheorem condorcet_policy_gap_all_order_check : ∀ j : Fin 6, ∀ a b : Fin 8,    a ∈ condorcet_policy_gap_all_sets j → b ∈ condorcet_policy_gap_all_sets j →    condorcet_minimal_private_relation a b →    condorcet_policy_gap_all_orders j a < condorcet_policy_gap_all_orders j b := by  decidetheorem condorcet_policy_gap_all_acyclic (j : Fin 6) :    WellFounded (fun a b : {a : Fin 8 // a ∈ condorcet_policy_gap_all_sets j} =>      condorcet_minimal_private_relation a.val b.val) := by  refine (measure (fun a : {a : Fin 8 // a ∈ condorcet_policy_gap_all_sets j} =>    condorcet_policy_gap_all_orders j a.val)).wf.mono ?_  intro a b hab  exact condorcet_policy_gap_all_order_check j a b a.property b.property habtheorem condorcet_optimized_all_triple_policy_lower_bound    (x : Fin 8 → Finset (Fin 8) → ℝ) (w : Fin 8 → ℝ)    (hx : ∀ a, ∀ J ∈ condorcet_policy_gap_all_family a, 0 ≤ x a J)    (hw : ∀ a, w a = ∑ J ∈ condorcet_policy_gap_all_family a, x a J)    (hflow : ∀ b, 3 * w b = ∑ a, ∑ J ∈ condorcet_policy_gap_all_family a,      if b ∈ J then x a J else 0) :    ∃ A : Finset (Fin 8),      WellFounded (fun a b : {a : Fin 8 // a ∈ A} =>        condorcet_minimal_private_relation a.val b.val) ∧      32 * (∑ a, w a) ≤ 101 * (∑ a ∈ A, w a) := by  have hdual : ∀ a : Fin 8, ∀ J ∈ condorcet_policy_gap_all_family a,      (32 : ℝ) + (∑ b ∈ J, (condorcet_policy_gap_all_potential b : ℝ)) ≤        (∑ j : Fin 6, if a ∈ condorcet_policy_gap_all_sets j then          (condorcet_policy_gap_all_coeff j : ℝ) else 0) +        3 * (condorcet_policy_gap_all_potential a : ℝ) := by    intro a J hJ    exact_mod_cast condorcet_policy_gap_all_dual_check a J hJ  obtain ⟨j,hj⟩ := condorcet_stationary_action_dual_acyclic_mass 8 6 (by decide)    condorcet_policy_gap_all_family x w    (fun a => (condorcet_policy_gap_all_potential a : ℝ))    condorcet_policy_gap_all_sets    (fun j => (condorcet_policy_gap_all_coeff j : ℝ)) 32    (fun j => Nat.cast_nonneg _) hx hw hflow hdual  have hsumN : (∑ j : Fin 6, condorcet_policy_gap_all_coeff j) = 101 := by decide  have hsumR : (∑ j : Fin 6, (condorcet_policy_gap_all_coeff j : ℝ)) = 101 := by    exact_mod_cast hsumN  rw [hsumR] at hj  exact ⟨_, condorcet_policy_gap_all_acyclic j, hj⟩
See it in the graphDiscuss this resultChallenge it