The fewest swaps to a winner

A Condorcet winner is a candidate who beats every other candidate in a head-to-head vote. When there is one, almost everyone agrees it should win. How few voters any majority needs showed how easily there is none: three voters with ordinary rankings can produce any pattern of head-to-head results at all, cycles included, and with four candidates about one electorate in seven drawn at random has no Condorcet winner.

What then? Charles Lutwidge Dodgson — better known as Lewis Carroll, and at the time a mathematics lecturer at Christ Church, Oxford — proposed an answer in a pamphlet of 1876 written for the college’s elections. If no candidate beats everyone, elect the one that is nearest to doing so, where nearness is measured by the fewest changes to the ballots that would make it a Condorcet winner. The change allowed is the smallest one possible: swapping two names that stand next to each other on one ballot.

In the figure, nine voters rank four candidates, and no candidate wins every contest. Candidate A needs one swap: on a single ballot, A moves up one place past C, and that one vote turns A’s defeat by C into a win. B needs two swaps, C three and D six. So the Dodgson winner is A. The Borda count, which gives each candidate points by position on every ballot, prefers B by one point. The two rules disagree on the same ballots, which five rules and five winners found to be the normal condition.

Where the score comes from #

A Dodgson score is built from the head-to-head margins, and the construction is worth taking apart.

For a candidate $c$ and a rival $d$, the margin is the number of voters ranking $c$ above $d$ minus the number ranking $d$ above $c$. With nine voters the margins are odd. If $c$’s margin against $d$ is $-1$, then $c$ has to win over one voter: moving $c$ above $d$ on one ballot changes that voter’s preference and swings the margin by two, to $+1$. If the margin is $-3$, two voters must be won over; in general $\lfloor -m/2 \rfloor + 1$ of them. That number, summed over the rivals $c$ has not yet beaten, is the votes still to win.

Every adjacent swap that moves $c$ up past $d$ wins exactly one vote against exactly one rival. So the Dodgson score is at least the votes still to win. It can be more, because a rival need not stand immediately above $c$ on any convenient ballot: to move $c$ past $d$ on a ballot where $e$ stands between them, $c$ must first pass $e$, which costs a swap and may win a vote that was not needed.

In this electorate the two counts agree for every candidate: A needs one vote against C, B needs two, C three and D six. In general they need not, and the gap between them is what makes the rule hard.

Two other ways to be nearest #

Dodgson’s is not the only rule that elects the candidate closest to a Condorcet winner; it is the one that measures closeness by swaps. Two others measure it differently, and comparing them shows what the swap count adds.

The minimax rule, associated with Paul Kramer and Edward Simpson, looks only at each candidate’s worst defeat — the most votes it would need to win over against any single rival — and elects the candidate whose worst defeat is smallest. It reads the same head-to-head table as Dodgson’s rule and asks a coarser question of it: not how many votes must be won in total, but how many against the hardest rival. In the figure’s electorate the two rules agree, since A’s only defeat is by a single vote and every other candidate loses somewhere by more. They come apart when a candidate has one narrow defeat and several others: minimax forgives the several, Dodgson’s rule counts them all.

Young’s rule, proposed by Peyton Young in 1977, measures closeness by deleting voters rather than swapping names: it elects the candidate that becomes a Condorcet winner after removing the fewest ballots. Deleting a voter who ranks $c$ low helps $c$ against every rival that voter ranked above it, all at once, where a swap helps against one rival at a time. Young’s rule shares the hardness of Dodgson’s and, as it happens, the same template: a consensus, a distance to it, and the candidate at the least distance.

All three are Condorcet-consistent, and all three pick different winners on some electorates. The template does not settle the rule; the choice of distance is where the principle lives.

Why the count needs a search #

To compute a Dodgson score exactly, one must decide for every ballot how far to lift the candidate — not at all, one place, two places — so that every deficit is met and the total lift is least. Each ballot offers a menu, and the choices interact, since lifting on one ballot may cover a deficit that another ballot would otherwise have to cover.

For a handful of candidates this is a small search. The figures compute it by working through the ballots one at a time and keeping, for each combination of votes still needed against each rival, the cheapest way found so far to reach it; with four candidates the combinations number at most a few thousand, and the search is exact. But the menu grows with the number of candidates, and the combinations grow exponentially.

John Bartholdi, Craig Tovey and Michael Trick proved in 1989 that deciding whether a given candidate’s Dodgson score is at most a given number is NP-complete — as hard as any problem whose answers can be checked quickly — and Edith and Lane Hemaspaandra and Jörg Rothe showed in 1997 that deciding who wins is harder still, complete for a class of problems solvable by asking an NP oracle many questions in parallel. So no efficient method for computing Dodgson winners exists unless the central conjecture of complexity theory is false. A failed search is a proof described what it means for a search to be unavoidable; Dodgson’s rule is a voting rule with one built in.

This was the first voting rule shown to be computationally hard, and it has become the standard example of a rule whose definition is transparent and whose outcome cannot, in general, be found.

How often other rules agree #

Dodgson’s rule is Condorcet-consistent: when a Condorcet winner exists, its score is zero and it wins. So the rule only has work to do on electorates without one, and on those the question is how often other rules choose the same candidate.

The answer is not what the definitions suggest. Copeland’s rule — count the contests each candidate wins — is built from the same head-to-head table as Dodgson’s, and yet it agrees with Dodgson only about half the time on these electorates. The reason is ties: without a Condorcet winner, four candidates in a cycle often win the same number of contests, and Copeland cannot choose among them. The Borda count, which never looks at the head-to-head table at all, agrees five times in six, because the candidate needing the fewest swaps is usually the one standing highest on the ballots overall.

With five candidates, Copeland ties less often and agrees more; plurality, which reads only first choices, agrees less. Borda and Dodgson agree remarkably often for rules built on different principles, and the reason is that both reward candidates who are ranked high by many voters — Dodgson because such a candidate needs short lifts, Borda because such a candidate collects points.

A shortcut that becomes exact #

If the exact count is hard, a cruder one may do. Nicolaus Tideman proposed ranking candidates simply by the votes still to win, ignoring the question of whether the necessary swaps are available where they are needed.

The shortcut is right about half the time with seven voters and four times in five with thirty-five. The trend is not an accident of the sample. John McCabe-Dansted, Geoffrey Pritchard and Arkadii Slinko proved in 2008 that, when voters rank candidates uniformly at random, the probability that the two rules agree tends to one as the electorate grows. The intuition is visible in the margins: with many voters, every candidate stands directly above every other on many ballots, so the swaps needed against each rival can almost always be found where they cost exactly one, and the score equals the votes still to win.

The hard problem is hard only on small, awkward electorates — or on electorates built to be hard, which is where the complexity proofs live. A rule that is intractable in the worst case can be almost always easy in the typical case, and here the easy answer is a count anyone can do from the head-to-head table.

When the table is a cycle #

Every electorate the rule has work to do on has a cycle somewhere in its head-to-head table, since an electorate without a Condorcet winner must contain one: follow each candidate to one that beats it, and eventually a candidate repeats. The majority that goes in a circle drew the smallest such cycle, and how often the majority goes in a circle counted how often random electorates produce one — about one in eleven for three candidates, rising with more.

Dodgson’s rule can be read as a way of breaking the cycle at its weakest point. In the figure’s electorate the cycle runs through A, B and C, and the weakest link is C’s one-vote win over A; a single swap on a single ballot reverses it, and with that link broken A beats everyone. Rules that break cycles at their weakest links — ranked pairs, the Schulze method — work on the table alone and are computed quickly; Dodgson’s goes back to the ballots, and pays for it in computation.

What Dodgson was after #

Dodgson’s pamphlets — three of them, written between 1873 and 1876 — were practical documents, about electing fellows and choosing between building plans, and they are a remarkable anticipation of the modern subject. He noticed cycles in the majority relation independently of Condorcet, whose work he appears not to have known. He analysed the Borda count and rejected it for being too easy to manipulate by insincere ranking, the concern a lie that pays made precise. And he proposed his own method as the most natural extension of majority rule to the cases where majority rule fails.

The idea behind it — elect the candidate that the smallest change to the ballots would make the Condorcet winner — has become a template. Rules defined as the distance to a consensus of some kind, with the distance and the consensus chosen differently, form a family that includes Kemeny’s rule, whose ranking closest to all the ballots the nearest consistent verdict found for judgements, and Young’s rule, which deletes voters instead of swapping names. Dodgson’s is the one in which the consensus is a single winner and the distance is the number of adjacent swaps.

Where the rule misbehaves #

A rule that picks the nearest Condorcet winner sounds as principled as any, and it still has flaws, discovered long after Dodgson.

Peter Fishburn pointed out in 1977 that Dodgson’s rule is not homogeneous: replacing every ballot by several copies of itself, which leaves every proportion unchanged, can change the Dodgson winner. The reason is visible in the construction of the score. Copying multiplies every margin, and so multiplies every deficit — but not exactly, because the number of voters to be won over is rounded up to a whole number at each rival, and rounding does not commute with multiplication. The examples are not small: among random electorates of four or five candidates and up to eleven voters, copying every ballot two, three or four times leaves the winner unchanged every time, and the known examples use larger, specially built profiles.

Dodgson’s rule also fails a condition the Borda count meets: that a candidate who wins in each of two separate electorates also wins when they are pooled. This is not a defect peculiar to Dodgson. Peyton Young and Arthur Levenglick showed in 1978 that no rule that always elects a Condorcet winner can satisfy that pooling condition, so the choice between Condorcet-consistency and consistency under pooling is forced on every rule, and Dodgson’s makes the first choice. The two families — rules that honour head-to-head majorities, and rules like Borda’s that add up positions — cannot be reconciled, which is one more instance of the pattern four conditions, and no rule that has all of them established.

The rule does satisfy the simplest kind of monotonicity: moving the winner up a place on some ballot cannot make it lose, since that swap can only lower its own score and cannot lower any rival’s.

What the figures can and cannot show #

The scores are exact for the electorates drawn. Each is computed by a search over every way of lifting the candidate on every ballot, organised so that no combination is missed, and the winning candidate’s swaps are applied to the ballots and checked to make it beat every rival.

The agreement rates are samples. They come from electorates in which every voter ranks the candidates uniformly at random — the impartial culture model — which is a convenient benchmark and a poor model of real voters, who share views. On real electorates, with Condorcet winners far more common, Dodgson’s rule has nothing to do most of the time. A model in which voters share a view of which candidate is best, as a majority wiser than its members assumed for judgements of fact, would make Condorcet winners the rule and the disagreements between rules rarer still.

The complexity is not drawn. Four candidates make a small search; the hardness theorem is about the growth of the search with the number of candidates, which no figure of a single electorate can show.

Still open: how close a fast rule can come #

Since exact Dodgson winners cannot be computed efficiently in general, the natural question is how well they can be approximated. Scores can be approximated within a factor that grows like the logarithm of the number of candidates, by methods from the theory of set cover, and Ioannis Caragiannis and colleagues showed in 2009 that no efficient method does much better unless P equals NP — so the approximability of the score is settled up to constants.

What is not settled is the social-choice question hiding behind it. An approximation algorithm is itself a voting rule, and Caragiannis and his coauthors asked for approximations that also keep Dodgson’s good properties, such as monotonicity and Condorcet-consistency, and found that some combinations of accuracy and property are achievable and others are provably not. Which properties a fast rule can keep while staying close to Dodgson’s is only partly mapped, and on typical electorates, where the simple count of votes still to win is almost always right, the gap between the worst case and the usual case is itself not well understood.

The nearest winner #

The habit worth keeping is to ask of a definition whether it can be computed.

Dodgson’s rule answers a natural question — which candidate is closest to beating everyone — with a natural measure. The measure turns out to require a search that no efficient method can shortcut in general. Yet on the electorates that arise from random voting, a count anyone can make from the head-to-head table gives the same answer most of the time, and almost always once the electorate is large. A rule can be intractable and still almost always easy, and the difference between those two statements is the difference between the worst case and the typical one.