condorcet_stable_fractional_tight_cover_obstruction
There are twenty three-element activity sets on six vertices, covering each vertex ten times, and injective local rankings. A stable fractional matching exists, but every such matching is exactly the uniform weight1/3. For every stable fractional matching and every set J of at most three vertices, some tight activity set is disjoint from J. The rank-compatible relation explicitly fails S3. Hence changing the stable fractional solution cannot guarantee three-vertex coverage of all tight sets for an arbitrary supplied half-cover family. The statement does not concern the family of all induced acyclic sets.
Statement
theorem condorcet_stable_fractional_tight_cover_obstruction : ∃ (U : Fin 20 → Finset (Fin 6)) (p : Fin 20 → Fin 6 → ℕ), (∀ v, (U v).card = 3) ∧ (∀ a, (univ.filter fun v => a ∈ U v).card = 10) ∧ (∀ v, Function.Injective (p v)) ∧ (∃ w : Fin 6 → ℝ, (∀ a, 0 ≤ w a) ∧ (∀ v, (∑ a ∈ U v, w a) ≤ 1) ∧ ∀ a, ∃ v, a ∈ U v ∧ (∑ b ∈ U v, w b) = 1 ∧ ∀ b ∈ U v, 0 < w b → p v b ≤ p v a) ∧ (∀ w : Fin 6 → ℝ, (∀ a, 0 ≤ w a) → (∀ v, (∑ a ∈ U v, w a) ≤ 1) → (∀ a, ∃ v, a ∈ U v ∧ (∑ b ∈ U v, w b) = 1 ∧ ∀ b ∈ U v, 0 < w b → p v b ≤ p v a) → ∀ a, w a = 1 / 3) ∧ (∀ w : Fin 6 → ℝ, (∀ a, 0 ≤ w a) → (∀ v, (∑ a ∈ U v, w a) ≤ 1) → (∀ a, ∃ v, a ∈ U v ∧ (∑ b ∈ U v, w b) = 1 ∧ ∀ b ∈ U v, 0 < w b → p v b ≤ p v a) → ∀ J : Finset (Fin 6), J.card ≤ 3 → ∃ v, (∑ a ∈ U v, w a) = 1 ∧ ∀ a ∈ J, a ∉ U v) ∧ ¬(∀ J : Finset (Fin 6), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, condorcet_cover_rank_relation U p a b)
- Source
- IN-391, OP-19 campaign session10, 2026-10-30. Method diagnostic for the stable-fractional-matching route suggested by On a lemma of Scarf, Theorem2.1, https://doi.org/10.1016/S0095-8956%2802%2900028-X. Experiment9879 supplies the finite orders; the uniqueness and all-solutions rounding obstruction are proved here in Lean. This is not a Condorcet counterexample and no election bound or research novelty is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- condorcet_cover_rank_relationThe loopless rank-compatible relation: an arrow a to b is permitted precisely when a differs from b and a has a strictly smaller…
The proof, explained
The theorem establishes an obstruction to guaranteeing three-vertex coverage of all tight sets by constructing a 6-vertex hypergraph consisting of all 20 triples, each vertex having degree 10, with injective local rankings. An auxiliary theorem first proves that any stable fractional matching is uniquely the uniform weight 1/3: stability and set exchange force weights to be non-increasing along the 6-cycle, pinching all weights to equality, while saturated triples then fix each weight to 1/3. Under this unique matching every triple is tight, so every subset of at most three vertices is disjoint from some tight triple because the complement has size at least three. Finally, an exhaustive check confirms that the induced rank-compatible relation fails property S3, meaning some three-element subset admits no external Condorcet dominator.
Ranks strictly increase along the cyclic successor within any triple containing consecutive elements, and replacing an element of any triple with an absent vertex always produces another triple in the family. automation
Two combinatorial facts about the 20 triples and their rankings are verified by finite exhaustive evaluation (`decide`): first, `hcyc` establishes that whenever a vertex a and its cyclic successor a + 1 belong to the same triple U v, the rank strictly increases (condorcet_stable_gap_rank v a < condorcet_stable_gap_rank v (a + 1)); second, `hreplace` establishes that swapping any element of a triple with an element outside that triple yields another triple in the 20-element family.
have hcyc : ∀ a v, a ∈ condorcet_stable_gap_sets v → condorcet_stable_gap_next a ∈ condorcet_stable_gap_sets v → condorcet_stable_gap_rank v a < condorcet_stable_gap_rank v (condorcet_stable_gap_next a) := by decide have hreplace : ∀ (v : Fin 20) (a b : Fin 6), a ∈ condorcet_stable_gap_sets v → b ∉ condorcet_stable_gap_sets v → ∃ z, condorcet_stable_gap_sets z = insert b ((condorcet_stable_gap_sets v).erase a) := by decide
The vertex weights of any stable fractional matching are non-increasing along the cyclic permutation: w (a + 1) ≤ w a for all a.
For each vertex a, if w (a + 1) ≤ 0, then w (a + 1) ≤ w a by non-negativity of weights (`hw`, using `le_of_not_gt`). Otherwise, w (a + 1) > 0. By the stability hypothesis for a, there is a triple U v containing a with weight sum 1 where every positive-weight element has rank at most that of a. If a + 1 were in U v, its rank would be at most that of a, contradicting `hcyc` via `not_lt_of_ge`; hence a + 1 ∉ U v. Swapping a for a + 1 gives another triple U z (`hreplace`), whose weight sum is at most 1 by capacity (`hcap z`). Decomposing this sum with `sum_insert` and `mem_of_mem_erase`, and comparing it to the saturated sum for U v using `sum_erase_add`, linear arithmetic (`linarith`) yields w (a + 1) ≤ w a.
uses
not_lt_of_ge,sum_insert,mem_of_mem_erase,sum_erase_add,le_of_not_gthave hmono : ∀ a, w (condorcet_stable_gap_next a) ≤ w a := by intro a by_cases hpos : 0 < w (condorcet_stable_gap_next a) · obtain ⟨v,hav,hload,horder⟩ := hstable a have hb : condorcet_stable_gap_next a ∉ condorcet_stable_gap_sets v := by intro hb exact (not_lt_of_ge (horder _ hb hpos)) (hcyc a v hav hb) obtain ⟨z,hz⟩ := hreplace v a (condorcet_stable_gap_next a) hav hb have hc := hcap z rw [hz, sum_insert (fun h => hb (mem_of_mem_erase h))] at hc have hs := sum_erase_add (condorcet_stable_gap_sets v) w hav rw [hload] at hs linarith · exact (le_of_not_gt hpos).trans (hw a)
All vertex weights in any stable fractional matching are equal: w a = w 0 for all vertices a.
Applying the cyclic inequality w (a + 1) ≤ w a around the 6-cycle gives w 1 ≤ w 0, w 2 ≤ w 1, w 3 ≤ w 2, w 4 ≤ w 3, w 5 ≤ w 4, and w 0 ≤ w 5 (lines 37-42). Linear arithmetic (`linarith`) pinches these into equalities w 1 = w 0 through w 5 = w 0 (lines 43-47). A case exhaustion over the 6 elements of Fin 6 (`fin_cases`) then proves w a = w 0 for every vertex a.
have h0 : w 1 ≤ w 0 := hmono 0 have h1 : w 2 ≤ w 1 := hmono 1 have h2 : w 3 ≤ w 2 := hmono 2 have h3 : w 4 ≤ w 3 := hmono 3 have h4 : w 5 ≤ w 4 := hmono 4 have h5 : w 0 ≤ w 5 := hmono 5 have heq1 : w 1 = w 0 := by linarith have heq2 : w 2 = w 0 := by linarith have heq3 : w 3 = w 0 := by linarith have heq4 : w 4 = w 0 := by linarith have heq5 : w 5 = w 0 := by linarith have heq : ∀ a : Fin 6, w a = w 0 := by intro a fin_cases a · rfl · exact heq1 · exact heq2 · exact heq3 · exact heq4 · exact heq5
Every stable fractional matching assigns weight exactly 1/3 to every vertex: w a = 1/3 for all a.
Stability for vertex 0 provides a triple U v with total weight 1. Since every triple has cardinality 3 (`hcard`, checked by `decide`), rewriting the sum of equal weights w 0 with `sum_const` gives 3 * w 0 = 1, forcing w 0 = 1/3. Since all weights equal w 0, w a = 1/3 for all a.
uses
sum_constobtain ⟨v,_,hload,_⟩ := hstable 0 have hcard : ∀ v, (condorcet_stable_gap_sets v).card = 3 := by decide simp_rw [heq] at hload rw [sum_const,hcard] at hload norm_num at hload intro a rw [heq] linarith
Every set in the family U of 20 triples has cardinality 3 and weight sum 1 under the uniform weight assignment 1/3.
The family U of 20 triples and local rankings p are defined. Finite check (`decide`) confirms that each triple has size 3 (`hcard`). Rewriting with `sum_const` and arithmetic shows that summing 1/3 over any triple U v yields 3 * (1/3) = 1 (`hload`).
uses
sum_constlet U := condorcet_stable_gap_sets let p := condorcet_stable_gap_rank have hcard : ∀ v, (U v).card = 3 := by decide have hload : ∀ v, (∑ a ∈ U v, (1 / 3 : ℝ)) = 1 := by intro v rw [sum_const,hcard] norm_num
The family U and rankings p satisfy the cardinality, 10-regularity, and injectivity conditions. automation
The witnesses U and p are supplied to the existential goal via `refine`. The cardinality condition is discharged by `hcard`. Finite exhaustion (`decide`) verifies that each vertex is covered by exactly 10 triples (line 96) and that the local ranking p v is injective for every triple v (line 97).
refine ⟨U,p,hcard,?_,?_,?_,?_,?_,?_⟩ · decide · decide
The uniform weight 1/3 is a stable fractional matching for (U, p).
Exhaustive finite check (`decide`) proves `hlast`: for every vertex a, there is a triple U v containing a where a has maximal rank (p v b ≤ p v a for all b ∈ U v). The uniform weight assignment w = 1/3 satisfies non-negativity, satisfies capacity with equality by `hload`, and satisfies stability because the maximal rank property holds on the saturated triple U v.
· have hlast : ∀ a, ∃ v, a ∈ U v ∧ ∀ b ∈ U v, p v b ≤ p v a := by decide refine ⟨fun _ => 1/3,fun _ => by norm_num,fun v => (hload v).le,?_⟩ intro a obtain ⟨v,hav,hv⟩ := hlast a exact ⟨v,hav,hload v,fun b hb _ => hv b hb⟩
Every stable fractional matching for (U, p) is uniquely the uniform weight 1/3.
The uniqueness claim is proved directly by applying the auxiliary theorem `condorcet_stable_gap_uniform`.
uses
condorcet_stable_gap_uniform· exact condorcet_stable_gap_uniformFor every stable fractional matching w and every subset J of at most three vertices, some tight triple is disjoint from J.
Finite evaluation (`decide`) proves `hmiss`: since U consists of all 20 triples of a 6-element set, any subset J of size at most 3 leaves at least 3 vertices in its complement, so there is some triple U v disjoint from J. By the uniqueness theorem `condorcet_stable_gap_uniform`, any stable matching w must be identically 1/3, which makes every triple tight by `hload`. Thus U v is a tight triple disjoint from J.
uses
condorcet_stable_gap_uniform· have hmiss : ∀ J : Finset (Fin 6), J.card ≤ 3 → ∃ v : Fin 20, ∀ a ∈ J, a ∉ U v := by decide intro w hw hc hs J hJ obtain ⟨v,hv⟩ := hmiss J hJ refine ⟨v,?_,hv⟩ have heq := condorcet_stable_gap_uniform w hw hc hs simp_rw [heq] exact hload v
The rank-compatible cover relation fails property S3. automation
Unfolding `condorcet_cover_rank_relation`, the claim that there exists a 3-element subset J with no external Condorcet dominator is verified by finite exhaustive evaluation (`decide`).
· unfold condorcet_cover_rank_relation decide
not_lt_of_ge- If a ≤ b, then b is not strictly less than a.
sum_insert- The sum of a function over a set with an element inserted equals the value at that element plus the sum over the original set, provided the element was not in the original set.
mem_of_mem_erase- If an element belongs to a finite set with some element removed, then it belongs to the original set.
sum_erase_add- For any element of a finite set, adding its value to the sum over the set with that element removed equals the total sum over the set.
le_of_not_gt- In a linear order, if b is not strictly less than a, then a ≤ b.
sum_const- The sum of a constant value over a finite set equals the cardinality of the set multiplied by that constant.
condorcet_stable_gap_uniform- Any non-negative weight assignment on the 6 vertices that satisfies the capacity constraints and stability condition with respect to the 20 triples and their rankings must assign the uniform weight 1/3 to every vertex.
- The cyclic ranking property hcyc, triple exchange property hreplace, vertex degree regularity, local ranking injectivity, maximal-element witness hlast, subset-missing property hmiss, and the failure of property S3 are all established by Lean's decide tactic via finite exhaustive evaluation over Fin 6 and Fin 20.
- The stability condition requires that for every vertex a, there is a saturated triple containing a in which no element with positive weight is ranked numerically strictly above a.
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 Finset BigOperatorsset_option maxHeartbeats 4000000set_option maxRecDepth 30000set_option synthInstance.maxSize 10000def condorcet_stable_gap_sets : Fin 20 → Finset (Fin 6) := ![{0,1,2},{0,1,3},{0,1,4},{0,1,5},{0,2,3},{0,2,4},{0,2,5},{0,3,4},{0,3,5},{0,4,5},{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}]def condorcet_stable_gap_rank : Fin 20 → Fin 6 → ℕ := ![![0,1,2,9,10,11],![0,1,8,2,10,11],![1,2,8,9,0,11],![1,2,8,9,10,0],![2,7,0,1,10,11],![0,7,2,9,1,11],![2,7,0,9,10,1],![1,7,8,0,2,11],![2,7,8,0,10,1],![2,7,8,9,0,1],![6,0,1,2,10,11],![6,0,1,9,2,11],![6,0,1,9,10,2],![6,1,8,0,2,11],![6,2,8,1,10,0],![6,1,8,9,0,2],![6,7,0,1,2,11],![6,7,0,1,10,2],![6,7,2,9,0,1],![6,7,8,0,1,2]]def condorcet_stable_gap_next : Fin 6 → Fin 6 := ![1,2,3,4,5,0]theorem condorcet_stable_gap_uniform (w : Fin 6 → ℝ) (hw : ∀ a, 0 ≤ w a) (hcap : ∀ v, (∑ a ∈ condorcet_stable_gap_sets v, w a) ≤ 1) (hstable : ∀ a, ∃ v, a ∈ condorcet_stable_gap_sets v ∧ (∑ b ∈ condorcet_stable_gap_sets v, w b) = 1 ∧ ∀ b ∈ condorcet_stable_gap_sets v, 0 < w b → condorcet_stable_gap_rank v b ≤ condorcet_stable_gap_rank v a) : ∀ a, w a = 1 / 3 := by have hcyc : ∀ a v, a ∈ condorcet_stable_gap_sets v → condorcet_stable_gap_next a ∈ condorcet_stable_gap_sets v → condorcet_stable_gap_rank v a < condorcet_stable_gap_rank v (condorcet_stable_gap_next a) := by decide have hreplace : ∀ (v : Fin 20) (a b : Fin 6), a ∈ condorcet_stable_gap_sets v → b ∉ condorcet_stable_gap_sets v → ∃ z, condorcet_stable_gap_sets z = insert b ((condorcet_stable_gap_sets v).erase a) := by decide have hmono : ∀ a, w (condorcet_stable_gap_next a) ≤ w a := by intro a by_cases hpos : 0 < w (condorcet_stable_gap_next a) · obtain ⟨v,hav,hload,horder⟩ := hstable a have hb : condorcet_stable_gap_next a ∉ condorcet_stable_gap_sets v := by intro hb exact (not_lt_of_ge (horder _ hb hpos)) (hcyc a v hav hb) obtain ⟨z,hz⟩ := hreplace v a (condorcet_stable_gap_next a) hav hb have hc := hcap z rw [hz, sum_insert (fun h => hb (mem_of_mem_erase h))] at hc have hs := sum_erase_add (condorcet_stable_gap_sets v) w hav rw [hload] at hs linarith · exact (le_of_not_gt hpos).trans (hw a) have h0 : w 1 ≤ w 0 := hmono 0 have h1 : w 2 ≤ w 1 := hmono 1 have h2 : w 3 ≤ w 2 := hmono 2 have h3 : w 4 ≤ w 3 := hmono 3 have h4 : w 5 ≤ w 4 := hmono 4 have h5 : w 0 ≤ w 5 := hmono 5 have heq1 : w 1 = w 0 := by linarith have heq2 : w 2 = w 0 := by linarith have heq3 : w 3 = w 0 := by linarith have heq4 : w 4 = w 0 := by linarith have heq5 : w 5 = w 0 := by linarith have heq : ∀ a : Fin 6, w a = w 0 := by intro a fin_cases a · rfl · exact heq1 · exact heq2 · exact heq3 · exact heq4 · exact heq5 obtain ⟨v,_,hload,_⟩ := hstable 0 have hcard : ∀ v, (condorcet_stable_gap_sets v).card = 3 := by decide simp_rw [heq] at hload rw [sum_const,hcard] at hload norm_num at hload intro a rw [heq] linariththeorem condorcet_stable_fractional_tight_cover_obstruction : ∃ (U : Fin 20 → Finset (Fin 6)) (p : Fin 20 → Fin 6 → ℕ), (∀ v, (U v).card = 3) ∧ (∀ a, (univ.filter fun v => a ∈ U v).card = 10) ∧ (∀ v, Function.Injective (p v)) ∧ (∃ w : Fin 6 → ℝ, (∀ a, 0 ≤ w a) ∧ (∀ v, (∑ a ∈ U v, w a) ≤ 1) ∧ ∀ a, ∃ v, a ∈ U v ∧ (∑ b ∈ U v, w b) = 1 ∧ ∀ b ∈ U v, 0 < w b → p v b ≤ p v a) ∧ (∀ w : Fin 6 → ℝ, (∀ a, 0 ≤ w a) → (∀ v, (∑ a ∈ U v, w a) ≤ 1) → (∀ a, ∃ v, a ∈ U v ∧ (∑ b ∈ U v, w b) = 1 ∧ ∀ b ∈ U v, 0 < w b → p v b ≤ p v a) → ∀ a, w a = 1 / 3) ∧ (∀ w : Fin 6 → ℝ, (∀ a, 0 ≤ w a) → (∀ v, (∑ a ∈ U v, w a) ≤ 1) → (∀ a, ∃ v, a ∈ U v ∧ (∑ b ∈ U v, w b) = 1 ∧ ∀ b ∈ U v, 0 < w b → p v b ≤ p v a) → ∀ J : Finset (Fin 6), J.card ≤ 3 → ∃ v, (∑ a ∈ U v, w a) = 1 ∧ ∀ a ∈ J, a ∉ U v) ∧ ¬(∀ J : Finset (Fin 6), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, condorcet_cover_rank_relation U p a b) := by let U := condorcet_stable_gap_sets let p := condorcet_stable_gap_rank have hcard : ∀ v, (U v).card = 3 := by decide have hload : ∀ v, (∑ a ∈ U v, (1 / 3 : ℝ)) = 1 := by intro v rw [sum_const,hcard] norm_num refine ⟨U,p,hcard,?_,?_,?_,?_,?_,?_⟩ · decide · decide · have hlast : ∀ a, ∃ v, a ∈ U v ∧ ∀ b ∈ U v, p v b ≤ p v a := by decide refine ⟨fun _ => 1/3,fun _ => by norm_num,fun v => (hload v).le,?_⟩ intro a obtain ⟨v,hav,hv⟩ := hlast a exact ⟨v,hav,hload v,fun b hb _ => hv b hb⟩ · exact condorcet_stable_gap_uniform · have hmiss : ∀ J : Finset (Fin 6), J.card ≤ 3 → ∃ v : Fin 20, ∀ a ∈ J, a ∉ U v := by decide intro w hw hc hs J hJ obtain ⟨v,hv⟩ := hmiss J hJ refine ⟨v,?_,hv⟩ have heq := condorcet_stable_gap_uniform w hw hc hs simp_rw [heq] exact hload v · unfold condorcet_cover_rank_relation decide