Impartiality in Tideman's 'Ranked Pairs' Rule

My preferred theory of rational choice is formally very similar to Tideman’s ‘ranked pairs’ voting rule. (This isn’t an accident—my theory is modeled on Tideman’s.) Working through the details in the case of rational choice, I’ve come to think that there’s a slight error in the way that ties are broken in the ‘ranked pairs’ rule. Today’s post explains why I think this and recommends a revision to the tie-breaking procedure.

1. Overview

One nice property of ‘ranked pairs’ is that it is independent of clones. To illustrate: suppose that (contrary to fact), every Democratic voter regards Elizabeth Warren and Bernie Sanders as more similar to each other than they are to any other candidate. That is, suppose that, due to the similarity of their positions, no voter ranks any other candidate between them. While not all voters are indifferent between Bernie and Warren—some prefer Warren and others prefer Bernie—there is no voter who thinks that Bernie is better than Biden, and Warren is worse than Biden. Nor is there any voter who thinks Warren is better than Harris, who is better than Bernie. If that’s so, then Tideman calls Warren and Bernie clones of each other. And the ‘ranked pairs’ rule is independent of clones in the following sense: firstly, under the ‘ranked pairs’ rule, if Biden wins the primary, then he will still win if either Warren or Bernie were to drop out of the race. Secondly, under the ‘ranked pairs’ rule, if either Warren or Bernie wins, then one of them will still win, if either were to drop out of the race. (And in general, what goes for Warren and Bernie goes for any other set of clones, and what goes for Biden goes for any other candidate who is not one of the clones.)

In order for the rule to be independent of clones in general, even when there are certain kinds of ‘ties’, the rule must ‘break’ these ties in a particular way. Zavist and Tideman introduce a method for breaking ties which they call ‘impartial’, and they prove that, if the ranked pairs rule breaks ties in an ‘impartial’ way, then it will be independent of clones in general. (Without the restriction to ‘impartial’ tie breaking, the rule is not independent of clones.)

However, beyond giving it the suggestive name ‘impartiality’, Zavist and Tideman don’t say anything about why we should want a tie-breaking method to be ‘impartial’ in their stipulated sense. And it’s far from obvious. In fact, I think that ‘impartiality’ is about as badly named as a principle could be. What it demands isn’t that you break ties in an impartial way, but rather that you do so in a maximally partial way. The right way to understand the principle is as a demand that ties are broken in such a way as to consistently favor certain candidates over others.

2. The ‘Ranked Pairs’ Rule

Suppose that you are in charge of selecting a candidate for office, the only information about the candidates you have is each voter’s preference ranking over the candidates, and the only thing you care about is respecting ‘the will of the people’. How should you proceed? Who should you pick?

Tideman gives the following advice: if there are more people who prefer candidate $a$ to candidate $b$ than there are people who prefer candidate $b$ to candidate $a$, then the people have expressed a preference for $a$ over $b$. The strength of their preference is given by the size of $a$’s majority over $b$, $M(a, b)$, which is just the number of people who prefer $a$ to $b$, minus the number of people who prefer $b$ to $a$. So, if you care about respecting the will of the people, then you have a pro tanto reason to prefer $a$ to $b$ yourself. And the strength of your reason to prefer $a$ to $b$ is given by $M(a, b)$.

2.1 Avoiding Cycles

I say you have a pro tanto reason to prefer $a$ to $b$ yourself. This reason could be overridden. For you may have an even stronger reason to prefer $b$ to $a$. Let’s see how that could happen: suppose that there are three candidates, $a, b,$ and $c$, and 7 voters. Three voters prefer $a$ to $b$ to $c$. Two prefer $b$ to $c$ to $a$. And two prefer $c$ to $a$ to $b$.

$$ \begin{array}{r c c c} \text{# of Voters:} & 3 & 2 & 2 \\
1st & a & b & c \\
2nd & b & c & a \\
3rd & c & a & b \end{array} $$

Then, $M(a, b) = 3$, $M(b, c) = 3$, and $M(c, a) =1$. So, you have pro tanto reason to prefer $a$ to $b$, to prefer $b$ to $c$, and to prefer $c$ to $a$. But these preferences are cyclic: they form the cycle $a \succ b \succ c \succ a$. Even if we suppose that cyclic preferences like these are possible, your goal to select a single candidate, so cyclic preferences won’t do. You need a winner, or at least a set of winners to randomly choose between, so you need some candidate or candidates to be at the top of your preferences. And no option is at the top of a cyclic preference ordering.

In this case, Tideman says that you have reason to prefer $a$ to $b$, you have reason to prefer $b$ to $c$, and you have reason to prefer $c$ to $a$. But the reason you have to prefer $c$ to $a$ is weaker that the reason you have to prefer $a$ to $b$ and $b$ to $c$. Since your only goal is respecting the will of the people, and since the size of a candidate $x$’s majority over $y$ represents how strongly the people prefer $x$ to $y$, you have most reason to honor the preferences corresponding to the largest majorities. Since $M(a, b)$ and $M(b, c)$ are both larger than $M(c, a)$, you should end up with the preference ordering $a \succ b \succ c$, and you should select $a$ for the position.

More generally, Tideman’s advice is this: draw up a list of the preferences which the people have expressed. That is, for every pair of distinct options $x, y$, if $M(x, y) > 0$, then write ‘$x \succ y$’ on your list. And order the preferences on your list by the size of the majorities which speak in their favor. That is, for any options $a, b, x, y,$ with $a \neq x$ and $b \neq y$: if $M(a, x) > M(b, y) > 0$, then place ‘$a \succ x$’ before ‘$b \succ y$’ on your list. When you’ve completed your list, start at the top and work your way down. As soon as you encounter a preference which, together with the preferences above it on your list, would lead to a cycle, strike that preference from your list. You have a pro tanto reason to honor that preference, but that pro tanto reason has been overridden by the stronger reasons above it. Continue on in this way, striking any preference which, together with the unstruck preferences above, would lead to a cycle. When you reach the bottom of the list, the unstruck preferences which remains are yours.

2.2 Breaking Ties

There are two ways that this procedure could result in ‘ties’. In the first place, it could be that, for some distinct $x$ and $y$, $M(x, y) = 0$. Call this ‘a tie between candidates’. In the second place, it could be that, for some options $a, b, x, y$ with $a \neq x$ and $b \neq y$, $M(a, x) = M(b, y)$, so the size of $a$’s majority over $x$ is the same as $b$’s majority over $y$, and you face a choice of which preference to put first on your list. Call this ‘a tie between preferences’.

In general, how you decide to break a tie between preferences can end up making a difference with respect to which candidate wins. For an illustration, suppose there are three voters and three candidates, $a, b,$ and $c$. One voter prefers $a$ to $b$ to $c$; one prefers $b$ to $c$ to $a$, and one prefers $c$ to $a$ to $b$.

$$ \begin{array}{r c c c} \text{# of Voters:} & 1 & 1 & 1 \\
1st & a & b & c \\
2nd & b & c & a \\
3rd & c & a & b \end{array} $$

Then, $M(a, b) = 1$, $M(b, c) = 1$, and $M(c, a) = 1$. So you have pro tanto reason to prefer $a$ to $b$, pro tanto reason to prefer $b$ to $c$, and pro tanto reason to prefer $c$ to $a$. None of these reasons are any stronger than the others, so we have a tie between preferences, and you have a free choice of which preference to place last on your list: ‘$a \succ b$‘, ‘$b \succ c$‘, or ‘$c \succ a$‘. If ‘$a \succ b$’ is last, then it will be struck, and you’ll end up with the preference ordering $b \succ c \succ a$. If ‘$b \succ c$’ is last, then it will be struck, and you’ll end up with the preference ordering $c \succ a \succ b$. If ‘$c \succ a$’ is last, then it will be struck, and you’ll end up with the preference ordering $a \succ b \succ c$.

Tideman suggests a simple approach to breaking ties between preferences: simply consider all possible ways of breaking these ties. That is: consider every possible list you could draw up consistent with the requirement that, if $M(a, x) > M(b, y) >0$, then ‘$a \succ x$’ comes before ‘$b \succ y$’ on your list. Then, running through the procedure described above, determine a final preference ordering from each such list. Gather all of these preference orderings together. If an option is at the top of at least one of these preference orderings, then it is a potential winner. If there is more than one potential winner, we randomly select one voter to pick a winner from amongst these potential winners. (Tideman deals with ties between candidates by simply ignoring them. He says to simply not bother writing down any preferences for tied candidates on your list. If, after you’ve struck the strict preferences which would lead to cycles, there are multiple preference orderings compatible with the unstruck preference on your list, then anyone at the top of one of these preferences orderings is a potential winner, and you proceed as before.)

2.3 Clone-Independence and Impartiality

Tideman conjectures that this tie-breaking procedure will be independent of clones. However, Zavist and Tideman provide a counterexample in which introducing a clone transforms a candidate from a potential winner into a definite loser.

Zavist and Tideman go on to give a diagnosis of why the original tie-breaking violated the independence of clones, and they additionally provide a new ‘tie-breaking’ procedure which will never violate it. First, I’ll present their new procedure, and then I’ll introduce their diagnosis.

Zavist and Tideman propose the following procedure for breaking ties both between candidates and between preferences. First, a single voter is randomly chosen. That voter’s preference ordering is selected. If the voter’s preferences include any indifferences between candidates, then those indifferences are settled one way or another using a coin flip, so that we end up with a total strict order over candidates. Call this ‘the tie-breaking’ ordering. The tie-breaking ordering is used to break both ties between candidates and ties between preferences. If $M(a, b) = 0$, then we go to the tie-breaking ordering to decide which preference to place on our list. If the tie breaking-ordering has $a$ preferred to $b$, then ‘$a \succ b$’ is placed on your list. If the tie-breaking ordering has $b$ preferred to $a$, then ‘$b \succ a$’ is placed on your list.

Turn now to ties between preferences. Suppose that, for some $a, b, x, y$ such that $a \neq x$ and $b \neq y$, $M(a, x) = M(b, y) > 0$, so that you face a free choice about whether to place ‘$a \succ x$’ or ‘$b \succ y$’ before the other on the list. Which is placed first is settled by the tie-breaking ordering. If $a$ is before $b$ in the tie-breaking ordering, then ‘$a \succ x$’ comes before ‘$b \succ y$‘. If $b$ comes before $a$, then ‘$b \succ y$’ comes before ‘$a \succ x$‘. What if $a = b$? In that case, place ‘$a \succ x$’ before ‘$b \succ y$’ iff $x$ comes before $y$ in the tie-breaking ordering.

Zavist and Tideman recommend this method for breaking ties between preferences, but the only property of it which they need in order to guarantee that the ‘Ranked Pairs’ method is independent of clones is that the tie-breaking method is impartial, in the following sense

Impartiality. A method of breaking ties between preferences is impartial iff, for any $a, b, x, y$, with $a, b \neq x, y$, $M(a, x) = M(b, x)$, and $M(a, y) = M(b, y)$: if ‘$a \succ x$’ is placed above ‘$b \succ x$‘, then ‘$a \succ y$’ is placed above ‘$b \succ y$‘, too.

Zavist and Tideman’s method of breaking ties between preferences will count as impartial in this sense, since, if the preference ‘$a \succ x$’ is placed above ‘$b \succ x$‘, then the tie-breaking ordering must place $a$ above $b$. And, in that case, ‘$a \succ y$’ will be placed above ‘$b \succ y$‘.

Zavist and Tideman prove that, if a method of breaking ties between preferences is impartial, then the ‘ranked pairs’ rule will be independent of clones in general.

3 Is Impartiality Properly So-Called?

In this section, I’m going to suggest that the principle 'impartiality' is badly mis-named. Far from imposing a constraint of impartiality, it imposes the constraint that you break ties in a way which is consistently partial towards certain candidates.

3.2 ‘Impartiality’ Actually Demands Consistent Partiality

To better understand what impartiality requires of a tie-breaking procedure, let’s think about what it means to break a tie between $a \succ x$ and $b \succ x$ so as to place $a \succ x$ above $b \succ x$. Placing $a \succ x$ higher on your list has the effect of protecting the preference $a \succ x$. For, if $a \succ x$ is higher on this list, then there are fewer preferences above, and so it is less likely to create a cycle with those preferences and end up being struck. On the other hand, placing $b \succ x$ lower on your list is effectively endangering the preference $b \succ x$. For if $b \succ x$ is lower on the list, then there are more preferences above it, and so it is more likely to lead to a cycle with those preferences and end up being struck.

Suppose that $a \succ x$ could potentially lead to a cycle. Then, if this preference is struck, $a$ will end up dispreferred to every other candidate in the potential cycle. (Since $a \succ x$ would lead to a cycle, were it not struck, there are candidates $c_1, c_2, \dots, c_N$ such that $x \succ c_1 \succ c_2 \succ \dots \succ c_N \succ a$. And if $a \succ x$ is struck, then all of these preferences must be unstruck above it. So $a$ ends up on the bottom of this potential cycle.) On the other hand, if $a$ is not struck, then $a$ will end up preferred to at least one of the other candidates in the potential cycle. So: placing $a \succ x$ higher on your list is a way of favoring $a$. For the same reason, placing $a \succ x$ lower on your list is a way of disfavoring $a$.

So: making the choice to place $a \succ x$ above $b \succ x$ is doing $a$ a favor and doing $b$ a disservice. Placing $a \succ x$ above $b \succ x$ expresses partiality towards $a$ over $b$.

And, in these terms, what Zavist and Tideman’s ‘impartiality’ tells us is this: if you break one tie in a way that expresses partiality for $a$ over $b$, then you must break all ties in a way that expresses partiality for $a$ over $b$. It imposes a kind of consistency requirement on a tie-breaking method. The constraint says: you’re only allowed to break ties in a way that will consistently favor one candidate over another. You’re allowed to break ties in such a way that you’ll always advantage $a$ over $b$, and you’re allowed to break ties in such a way that you’ll always advantage $b$ over $a$, but you’re not allowed to break ties in such a way that you sometimes favor $a$ over $b$ and other times favor $b$ over $a$.

So I think that the principle is better called “consistent partiality” than “impartiality”. The principle doesn’t seem to have anything at all to do with treating all candidates equally; quite the reverse. This is a problem for the principle’s name, but I don’t think it’s a problem for the principle itself. This kind of partiality is exactly what we should want from a tie-breaking procedure—the whole point of the tie-breaking procedure is to treat the tied candidates unequally, to show some candidate unearned favor. What the principle asks of us is just that we do this in a consistent way, showing the same candidates unearned favor with each tie we break.

3.3 Zavist and Tideman’s Tie-Breaking Method isn’t Consistently Partial

If we understand the principle as requiring that ties be broken in a consistent way, then it’s worth noting that Zavist and Tideman’s own tie-breaking method is not consistent in this sense—in some cases, it will favor $a$ over $b$; while, in others, it favors $b$ over $a$.

Recall: if there are any ties, then a single voter is randomly chosen. If that voter is indifferent between any candidates, then coin flips are used to arrive at a strict total order. If there are any options $x,y$ such that $M(x, y) = 0$, then we use this random voter’s preferences to determine whether to include $x \succ y$ or $y \succ x$ on our initial list. If there are ties between preferences, then we use this random tie-breaking voter’s preferences to settle the ties in the following way: if $M(a, x) = M(b, y) >0$, then:

  1. if $a \neq b$, then $a \succ x$ comes before $b \succ y$ iff $a$ comes before $b$ in the tie-breaking voter’s preferences.
  2. if $a = b$, then $a \succ x$ comes before $b \succ y$ iff $x$ comes before $y$ in the tie-breaking voter’s preferences.

As I suggested above, (1) uses the tie-breaking voter’s preference of $a$ over $b$ to consistently favor $a$ over $b$ in the breaking of tied preferences. However, (2) is very different. (2) uses the tie-breaking voter’s preference of $x$ over $y$ to consistently favor y over x in the breaking of tied preferences.

By way of explanation: take a preferences $a \succ x$. Suppose that $a \succ x$ could potentially lead to a cycle. Then, if this preference is struck, $x$ will end up preferred to every other candidate in the cycle. Since $a \succ x$ would lead to a cycle, were it not struck, there are candidates $c_1, c_2, \dots, c_N$ such that $x \succ c_1 \succ c_2 \succ \dots \succ c_N \succ a$. And if $a \succ x$ is struck, then all of these preferences must be unstruck above it. So $x$ ends up at the top of this potential cycle. On the other hand, if $a \succ x$ is not struck, then $x$ will end up dispreferred to at least one of the other candidates in the potential cycle. So: place $a \succ x$ lower on your list is a way of favoring $x$. Placing it lower on your list makes it more likely that $a \succ x$ will be struck. This is bad for $a$, but good for $x$.

So what part (2) of Zavist and Tideman’s tie-breaking procedure tells us is this: if you must break a tie between two preferences $a \succ x$ and $a \succ y$, do so in such a way that is good for $x$ and bad for $y$ iff the tie-breaking voter prefers $y$ to $x$. That is: it ends up punishing an option for being preferred by the random tie-breaking voter. This doesn’t seem in the spirit of their principle ‘Impartiality’, once it is properly understood. I think that we should accept the following strengthened form of that principle, which I’ll call ‘consistent partiality‘:

Consistent Partiality. A method of breaking ties between preferences is consistently partial iff, for any $a, b, x, y$, with $a, b \neq x, y$, $M(a, x) = M(b, x)$, and $M(a, y) = M(b, y)$:

  1. if ‘$a \succ x$’ is placed above ‘$b \succ x$‘, then ‘$a \succ y$’ is placed above ‘$b \succ y$‘, too
  2. if ‘$a \succ y$’ is placed above ‘$a \succ x$‘, then ‘$b \succ y$’ is placed above ‘$b \succ x$‘, too

Zavist and Tideman’s tie-breaking method does not satisfy Consistent Partiality. However, this could be easily remedied. We proceed as they did, selecting a random voter whose preferences we wish to use to break ties. We flip a coin to settle any indifferences in the voter’s preferences, and then settle ties between candidates as Zavist and Tideman do. For ties between preferences, we say: if $M(a, x) = M(b, y) >0$, then:

  1. if $a \neq b$, then $a \succ x$ comes before $b \succ y$ iff $a$ comes before $b$ in the tie-breaking voter’s preferences.
  2. if $a = b$, then $a \succ x$ comes before $b \succ y$ iff y comes before x in the tie-breaking voter’s preferences.

The only change is indicated in boldface. I recommend it.