Condorcet Rule (COMSOC)

Definition

Condorcet Rule ( COMSOC)

The Condorcet rule compares every pair of alternatives by majority vote and selects an alternative that defeats every opponent. For a profile

$$R=({\succ }_1,\dots ,{\succ }_n)$$

of $n$ complete, strict rankings over $C$, let $N_R$ be its pairwise support function. Then

$$\begin{array}{rl}{\lambda }_{\mathrm{Condorcet}}(R)& :=\left\{x\in C:\forall y\in C\setminus \{x\},N_R(x,y)>\frac{n}{2}\right\}.\end{array}$$

In each contest, every voter supports whichever of the two alternatives they rank higher. A strict majority wins the contest; a tie is not a victory. The selected alternative is the Condorcet winner.

Unlike plurality or Borda count, this procedure can return no alternative: ${\lambda }_{\mathrm{Condorcet}}(R)$ is either a singleton or empty. A voting rule that must always return a winner needs an additional convention for the empty case.

Intuition

For one contest, keep only the two alternatives being compared on each ballot. Their relative order stays unchanged. Unlike plurality, a voter need not rank an alternative first overall to support it in this contest.

The course profile has $n=30+18+28+24=100$ voters. For $B$ against $C$, it reduces to:

Thus $C$ defeats $B$, even though 24 of its supporters rank $D$ first overall. Repeat this comparison against every opponent. Winning just one contest is not enough, and the sizes of victories are not added into a total score.

Condorcet Consistency

A Condorcet consistent voting rule selects the Condorcet winner whenever one exists. This requirement alone does not specify what to return when none exists; the Condorcet principle is therefore not a complete voting rule on all profiles.

Issues

Non-existence

Pairwise majorities can cycle: $A$ defeats $B$, $B$ defeats $C$, and $C$ defeats $A$. Every alternative then loses a contest, so none is a Condorcet winner.

Definition

Condorcet Paradox

In COMSOC, the Condorcet paradox is the fact that individually consistent preference rankings can induce a cyclic majority relation over alternatives.

Let $R$ be a preference profile, and define the majority relation ${\succ }_M$ by

$$x{\succ }_{M}y⟺N_R(x,y)>\frac{n}{2},$$

where $N_R$ is the pairwise support function and $n$ is the number of voters. A Condorcet paradox occurs when ${\succ }_M$ contains a cycle, for example

$$x_1{\succ }_M{x}_2{\succ }_M\cdots {\succ }_M{x}_k{\succ }_M{x}_1.$$

No alternative on the cycle is a Condorcet winner, since each loses to another member. If the cycle includes every alternative, no Condorcet winner exists; an alternative outside the cycle may still defeat all others.

Link to original

Majority Graph

Each vertex represents an alternative. An arrow points from the head-to-head winner to the loser: $x\to y$ means $N_R(x,y)>n/2$. It records a comparison, not a transfer of votes.

The label gives winner’s votes : loser’s votes. Here 52 voters prefer $C$ to $B$ and 48 prefer $B$ to $C$, so the arrow points towards $B$.

Now focus on $B$. An incoming arrow records a defeat; an outgoing arrow records a victory. Here $B$ loses to $C$ but defeats $A$. These are two separate contests using the same ballots.

A tied pair has no arrow in either direction. Thus having no incoming arrows is not enough to be a Condorcet winner: an alternative must actually defeat every opponent.

In the course profile, $C$ has an outgoing arrow to each of $A,B,D$. All three counts exceed 50, so $C$ is the Condorcet winner. The full graph in the example also includes the contests among its opponents.

Do not infer another victory by following a path. In this separate profile, each ranking occurs once, and the three majorities form a cycle. Every alternative has an incoming arrow, so none is a Condorcet winner.

Example

The same 100-voter profile

Each row groups voters with the same complete ranking. The copied diagram shows plurality scores for comparison; Condorcet contests use the relative order of each pair instead.

Count the voters preferring each alternative to its opponent:

contest	majority winner	votes for winner–loser
$A$ vs. $B$	$B$	$70$—$30$
$A$ vs. $C$	$C$	$70$—$30$
$A$ vs. $D$	$A$	$58$—$42$
$B$ vs. $C$	$C$	$52$—$48$
$B$ vs. $D$	$B$	$76$—$24$
$C$ vs. $D$	$C$	$58$—$42$

Since $C$ defeats $A$, $B$, and $D$, the alternative $C$ is the Condorcet winner.

In particular,

$$\begin{array}{rl}{N}_R(C,A)& =18+28+24=70>50,\\ N_R(C,B)& =28+24=52>50,\\ N_R(C,D)& =30+28=58>50.\end{array}$$

This differs from the same profile’s plurality winner $A$ and Borda winner $B$.