condorcet_optimized_all_triple_policy_lower_bound
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
- condorcet_stationary_action_dual_acyclic_massFor nonnegative occupations of arbitrary finite families of rooted finite-set actions, let each vertex weight equal the sum of occupations…
- condorcet_minimal_private_averaging_obstructionThere exist an irreflexive directed relation R on eight vertices, nonempty complete families F(a) of private three-element sets at each…
- Used by 1
- condorcet_stationary_policy_strict_unrestricted_gapFor the existing integer weights [1,1,1,1,4,1,3,4] of total16 on the explicit eight-vertex relation, every induced acyclic subset has at…
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.
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.
3 * condorcet_policy_gap_all_potential a := by decide
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.
decideThe 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.
uses
measure,condorcet_policy_gap_all_order_checkrefine (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
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.
uses
condorcet_policy_gap_all_dual_checkhave 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
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).
uses
condorcet_stationary_action_dual_acyclic_mass,Nat.cast_nonnegobtain ⟨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
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.
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
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.
uses
condorcet_policy_gap_all_acyclicrw [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.
- The verification of the dual inequality and the acyclicity order check relies on exhaustive computational checks by `decide` on finite structures (8 vertices, subsets of size 3, and 6 candidate sets).
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩