Condorcet Winner (COMSOC)

Definition

Condorcet Winner ( COMSOC)

A Condorcet winner is an alternative that defeats every other alternative by strict majority under the Condorcet method. For a profile $R=({\succ }_1,\dots ,{\succ }_n)$ of $n$ complete, strict rankings over $C$, let $N_R$ be its pairwise support function. Alternative $c\in C$ is a Condorcet winner exactly when

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

A tie against even one opponent is insufficient. A Condorcet winner need not exist, but is unique whenever it exists: two alternatives cannot each be preferred to the other by more than half the voters.

Majority Graph

In the majority graph $G(R)=(C,E)$, let $m=|C|$ and let $d^{+}(c)$ be the number of outgoing arcs from $c$. Then

$$c\text{ is a Condorcet winner}⟺d^{+}(c)=m-1.$$

There must be an outgoing arc to every other alternative, because each arc records a strict head-to-head victory. Having no incoming arcs alone is insufficient: a tied contest produces no arc, but prevents $c$ from defeating every opponent.

Dodgson Score

An alternative is already a Condorcet winner exactly when no adjacent swaps are needed to make it one. Thus its Dodgson score satisfies

$$c\text{ is a Condorcet winner in }R⟺{\mathrm{Dodgson}}_R(c)=0.$$

Young Score

Under the minimum-deletions convention, an alternative is already a Condorcet winner exactly when no voters need to be removed. Thus its Young score satisfies

$$c\text{ is a Condorcet winner in }R⟺{\mathrm{Young}}_R(c)=0.$$

Under the alternative maximum-retained convention, the corresponding score is $n$, not zero: all voters can be retained.