Dodgson Rule (COMSOC)

Definition

Dodgson Rule ( COMSOC)

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

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 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:

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

Complexity

Determining a Dodgson winner is NP-hard.

Example

One swap suffices for

Use the familiar five-voter profile:

Initially defeats by and by , but loses to by . In one of the first two ballots, exchange the adjacent :

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

One swap suffices, and zero cannot suffice because originally loses to . Therefore .

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