AFTD Auto-Formalizing Theoretical Domains

condorcet_stable_fractional_tight_cover_obstruction

theoremverified

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.

  1. 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.

    lines 17–22

      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
  2. 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.

    lines 23–36

    uses not_lt_of_ge, sum_insert, mem_of_mem_erase, sum_erase_add, le_of_not_gt

      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)
  3. 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.

    lines 37–56

      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
  4. 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.

    lines 57–64

    uses sum_const

      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]
      linarith
  5. 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`).

    lines 88–94

    uses sum_const

      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
  6. 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).

    lines 95–97

      refine ⟨U,p,hcard,?_,?_,?_,?_,?_,?_⟩
      · decide
      · decide
  7. 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.

    lines 98–102

      · 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⟩
  8. 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`.

    line 103

    uses condorcet_stable_gap_uniform

      · exact condorcet_stable_gap_uniform
  9. For 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.

    lines 104–110

    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
  10. 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`).

    lines 111–112

      · 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.

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 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
See it in the graphDiscuss this resultChallenge it