single_peaked_median_is_condorcet_winner
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— 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.
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.
uses
lt_or_gt_of_neintro y hy rcases lt_or_gt_of_ne hy with hym | hym
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.
uses
single_peaked_median_defeats_less· exact single_peaked_median_defeats_less P hasymm peak hsp m h_ge y hymWhen 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.
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
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.
/-- 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