Dodgson Method - Condorcet completion by minimum pairwise swaps

Pairwise-swap distance - alternative needing fewest swaps to become Condorcet winner

Dodgson, C. L.1900

Overview

Dodgson selects the alternative that is 'closest' to being a Condorcet winner - measured in pairwise swap distance. Always returns a winner (no paradox), but winner determination is NP-hard for unrestricted preference profiles. For m ≤ 10, exhaustive search is practical; beyond that, use approximation algorithms. Orakçı 2024 (Bölüm 3) shows Dodgson fails to produce full rankings in 82-99% of random samples for m ≥ 3 - use Kemeny or RAT for guaranteed full rankings.

Output: rank position, lower is better
Data: Crisp, complete rank
Size: 2+ alternatives, 3-12 criteria works best
Used for: Rank aggregation, social choice, preference fusion

How it works

1
Collect rankings R[i,k]; build pairwise preference count matrix p_ij = #{k: r_ik < r_jk}.
$R = [r_{ik}]_{m \times n}, p_{ij} = # {k : r_{ik} < r_{j k}}$
Dodgson 1876, Sec.1
2
For each alternative i, find the minimum number of adjacent swaps (across all rankings) required so that i becomes the Condorcet winner. Sum of swaps over rankings = Dodgson score s_i.
$s_{i} = π \in S_{m}^{n} min # {adjacent swaps in π^{(1)}, \dots, π^{(n)}} s.t. p_{ij}^{π} > p_{j i}^{π} \forall j \neq = i$
Dodgson 1876, Sec.2; Black 1958 Appendix A
3
Dodgson winner = arg min_i s_i (alternative needing fewest swaps). Rank others by ascending swap count.
$i^{*} = ar g i \in {1, \dots, m} min s_{i}; Rank (i) \propto s_{i}$
Dodgson 1876, Sec.3

Fits when / Look elsewhere when

Fits when

•Native group-decision support (multi-DM aggregation built into the pipeline)

Look elsewhere when

•Cardinal preferences important. Use a MAUT method.

Assumptions to verify

Input is a rank matrix (1=best, m=worst per voter)
Each voter ranks all alternatives

Edge cases and pitfalls

NP-hardness of winner determination - exact computation infeasible for m > 12 in practice. Use Bartholdi-Tovey-Trick (1989) approximation or restrict to small candidate sets.
Frequent non-full rankings: Orakçı 2024 Bölüm 3 demonstrates Dodgson fails to produce strict total order in ~82-99% of random samples - combine with another rule or use RAT/Kemeny if completeness matters.

How to cite

Dodgson, C. L. (1900). A method of taking votes on more than two issues (1876). Pamphlet, Clarendon Press, Oxford (original 1876).

BibTeX RIS APA (.txt)

System ID, as it appears in reports and the API

DODGSON

Overview

Output

rank position, lower is better

Data

Crisp, complete rank

Size

2+ alternatives, 3-12 criteria works best

Used for

Rank aggregation, social choice, preference fusion

How it works

Collect rankings R[i,k]; build pairwise preference count matrix p_ij = #{k: r_ik < r_jk}.

R = [r_{ik}]_{m \times n}, p_{ij} = # {k : r_{ik} < r_{j k}}

Dodgson 1876, Sec.1

For each alternative i, find the minimum number of adjacent swaps (across all rankings) required so that i becomes the Condorcet winner. Sum of swaps over rankings = Dodgson score s_i.

s_{i} = π \in S_{m}^{n} min # {adjacent swaps in π^{(1)}, \dots, π^{(n)}} s.t. p_{ij}^{π} > p_{j i}^{π} \forall j \neq = i

Dodgson 1876, Sec.2; Black 1958 Appendix A

Dodgson winner = arg min_i s_i (alternative needing fewest swaps). Rank others by ascending swap count.

i^{*} = ar g i \in {1, \dots, m} min s_{i}; Rank (i) \propto s_{i}

Dodgson 1876, Sec.3

Edge cases and pitfalls

NP-hardness of winner determination - exact computation infeasible for m > 12 in practice. Use Bartholdi-Tovey-Trick (1989) approximation or restrict to small candidate sets.

Frequent non-full rankings: Orakçı 2024 Bölüm 3 demonstrates Dodgson fails to produce strict total order in ~82-99% of random samples - combine with another rule or use RAT/Kemeny if completeness matters.