Dodgson Rule (COMSOC)

Definition

Dodgson Rule ( COMSOC)

The Dodgson rule is the voting rule selecting alternatives with the smallest Dodgson score. For a profile $R$ over alternatives $C$,

$${\lambda }_{\mathrm{Dodgson}}(R):=\arg \underset{x\in C}{\min }{\mathrm{Dodgson}}_R(x).$$

It selects the alternatives requiring the fewest adjacent swaps within voters’ rankings to become Condorcet winners. All alternatives attaining this minimum are Dodgson winners; a further tie-break is needed to select just one when several tie.

Intuition

A Condorcet winner needs no changes. When none exists, ask separately for each alternative: how many exchanges of neighbouring alternatives would suffice to make it defeat every opponent?

These edits are hypothetical. The rule compares the minimum costs from the original ballots; it does not actually rewrite submitted preferences or transfer votes. A successful sequence gives an upper bound on a candidate’s score. To establish the exact score, one must also show that fewer swaps cannot suffice.

Condorcet Consistency

If $c$ is already the Condorcet winner, its score is zero. Every other alternative has positive score, since it is not a Condorcet winner in the unchanged profile:

$${\mathrm{Dodgson}}_R(c)=0<{\mathrm{Dodgson}}_R(x)(x\ne c).$$

Thus $c$ is the unique Dodgson winner, so the rule is Condorcet consistent.

Complexity

Determining a Dodgson winner is NP-hard.

Example

One swap suffices for $B$

Use the familiar five-voter profile:

$$\begin{array}{rl}2\text{ voters}:& A\succ B\succ C\succ D,\\ 1\text{ voter}:& B\succ C\succ D\succ A,\\ 1\text{ voter}:& C\succ D\succ A\succ B,\\ 1\text{ voter}:& D\succ B\succ C\succ A.\end{array}$$

Initially $B$ defeats $C$ by $4:1$ and $D$ by $3:2$, but loses to $A$ by $2:3$. In one of the first two ballots, exchange the adjacent $A,B$:

$$A\succ B\succ C\succ D⟶B\succ A\succ C\succ D.$$

Support for $B$ against $A$ changes from $2$ to $3$, while support for $A$ changes from $3$ to $2$. All other pairwise comparisons remain unchanged. Hence $B$ now defeats every opponent.

One swap suffices, and zero cannot suffice because $B$ originally loses to $A$. Therefore ${\mathrm{Dodgson}}_R(B)=1$.

The original majority cycle $A\to B\to C\to D\to A$ means nobody has score zero. Thus $B$ attains the smallest possible score and is a Dodgson winner. This argument does not claim that it is the unique winner.