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.