AFTD Auto-Formalizing Theoretical Domains

condorcet_failure_k_iff_acyclic_half_cover

theoremverified

For fixed voter count n and committee bound k, some finite n-voter election has no strict Condorcet winning committee of size at most k if and only if some finite relation has outside common predecessors for sets of size at most k and admits n induced acyclic sets covering every vertex at least half the time. This generalizes the existing k=3 equivalence and proves neither existence nor nonexistence of such objects.

Statement

theorem condorcet_failure_k_iff_acyclic_half_cover (n k : ℕ) :
    (∃ (m : ℕ) (P : Fin n → Equiv.Perm (Fin m)),
      ∀ S : Finset (Fin m), S.card ≤ k → ¬is_condorcet_winning_set P S) ↔
    (∃ (q : ℕ) (R : Fin q → Fin q → Prop) (U : Fin n → Finset (Fin q)),
      (∀ J : Finset (Fin q), J.card ≤ k → ∃ a, a∉J ∧ ∀ b∈J, R a b) ∧
      (∀ v, WellFounded (fun a b : {a : Fin q // a∈U v} => R a.val b.val)) ∧
      (∀ a, n ≤ 2*(univ.filter fun v => a∈U v).card))
Source
IN-383, OP-19 campaign session 9, 2026-10-30. Structural verification of the maximum-potential neighborhood route suggested in IN-380. Generalization of the existing acyclic-cover reduction, whose strict election definition is from Condorcet winning sets, Social Choice and Welfare 44(3):493-517 (2015), https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf . No new election bound or research novelty is claimed.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • condorcet_acyclic_cover_no_winning_kFor any voter count n and committee bound k, a finite relation having outside common predecessors for all sets of at most k vertices,…
  • condorcet_acyclic_half_cover_of_no_winning_kFor any n and k, a finite n-voter election with no strict Condorcet winning set of size at most k yields a finite relation with outside…
  • is_condorcet_winning_setWith n voters holding strict rankings of m candidates, S is a Condorcet winning set if for every candidate a ∉ S, strictly fewer than n/2…

The proof, explained

The theorem establishes an equivalence between the non-existence of a size-at-most-k Condorcet winning committee in an n-voter election and the existence of a finite relation where every subset of size at most k has an outside common predecessor, together with n induced acyclic subsets covering each vertex at least half the time. The proof decomposes the equivalence into two directions. The forward direction applies `condorcet_acyclic_half_cover_of_no_winning_k` to extract the relation and acyclic half-cover from an election profile lacking a winning committee, while the reverse direction applies `condorcet_acyclic_cover_no_winning_k` to construct such an election profile from the relational data.

  1. The equivalence reduces to proving each implication separately.

    Splitting the bidirectional equivalence with `constructor` yields two independent subgoals: the forward implication and the reverse implication.

    line 13

      constructor
  2. An election profile with no Condorcet winning committee of size at most k implies the existence of an acyclic half-cover relation.

    Assuming an election profile P on m candidates with no Condorcet winning set of size at most k, the lemma `condorcet_acyclic_half_cover_of_no_winning_k` directly constructs the candidate count q, relation R, and acyclic half-cover family U satisfying the three relational conditions.

    lines 14–15

    uses condorcet_acyclic_half_cover_of_no_winning_k

      · rintro ⟨m,P,hP⟩
        exact condorcet_acyclic_half_cover_of_no_winning_k n m k P hP
  3. Conversely, an acyclic half-cover relation implies the existence of an election profile with no Condorcet winning committee of size at most k.

    Given a relation R on q elements with outside common predecessors for sets of size at most k and an acyclic half-cover U, the lemma `condorcet_acyclic_cover_no_winning_k` constructs an n-voter election profile P on q candidates where no committee of size at most k is winning. Providing q and P closes the reverse goal.

    lines 16–18

    uses condorcet_acyclic_cover_no_winning_k

      · rintro ⟨q,R,U,hroot,hacyclic,hhalf⟩
        obtain ⟨P,hP⟩ := condorcet_acyclic_cover_no_winning_k n q k R U hroot hacyclic hhalf
        exact ⟨q,P,hP⟩
condorcet_acyclic_half_cover_of_no_winning_k
If an n-voter election on m candidates has no Condorcet winning committee of size at most k, then there exists a finite relation on q elements where every subset of size at most k has an outside common predecessor, and an n-family of induced acyclic subsets covering each vertex at least half the time.
condorcet_acyclic_cover_no_winning_k
If a relation on m elements has outside common predecessors for all subsets of size at most k and admits an n-family of induced acyclic subsets covering each vertex at least half the time, then there exists an n-voter election profile on m candidates in which no committee of size at most k is Condorcet winning.

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 4000000set_option maxRecDepth 10000theorem condorcet_failure_k_iff_acyclic_half_cover (n k : ℕ) :    (∃ (m : ℕ) (P : Fin n → Equiv.Perm (Fin m)),      ∀ S : Finset (Fin m), S.card ≤ k → ¬is_condorcet_winning_set P S) ↔    (∃ (q : ℕ) (R : Fin q → Fin q → Prop) (U : Fin n → Finset (Fin q)),      (∀ J : Finset (Fin q), J.card ≤ k → ∃ a, a∉J ∧ ∀ b∈J, R a b) ∧      (∀ v, WellFounded (fun a b : {a : Fin q // a∈U v} => R a.val b.val)) ∧      (∀ a, n ≤ 2*(univ.filter fun v => a∈U v).card)) := by  constructor  · rintro ⟨m,P,hP⟩    exact condorcet_acyclic_half_cover_of_no_winning_k n m k P hP  · rintro ⟨q,R,U,hroot,hacyclic,hhalf⟩    obtain ⟨P,hP⟩ := condorcet_acyclic_cover_no_winning_k n q k R U hroot hacyclic hhalf    exact ⟨q,P,hP⟩
See it in the graphDiscuss this resultChallenge it