Dodgson's Rule (COMSOC)

comsoc

Definition

Dodgson's Rule

In COMSOC, Dodgson’s Rule, named after Charles Lutwidge Dodgson, is a voting rule that selects the alternatives that can be made Condorcet winners with the fewest adjacent swaps in the voters’ preference rankings.

Let

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

be a preference profile over alternatives $C$. For an alternative $x\in C$, its Dodgson score is

$${\mathrm{Dodgson}}_R(x):=\min \{k:\text{after }k\text{ adjacent swaps in }R,x\text{ is a Condorcet winner}\}.$$

Dodgson’s Rule returns the alternatives with minimum Dodgson score:

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

Each alternative in this set is a Dodgson winner.

Mechanism

Repairing pairwise losses

An adjacent swap exchanges two neighbouring alternatives in one voter’s ranking. Dodgson’s Rule asks how cheaply each alternative can be moved upward across enough rankings to defeat every other alternative in head-to-head majority contests.

Example

Lecture profile

Consider the profile from the lecture notes:

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$

Alternative $B$ defeats $C$ and $D$, but loses to $A$ by $3$ votes to $2$. Swapping $B$ above $A$ in one of the two rankings

$$A\succ B\succ C\succ D$$

changes that one voter from preferring $A$ over $B$ to preferring $B$ over $A$. Then $B$ defeats $A$ by $3$ votes to $2$, and hence $B$ becomes a Condorcet winner.

Therefore

$${\mathrm{Dodgson}}_R(B)=1.$$

Properties

Condorcet winners have score zero

If $x$ is already a Condorcet winner, then

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

Conversely, if ${\mathrm{Dodgson}}_R(x)=0$, then $x$ is already a Condorcet winner.

Condorcet consistency

Dodgson’s Rule is a Condorcet consistent voting rule.

Computational hardness

The lecture notes state that determining a Dodgson winner is NP-hard.