Dodgson Score (COMSOC)

Definition

Dodgson Score ( COMSOC)

The Dodgson score of an alternative $x$ is the minimum total number of adjacent swaps in the ballots needed to make $x$ a Condorcet winner. For a profile $R$ of complete, strict rankings,

$${\mathrm{Dodgson}}_R(x):=\underset{R^{\prime }:x\text{ is a Condorcet winner in }{R}^{\prime }}{\min }d(R,R^{\prime }).$$

Here $d(R,R^{\prime })$ is the minimum number of adjacent swaps transforming $R$ into $R^{\prime }$, with the same voters and alternatives.

One swap exchanges two neighbouring alternatives in one voter’s ranking. Swaps may be distributed across several ballots; their total is the cost. Every candidate is evaluated separately, starting from the same original profile $R$.

The score is zero exactly when $x$ is already a Condorcet winner. A positive score measures the least required modification, not merely the number of pairwise contests $x$ loses.

Intuition

One voter: count positions passed

With one voter, becoming a Condorcet winner means reaching first place. In

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

the scores are therefore $(0,1,2,3)$: each alternative must pass everyone above it. For $C$,

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

With several voters, count swaps across ballots and check majorities across the whole profile. Compute every candidate’s score from the same original profile.

Candidate B: two swaps

The left side is the original profile $R$; the right side modifies two ballots to make $B$ a Condorcet winner:

$$\begin{array}{rlrl}1:& A\succ B\succ C⟶B\succ A\succ C& & \text{cost }1,\\ 2:& A\succ C\succ B⟶A\succ B\succ C& & \text{cost }1,\\ 3:& C\succ B\succ A⟶C\succ B\succ A& & \text{cost }0.\end{array}$$

$B$ initially loses both contests. Each swap supplies one missing supporter; with $n=3$, two supporters form a strict majority:

$$\begin{array}{rlrl}{N}_R(B,A)=1& ⟶N_{R^{\prime }}(B,A)=2& & \text{voters 1 and 3},\\ N_R(B,C)=1& ⟶N_{R^{\prime }}(B,C)=2& & \text{voters 1 and 2}.\end{array}$$

Two swaps suffice. One cannot: an adjacent swap changes only one pairwise comparison, but $B$ must repair two losses. Hence ${\mathrm{Dodgson}}_R(B)=2$.

Candidate A: no swaps

Voters 1 and 2 prefer $A$ to both opponents:

$$N_R(A,B)=2,N_R(A,C)=2.$$

Both counts are strict majorities, so no swaps are needed: ${\mathrm{Dodgson}}_R(A)=0$.

Candidate C: one swap

Voters 2 and 3 prefer $C$ to $B$, but only voter 3 prefers $C$ to $A$:

$$N_R(C,B)=2,N_R(C,A)=1.$$

Only the contest against $A$ needs repair. Exchange the adjacent $A,C$ in ballot 2:

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

Now voters 2 and 3 support $C$ against $A$, while its majority against $B$ remains unchanged. One swap suffices; zero cannot suffice because $C$ originally loses to $A$. Hence ${\mathrm{Dodgson}}_R(C)=1$.

The Dodgson winner is $A$, since

$${\mathrm{Dodgson}}_R(A)=0<{\mathrm{Dodgson}}_R(C)=1<{\mathrm{Dodgson}}_R(B)=2.$$

The hypothetical edits above only establish $B$‘s score; they do not make $B$ the winner of the original election.

Each swap increases one side’s support by one and decreases the other’s by one, changing the margin by two. The goal is not to put $B$ first everywhere: different voters can supply its majorities against different opponents.