AFTD Auto-Formalizing Theoretical Domains

single_peaked_median_is_condorcet_winner

theoremverifiedformalization

Under single-peaked preferences with asymmetric preferences, if an alternative m satisfies that strictly more than half of the voters have peak at least m and strictly more than half have peak at most m, then m is a Condorcet winner.

Statement

theorem single_peaked_median_is_condorcet_winner {V A : Type*} [Fintype V] [LinearOrder A]
    (P : V → A → A → Prop) [∀ v, DecidableRel (P v)]
    (hasymm : ∀ v x y, P v x y → ¬ P v y x)
    (peak : V → A) (hsp : ∀ v, is_single_peaked (P v) (peak v))
    (m : A)
    (h_ge : Fintype.card V < 2 * (Finset.filter (fun v => m ≤ peak v) Finset.univ).card)
    (h_le : Fintype.card V < 2 * (Finset.filter (fun v => peak v ≤ m) Finset.univ).card) :
    condorcet_winner P m
Formalizes
Duncan Black, 'On the Rationale of Group Decision-making', Journal of Political Economy 56(1):23-34 (1948)
Verified
09 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • condorcet_winnerIn a profile of preferences P where a finite set of voters V have pairwise preferences over alternatives A, an alternative x : A is a…
  • is_single_peakedA strict preference relation P over a linearly ordered set of alternatives A is single-peaked with peak p if moving toward p strictly…
  • single_peaked_median_defeats_lessUnder single-peaked preferences with asymmetric preferences, if strictly more than half of the voters have peak at least m, then for any…
  • single_peaked_median_defeats_greaterUnder single-peaked preferences with asymmetric preferences, if strictly more than half of the voters have peak at most m, then for any…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

Read back from the Lean

Let $V$ be a finite type (of voters) and $A$ a linearly ordered type (of alternatives). Let $P : V \to A \to A \to \mathrm{Prop}$ be a profile of decidable preference relations, such that each voter's preference is asymmetric (for all $v \in V$ and $x, y \in A$, $P(v, x, y) \implies \neg P(v, y, x)$). Let $\mathrm{peak} : V \to A$ assign each voter a peak alternative such that each voter's preference relation $P(v)$ is single-peaked at $\mathrm{peak}(v)$ (in the sense of is_single_peaked). Let $m \in A$ be an alternative. Assume that: 1. Strict majority above/at $m$: The total number of voters $|V|$ is strictly less than $2 \cdot |\{v \in V \mid m \le \mathrm{peak}(v)\}|$; and 2. Strict majority below/at $m$: The total number of voters $|V|$ is strictly less than $2 \cdot |\{v \in V \mid \mathrm{peak}(v) \le m\}|$. Then $m$ is a Condorcet winner under $P$ (in the sense of condorcet_winner): for every alternative $y \in A$ with $y \ne m$, strictly more voters prefer $m$ to $y$ ($P(v, m, y)$) than prefer $y$ to $m$ ($P(v, y, m)$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To prove that the median peak alternative m is a Condorcet winner, we consider any alternative y ≠ m and show that m defeats y in a head-to-head vote. Since the alternatives are linearly ordered, either y < m or m < y. The argument splits into these two cases, each solved by an existing helper lemma: when y < m, m wins because a strict majority of voters have peaks at or above m; when y > m, m wins because a strict majority of voters have peaks at or below m.

  1. To show that m is a Condorcet winner, it suffices to show that m defeats any alternative y when y < m and when m < y.

    By definition, m is a Condorcet winner if for every alternative y ≠ m, strictly more voters prefer m to y than prefer y to m. Because the space of alternatives A is linearly ordered, any y ≠ m satisfies either y < m or m < y by lt_or_gt_of_ne.

    lines 10–11

    uses lt_or_gt_of_ne

      intro y hy
      rcases lt_or_gt_of_ne hy with hym | hym
  2. When y < m, strictly more voters prefer m to y than prefer y to m.

    By hypothesis h_ge, strictly more than half of the voters have their peak at least m. Applying the lemma single_peaked_median_defeats_less concludes that m defeats y in pairwise voting.

    line 12

    uses single_peaked_median_defeats_less

      · exact single_peaked_median_defeats_less P hasymm peak hsp m h_ge y hym
  3. When m < y, strictly more voters prefer m to y than prefer y to m.

    Symmetrically, by hypothesis h_le, strictly more than half of the voters have their peak at most m. Applying the lemma single_peaked_median_defeats_greater concludes that m defeats y in pairwise voting.

    line 13

    uses single_peaked_median_defeats_greater

      · exact single_peaked_median_defeats_greater P hasymm peak hsp m h_le y hym
lt_or_gt_of_ne
In a linear order, any two distinct elements satisfy either a < b or b < a.
single_peaked_median_defeats_less
Under asymmetric single-peaked preferences, if strictly more than half the voters have their peak at or above m, then m defeats any alternative strictly below m in pairwise majority voting.
single_peaked_median_defeats_greater
Under asymmetric single-peaked preferences, if strictly more than half the voters have their peak at or below m, then m defeats any alternative strictly above m in pairwise majority voting.

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

/-- Black's Median Voter Theorem: an alternative m satisfying the median peak inequalities is a Condorcet winner. -/theorem single_peaked_median_is_condorcet_winner {V A : Type*} [Fintype V] [LinearOrder A]    (P : V → A → A → Prop) [∀ v, DecidableRel (P v)]    (hasymm : ∀ v x y, P v x y → ¬ P v y x)    (peak : V → A) (hsp : ∀ v, is_single_peaked (P v) (peak v))    (m : A)    (h_ge : Fintype.card V < 2 * (Finset.filter (fun v => m ≤ peak v) Finset.univ).card)    (h_le : Fintype.card V < 2 * (Finset.filter (fun v => peak v ≤ m) Finset.univ).card) :    condorcet_winner P m := by  intro y hy  rcases lt_or_gt_of_ne hy with hym | hym  · exact single_peaked_median_defeats_less P hasymm peak hsp m h_ge y hym  · exact single_peaked_median_defeats_greater P hasymm peak hsp m h_le y hym
See it in the graphDiscuss this resultChallenge it