Condorcet (COMSOC)

comsoc

Definition

Condorcet

In COMSOC, the Condorcet principle compares alternatives by pairwise majority contests. An alternative $x$ defeats an alternative $y$ if a strict majority of voters ranks $x$ above $y$.

Let

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

be a preference profile over a set of alternatives $C$. For $x,y\in C$, define

$$N_R(x,y):=\left|\{i\in \{1,\dots ,n\}:x{\succ }_{i}y\}\right|.$$

Then $x$ defeats $y$ whenever

$$N_R(x,y)>\frac{n}{2}.$$

A Condorcet winner is an alternative $c\in C$ that defeats every other alternative:

$$\forall y\in C\setminus \{c\}:N_R(c,y)>\frac{n}{2}.$$

Properties

Existence and uniqueness

A Condorcet winner need not exist. If it exists, it is unique, because two distinct alternatives cannot both defeat each other by strict majority.

Condorcet consistency

A Condorcet consistent voting rule always returns the Condorcet winner whenever one exists.

Condorcet paradox

Condorcet Paradox (COMSOC)

comsoc

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(x,y)$ is the number of voters who rank $x$ above $y$. 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.$$

In such a cycle, no alternative can defeat every other alternative, so no Condorcet winner exists.

Example

Majority cycle from the lecture notes

Consider the profile

voters	ranking
$2$	$A\succ B\succ C\succ D$
$1$	$B\succ C\succ D\succ A$
$1$	$C\succ D\succ A\succ B$
$1$	$D\succ B\succ C\succ A$

The majority relation contains the cycle

$$A{\succ }_{M}B,B{\succ }_{M}C,C{\succ }_{M}D,D{\succ }_{M}A.$$

Hence there is no alternative that defeats every other alternative by strict majority.

Link to original

Example

Course profile

In the lecture profile, the pairwise majority contests are:

contest	majority winner	margin
$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.