![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Ranked Choice Voting: yay, sorta
So yesterday New York City's voters overwhelmingly approved an Instant Runoff Voting system. It only applies to primary and special elections, not general elections, and it only applies to certain city offices, not state or Federal offices (I presume those would require action at the State level, which is actually possible now that Democrats control both houses of the State legislature). And I'm sure it'll be an improvement over the current system.
It bothers me that so much media coverage calls this "ranked choice voting, also known as instant runoff voting." Those are not the same thing. Ranked choice voting, in a rational world, means that the voters cast ranked ballots. Instant runoff voting is one of the possible ways to count ranked ballots, and not a particularly good one; the other two well-known ways to count ranked ballots, the Borda system and the Condorcet system, are better in almost every way.
OK, why is a single-vote system bad? The most well-known reason is vote-splitting. Imagine there are six candidates: five nearly indistinguishable candidates from the Sane Party (which, being sane, gets 80% popular support for its positions) and one from the Loony Party (with 20% popular support for its positions). In a single-vote system, the five Sane candidates may split their 80% popular support, each get 16%, and the one Loony candidate wins with 20%. A runoff system avoids this scenario (at the expense of running an additional election), but is still susceptible to a scenario involving several Sane candidates, one Loony candidate, and one Bonkers candidate: the runoff can be between the Loony and the Bonkers, even though very few voters support either of them. The traditional solution to this problem has been political parties, which choose (whether by primary, caucus, or smoke-filled room) a single nominee from their field of possibilities, so there aren't several similar candidates running against one another. The downsides are substantial: the cost of running a separate election just to help the political parties decide whom they're going to put into the general election (and why do taxpayers pay for that, rather than the parties?), and the well-known phenomenon of candidates running to the extremes in primaries and suddenly moderating all their positions as soon as they win nomination, and the expense and old-boy corruption historically associated with party machines. Ranked ballots are an alternative solution to the vote-splitting problem, allowing several similar candidates to be in the same race without significantly hurting one another. In my ideal world, ranked ballots would make it unnecessary to have political parties or primaries at all: you just put all the candidates into the general election and have the voters decide. Yesterday's NYC referendum doesn't quite reach that desirable outcome, because it doesn't apply to general elections, but perhaps that can be a few years from now.
Another problem with a single-vote system is "strategic" or "insincere" voting: it encourages voters to vote not for the candidate they most want to win, but the candidate they most want to win from among those they've been told have a realistic chance of winning, which in turn depends on which media outlets they watch/read and which public-opinion polls they believe. Every voter has to cast a vote based not on hir own preferences, but on hir own beliefs about other voters' preferences. How can a "democratic" voting system possibly do what the voters want if the voters aren't even telling it the truth about what they want? (The "realistic chance of winning" filter also makes it almost impossible for a third party to win, no matter how popular its positions are.) With a ranked ballot, there are fewer and rarer scenarios in which strategic voting helps you; lying about what you want is harder and more complicated, while telling the truth about what you want is easier, so people are more likely to do it. Instant Runoff is still fairly susceptible to strategic voting; Borda much less so; and Condorcet even less so.
A third problem with single-vote systems is that they weight a candidate's positives much more heavily than the candidate's negatives. (A hypothetical single-vote system in which you vote against your least favorite candidate, and the candidate with the fewest anti-votes wins, would have the opposite problem, weighting a candidate's negatives much more heavily than the candidate's positives.) In a single-vote system, the difference between your first choice and your second choice is everything, while the difference between your second choice and your tenth is ignored completely. The result is that a candidate with the support of a strong minority can win despite being despised (ranked last) by a solid majority of voters; a divisive, factional candidate will beat a boring, consensus candidate every time.
Instant runoff has the same problem, slightly less badly, because it doesn't look at the difference between your second choice and your tenth until your first choice is eliminated. If your first choice survives to the final round, IRV doesn't know whether the other candidate in that round was your second choice ("almost as good") or your last choice ("over my dead body"). Imagine an election in which Anne, Bob, and Charlie split the first-place votes evenly, while Denise is everybody's second choice. A majority of voters (all the Bob and Charlie partisans) prefer Denise over Anne; a different majority prefer Denise over Bob; a third majority prefer Denise over Charlie; and Denise is the most likely to be able to run a functioning government because nobody hates her; but Denise is eliminated at the first round because she didn't get any first-place votes.
By contrast, in the Borda and Condorcet systems, the difference between your first and second choices carries the same weight as the difference between your ninth and tenth choices; you can express your extreme disapproval of a candidate by ranking that candidate last, and it matters that you did so. As a result, Denise wins the above scenario, and a majority of voters are happier with the outcome.
Then there are the mathematical properties: common-sense things mathematicians would like to see in a voting system, such as "if your preferences and mine are exact opposites, your vote and mine cancel one another out." Due to the asymmetry of weights discussed in the previous two paragraphs, this isn't true in a single-vote system, nor in IRV, but it is true in both Borda and Condorcet. And single-vote and IRV are subject to "kingmakers": the presence or absence of one non-winning candidate can change who does win, which is almost impossible in Borda, and I think completely impossible in Condorcet.
Finally, there are the practicalities of counting ballots. A single-vote system is easy to count: maintain a counter (initially zero) for each candidate, and for each ballot, increment the counter for the candidate chosen on that ballot; then see which candidate has the most votes. It's a linear-time algorithm (more precisely O(V + C), where V is the number of voters and C the number of candidates), and easily parallelized so you can do a count within each precinct, report a number for each candidate (C numbers to report), add them up and get valid city-wide, state-wide, or nation-wide results.
Instant runoff is much trickier. There are two obvious algorithms. In one algorithm, you loop through all the ballots, incrementing first-place counters as above in O(V) time, then in O(C) time find out which candidate has the most and fewest votes and whether the most votes is more than 50%, but if not, you then have to find all the ballots whose first choice was the least-popular, and go through them again, and perhaps do that again, and again, until somebody has 50%+1. Finding the number of first-place votes for each candidate is still parallelizable, but you can't do the "instant runoff" part locally because you don't know which candidate to eliminate until you've finished the global count; then you have to tell each precinct which candidate to eliminate and have them start all over, and possibly repeat this up to C-2 times. Total computation time O(C*(V+C)), with O(C) rounds of communication. If you want to know who came in second, third, etc. you need to do even more rounds of communication.
In the other algorithm, each precinct counts how many votes there were for each possible permutation of candidates, and reports this number to a central tabulator, which adds up the number for each permutation, and this is enough information to find a winner. But this requires reporting and adding up C! buckets, not only C buckets.
In the Condorcet system, you loop over each pair (X,Y) of candidates, and decide whether a majority of voters prefer X over Y or Y over X. This produces (in time O(C2V)) a bunch of pairwise win/lose choices, and a standard tournament algorithm (in time O(C)) finds who beat everybody else. Unfortunately, it's possible that nobody beat everybody else: it's possible for Anne to beat Bob, Bob to beat Charlie, and Charlie to beat Anne, resulting in a three-way tie which is the biggest disadvantage of the Condorcet system. (There are ways to break the tie by counting by how many votes Anne beat Bob, Bob beat Charlie, and Charlie beat Anne, but they make the system more complex to describe and analyze.) The system is moderately parallelizable: each precinct counts, for each pair (X,Y), how many voters preferred X over Y and how many Y over X; these O(C2) numbers can be reported to a central tabulator, which adds up the numbers for each pair and has enough information to find a winner.
In the Borda system, you maintain a counter (initially zero) for each candidate, and for each ballot, increment each candidate's counter by a number of "points" corresponding to the candidate's rank: if the voter ranked five candidates, give them 5, 4, 3, 2, and 1 points respectively. This takes O(C*V) time, but the O(C) factor is localized to a single ballot, not multiple rounds as in IRV. Then in O(C) additional time, find which candidate has the most points, and declare that candidate the winner. The system is easily parallelizable: each precinct computes a point total for each candidate, reports these C numbers to a central tabulator, the central tabulator adds them up and has enough information to find a winner (and indeed to rank all the candidates). There are only C numbers to report (although they're O(C) times larger), rather than C choose 2 or C factorial.
For a 10-candidate race, single-vote or Borda requires reporting 10 numbers from each precinct to central; Condorcet requires reporting 45 numbers; IRV with the first algorithm requires reporting 10 numbers but possibly having each precinct go through its ballots up to 7 more times; and IRV with the second algorithm requires that each precinct report over 3 million numbers (most of which may be zeroes) to the central tabulator, regardless of how many voters are in the precinct.
So, "yay, sorta". A definite step in the right direction, but if we were improving our voting system, why couldn't we have improved it more?
ETA: see today's XKCD.
It bothers me that so much media coverage calls this "ranked choice voting, also known as instant runoff voting." Those are not the same thing. Ranked choice voting, in a rational world, means that the voters cast ranked ballots. Instant runoff voting is one of the possible ways to count ranked ballots, and not a particularly good one; the other two well-known ways to count ranked ballots, the Borda system and the Condorcet system, are better in almost every way.
Vote-splitting
OK, why is a single-vote system bad? The most well-known reason is vote-splitting. Imagine there are six candidates: five nearly indistinguishable candidates from the Sane Party (which, being sane, gets 80% popular support for its positions) and one from the Loony Party (with 20% popular support for its positions). In a single-vote system, the five Sane candidates may split their 80% popular support, each get 16%, and the one Loony candidate wins with 20%. A runoff system avoids this scenario (at the expense of running an additional election), but is still susceptible to a scenario involving several Sane candidates, one Loony candidate, and one Bonkers candidate: the runoff can be between the Loony and the Bonkers, even though very few voters support either of them. The traditional solution to this problem has been political parties, which choose (whether by primary, caucus, or smoke-filled room) a single nominee from their field of possibilities, so there aren't several similar candidates running against one another. The downsides are substantial: the cost of running a separate election just to help the political parties decide whom they're going to put into the general election (and why do taxpayers pay for that, rather than the parties?), and the well-known phenomenon of candidates running to the extremes in primaries and suddenly moderating all their positions as soon as they win nomination, and the expense and old-boy corruption historically associated with party machines. Ranked ballots are an alternative solution to the vote-splitting problem, allowing several similar candidates to be in the same race without significantly hurting one another. In my ideal world, ranked ballots would make it unnecessary to have political parties or primaries at all: you just put all the candidates into the general election and have the voters decide. Yesterday's NYC referendum doesn't quite reach that desirable outcome, because it doesn't apply to general elections, but perhaps that can be a few years from now.
Strategic voting
Another problem with a single-vote system is "strategic" or "insincere" voting: it encourages voters to vote not for the candidate they most want to win, but the candidate they most want to win from among those they've been told have a realistic chance of winning, which in turn depends on which media outlets they watch/read and which public-opinion polls they believe. Every voter has to cast a vote based not on hir own preferences, but on hir own beliefs about other voters' preferences. How can a "democratic" voting system possibly do what the voters want if the voters aren't even telling it the truth about what they want? (The "realistic chance of winning" filter also makes it almost impossible for a third party to win, no matter how popular its positions are.) With a ranked ballot, there are fewer and rarer scenarios in which strategic voting helps you; lying about what you want is harder and more complicated, while telling the truth about what you want is easier, so people are more likely to do it. Instant Runoff is still fairly susceptible to strategic voting; Borda much less so; and Condorcet even less so.
Asymmetry of weights
A third problem with single-vote systems is that they weight a candidate's positives much more heavily than the candidate's negatives. (A hypothetical single-vote system in which you vote against your least favorite candidate, and the candidate with the fewest anti-votes wins, would have the opposite problem, weighting a candidate's negatives much more heavily than the candidate's positives.) In a single-vote system, the difference between your first choice and your second choice is everything, while the difference between your second choice and your tenth is ignored completely. The result is that a candidate with the support of a strong minority can win despite being despised (ranked last) by a solid majority of voters; a divisive, factional candidate will beat a boring, consensus candidate every time.
Instant runoff has the same problem, slightly less badly, because it doesn't look at the difference between your second choice and your tenth until your first choice is eliminated. If your first choice survives to the final round, IRV doesn't know whether the other candidate in that round was your second choice ("almost as good") or your last choice ("over my dead body"). Imagine an election in which Anne, Bob, and Charlie split the first-place votes evenly, while Denise is everybody's second choice. A majority of voters (all the Bob and Charlie partisans) prefer Denise over Anne; a different majority prefer Denise over Bob; a third majority prefer Denise over Charlie; and Denise is the most likely to be able to run a functioning government because nobody hates her; but Denise is eliminated at the first round because she didn't get any first-place votes.
By contrast, in the Borda and Condorcet systems, the difference between your first and second choices carries the same weight as the difference between your ninth and tenth choices; you can express your extreme disapproval of a candidate by ranking that candidate last, and it matters that you did so. As a result, Denise wins the above scenario, and a majority of voters are happier with the outcome.
Mathematical properties
Then there are the mathematical properties: common-sense things mathematicians would like to see in a voting system, such as "if your preferences and mine are exact opposites, your vote and mine cancel one another out." Due to the asymmetry of weights discussed in the previous two paragraphs, this isn't true in a single-vote system, nor in IRV, but it is true in both Borda and Condorcet. And single-vote and IRV are subject to "kingmakers": the presence or absence of one non-winning candidate can change who does win, which is almost impossible in Borda, and I think completely impossible in Condorcet.
Algorithmic efficiency
Finally, there are the practicalities of counting ballots. A single-vote system is easy to count: maintain a counter (initially zero) for each candidate, and for each ballot, increment the counter for the candidate chosen on that ballot; then see which candidate has the most votes. It's a linear-time algorithm (more precisely O(V + C), where V is the number of voters and C the number of candidates), and easily parallelized so you can do a count within each precinct, report a number for each candidate (C numbers to report), add them up and get valid city-wide, state-wide, or nation-wide results.
Instant runoff is much trickier. There are two obvious algorithms. In one algorithm, you loop through all the ballots, incrementing first-place counters as above in O(V) time, then in O(C) time find out which candidate has the most and fewest votes and whether the most votes is more than 50%, but if not, you then have to find all the ballots whose first choice was the least-popular, and go through them again, and perhaps do that again, and again, until somebody has 50%+1. Finding the number of first-place votes for each candidate is still parallelizable, but you can't do the "instant runoff" part locally because you don't know which candidate to eliminate until you've finished the global count; then you have to tell each precinct which candidate to eliminate and have them start all over, and possibly repeat this up to C-2 times. Total computation time O(C*(V+C)), with O(C) rounds of communication. If you want to know who came in second, third, etc. you need to do even more rounds of communication.
In the other algorithm, each precinct counts how many votes there were for each possible permutation of candidates, and reports this number to a central tabulator, which adds up the number for each permutation, and this is enough information to find a winner. But this requires reporting and adding up C! buckets, not only C buckets.
In the Condorcet system, you loop over each pair (X,Y) of candidates, and decide whether a majority of voters prefer X over Y or Y over X. This produces (in time O(C2V)) a bunch of pairwise win/lose choices, and a standard tournament algorithm (in time O(C)) finds who beat everybody else. Unfortunately, it's possible that nobody beat everybody else: it's possible for Anne to beat Bob, Bob to beat Charlie, and Charlie to beat Anne, resulting in a three-way tie which is the biggest disadvantage of the Condorcet system. (There are ways to break the tie by counting by how many votes Anne beat Bob, Bob beat Charlie, and Charlie beat Anne, but they make the system more complex to describe and analyze.) The system is moderately parallelizable: each precinct counts, for each pair (X,Y), how many voters preferred X over Y and how many Y over X; these O(C2) numbers can be reported to a central tabulator, which adds up the numbers for each pair and has enough information to find a winner.
In the Borda system, you maintain a counter (initially zero) for each candidate, and for each ballot, increment each candidate's counter by a number of "points" corresponding to the candidate's rank: if the voter ranked five candidates, give them 5, 4, 3, 2, and 1 points respectively. This takes O(C*V) time, but the O(C) factor is localized to a single ballot, not multiple rounds as in IRV. Then in O(C) additional time, find which candidate has the most points, and declare that candidate the winner. The system is easily parallelizable: each precinct computes a point total for each candidate, reports these C numbers to a central tabulator, the central tabulator adds them up and has enough information to find a winner (and indeed to rank all the candidates). There are only C numbers to report (although they're O(C) times larger), rather than C choose 2 or C factorial.
For a 10-candidate race, single-vote or Borda requires reporting 10 numbers from each precinct to central; Condorcet requires reporting 45 numbers; IRV with the first algorithm requires reporting 10 numbers but possibly having each precinct go through its ballots up to 7 more times; and IRV with the second algorithm requires that each precinct report over 3 million numbers (most of which may be zeroes) to the central tabulator, regardless of how many voters are in the precinct.
So, "yay, sorta". A definite step in the right direction, but if we were improving our voting system, why couldn't we have improved it more?
ETA: see today's XKCD.
no subject
It is unclear to me what happens in our recently adopted system if I rank my four acceptable choices out of six and don't place a 5th. Have I succeeded in not giving any of the others even a fractional vote because I despise both of them, or have I gotten my entire ballot invalidated?
no subject