Condorcet Paradox (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$ 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.

Example

Majority cycle from the lecture notes

Each row groups voters with the same complete ranking:

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.