## Thursday, August 23, 2012

### voting for a single winner

In a situation in which people are voting for one outcome out of several choices, there is some question as to how we should go about aggregating people's preferences.  Elections in the United States typically ask each person to vote for one candidate, and the candidate with the largest number of votes wins.  This leads to phenomena like "vote-splitting", where two similar candidates may each get 30% of the vote while a third candidate gets 40%; if either of the similar candidates had dropped out, the other would have won.  This feels wrong, but it turns out that it is generically hard to avoid this problem; in particular, as wikipedia explains it,
In short, the theorem states that no rank-order voting system can be designed that satisfies these three "fairness" criteria:
• If every voter prefers alternative X over alternative Y, then the group prefers X over Y.
• If every voter's preference between X and Y remains unchanged, then the group's preference between X and Y will also remain unchanged (even if voters' preferences between other pairs like X and Z, Y and Z, or Z and W change).
• There is no "dictator": no single voter possesses the power to always determine the group's preference.
The second condition is essentially this vote-splitting criterion.  Note that the theorem worked with more flexible ballots than we usually use — Arrow would ask voters to rank all of their alternatives, rather than only state a first choice — and supposes that the voter reports preferences honestly instead of strategizing.*

In somewhat recent work, it has been noted that in practice preferences might be likely to be constrained somewhat; if there are five candidates, for example, it might be odd to see a voter whose first choice is the most conservative candidate and whose second is the most liberal.  If you rule out preferences of this sort, then you can do much better; in particular, taking the ordered ballots from each voter, you can infer, for each pair of candidates, which candidate would win in a two-candidate "run-off", and if one candidate beats all of the other candidates in such pair-wise elections, it makes sense to call that candidate the winner.  This system satisfies all of Arrow's criteria, except that it can sometimes fail to choose a winner (if candidate A beats B, B beats C, but C beats A in pairwise elections).  When it does choose a winner, we call that winner the "Condorcet winner", and in such situations it tends to be fairly attractive — for example, in a lot of cases it helps voters find compromise candidates who might be ignored in a single-preference voting system.  It turns out that it is necessary for some voters to have "odd preferences" in order for there not to be a Condorcet winner; in fact, among voting systems that satisfy Arrow's criteria for some set of allowable preferences, this system is the most permissive.

As an example, suppose about 40% of the voters prefer the liberal candidate, about 40% prefer the conservative candidate, and 20% prefer a "moderate" candidate.  Presumably, in a two-candidate race, the moderate candidate would beat either of the others.  In a three-candidate race, if it becomes conventional wisdom that the moderate candidate can't win, voters with a single-preference vote strategically shift toward whichever of the "major" candidates they prefer.  Note that, if all voters believe that the conservative candidate can't win, then the moderate candidate will pick up the 60% vote and win.  The main problem with the single-preference vote is that there are self-fulfilling beliefs that lead to other outcomes.  Asking each voter for a ranking of candidates allows the voting system to work out the better outcome itself.

It seems attractive, then, to get people away from single-preference voting, and the real enthusiasts of voting reform tend to be big proponents of ordered ballots.  They are used successfully by Cambridge, MA, for its elections for city council and school board, but there are much less radical changes that can yield a lot of benefits relative to our current single-preference system; in particular, instead of saying "vote for one candidate", we can say "vote for as many candidates as you like".  If there are five candidates and you really dislike one of them, and don't have strong preferences among the other four, you can effectively vote "against" that one candidate (by voting for all of the others).  The system is, however, typically called "approval voting", with the idea that you indicate which candidates receive your approval.  In our above example, if it is believed that the moderate candidate has no chance, then the moderate voters can continue to vote for their preferred candidate, even as they also vote strategically for one of the major candidates; if it looks like the liberal candidate has a good chance of winning, then the conservative voters, too, will vote for the moderate candidate in addition to their own, and, conversely, if it looks like the conservative candidate has a good chance of winning, the liberals will vote for the moderate as well as the liberal.  There is no set of common, self-fulfilling beliefs in which the moderate fails to win.

A lot of game theory generally and voting theory in particular works in these "full-information" (or "almost full-information") environments, in which all voters have the same beliefs about what the outcome of an election will be, with these beliefs clustered very tightly around the actual outcome; in an election with 1,000,000 votes cast, people might not be quite sure exactly how many votes each candidate will get, but they would be able to guess to within about 1,000 votes.  This is clearly unrealistic; indeed, another problem with the single-preference ballot is that much of the primary system is spent trying to influence beliefs about which candidates are likely to win, and voters spend a lot of their energy trying to form these beliefs and strategizing around them.  Approval voting reduces this problem, but doesn't eliminate it; it is still not that unlikely that, even if there is only one "equilibrium" (i.e. set of self-fulfilling common beliefs) and it has a good outcome, voters with different expectations would find themselves surprised by the outcome and, after improperly strategizing, would effect the wrong result.

Consider, then, an environment in which it's practical to let people change their vote, and in which releasing running vote totals doesn't compromise privacy that we want to protect.[2] I believe in this context -- essentially a full information context -- that approval voting has a unique equilibrium selecting the Condorcet winner if there is one,Update:this turns out to be false. and that it does not have a deterministic equilibrium (i.e. one in which people are practically certain who's going to win) if there is no Condorcet winner.  In this extended-vote format, I would expect the result to stabilize when there is a Condorcet winner, and, when there isn't one, for the "leading candidate" to switch from one candidate to another among a set of candidates with fairly broad support and good compromise qualities, similar to Condorcet winners.  I therefore propose:
1. Allow voting for a fixed period of time, in which voters are free to vote for as many candidates as they want, and may vote or rescind their vote for any candidate at any time in this period.
2. Maintain a public tally of the number of votes for each candidate for the bulk of this period.
3. Stop releasing the public tallies shortly before the close of the voting period.  (I'm imagining something like 15 or 30 seconds in the context of a vote for Speaker of the House, and certainly much longer in anything like a general election; long enough for voters to give a little bit of last-minute strategic thought and to enter their final votes.)
4. In the event of a tie, the last votes to change lose priority; thus if two candidates tie, and they were tied before the last vote change, but the penultimate vote change was for or against one of them, that penultimate change is disallowed.