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.
The purpose of 4 is partly to give a definite winner, but also to create a small incentive to vote early.  The purpose of 2 is to allow coordination, so that the result should end up in an equilibrium (if there is one) or a near-equilibrium; if the voters are about to settle on a bad outcome because they have mistaken beliefs about who is winning, they should see that in the early returns and be able to change their votes in light of the new information.  (1 also can be viewed as having this purpose, insofar as single-preference voting tends to have bad equilibria; single-preference voting would be enough to thwart the rest of the design, which would simply lead voters to lock in to some equilibrium, but quite possibly the wrong one.)  I would presume, then, that this system leads to a Condorcet winner where one exists; there remains the question, though, of choosing a winner when there is no such candidate.  The purpose of 3 is to allow the final vote to be taken under some kind of fairly shared and fairly accurate public belief about who the most popular candidates are; rather than having people race to change their votes at the last minute (again, also part of the reason for 4), I want the decision to be made on intensity of preference: e.g. which do you prefer, your second choice of the 3 viable candidates, or a 50% chance of your first choice and a 50% chance of your third choice?  On some level, I would like to take account of intensity of preferences more generally, but more generally attempts to do so tend to lead to strategizing that undermines the attempt; in the case in which there is no Condorcet winner, the proposed program is a way to do so that should be robust to attempts at strategy.

* It's worth noting that the three criteria are related to strategy-proofness in an important way. If everyone knows what votes everyone else is casting, any system designed such that the voter will report his true preferences regardless of what everyone else's vote is must obey the first two of Arrow's criteria. In more general settings it is convenient to suppose that the voting system itself does any necessary "strategizing" — if a voting system would reward a voter with one set of preferences for reporting a different set of preferences, the system should simply treat a report of the first sort as a report of the second sort, so that the voters can simply report honestly.

[2]The former is certainly more straightforward where there are no secret ballots; in the case of the latter, I'm imagining you watch someone walk into a voting booth and see a candidate's total go up as they vote and infer how they voted. In a large election with computerized voting, you could allow the computer to keep track of your current vote, allowing you to change it; then you just have to trust that this will stay anonymous. Also in a large election, many people will be voting at about the same time, so the privacy concern is reduced; in addition, instead of releasing vote totals continuously, you could release them every few minutes, for example. Finally, I would note that a system of daily tracking polls to some extent effects a system like this; indeed, if we could just get tracking pollsters to ask "Is your support strategic, and, if it is, what candidates do you prefer to the one you're voting for?", most of my idea would be implemented.


Clay Shentrup said...

You never talked about Bayesian Regret.

The measure of a voting system's performance is "Bayesian Regret". Approval Voting is basically the second best voting system.

The problem with historical analysis of voting methods, prior to modern understanding of Bayesian Regret, is that it's based on totally subjective criteria.

dWj said...

Range voting with strategic voters is equivalent to approval voting; in practice, I expect range voting would do better, insofar as people are sometimes less strategic than they should be. It is a bit more complicated, though, than approval voting; one of the things I like about approval voting is that it is such a small change from what people are used to doing.

I would expect votes in a legislature or other smallish body to, after time, become increasingly strategic. In the general population, I would expect range voting to still maintain a small advantage over approval voting. I think it would be a harder sell, though.

I'm not extremely impressed by Bayesian Regret, but I'll think about it. In particular, how sensitive are the results to your assumptions on the distributions of preferences? I'll go back and reread your page, hopefully later this week, though I might get more less busy in a month or two than I will this week.