Friday, September 20, 2013

voting with markets

I noted before that one of the problems with some voting systems is their sensitivity to beliefs; in particular, if Borda count is used to elect a single winner, most equilibria have almost all candidates receiving the same number of votes, and if some block of voters believes it knows which candidate is likely to have slightly more votes than others, the vote results will swing dramatically.

Plurality voting, in fact, will tend to have multiple equilibria — if you're not used to game theory, it's worth remembering that "equilibrium" in this context essentially means "self-fulfilling beliefs". In this context, if everyone believes a candidate has no chance of winning, nobody will "waste their vote" on that candidate, and so the candidate has no chance of winning, just as was predicted. In the case of approval voting, giving that candidate a vote, in addition to whichever other candidate(s) might have received your vote, costs you nothing, and, if the candidate is in fact fairly popular, the "equilibrium" in which that candidate was not viable is destroyed; it is no longer self-fulfilling.

The fragility problem, then, is whether almost equilibrium beliefs result in almost equilibrium behavior. Approval voting (generally) has equilibria that are fairly stable, to the point where I think it's frequently reasonable to imagine that voters would know what the final vote totals will look like with enough precision to behave in a way that produces the nearby (and typically in some sense optimal) equilibrium.  I have previously suggested that, in other contexts, that information can be made public through a continuous voting mechanism, provided it is feasible to allow people to vote and then later change those votes.

In some contexts it may not be feasible, and I propose the following mechanism, making explicit (as I often don't, but should always be implicit) that this blog is a brain-stormy sort of place, and I'm not going to apologize for a refusal to defend this proposal in some other venue in the future.[1] So long as some reasonably sized set of agents is able to participate on a continuous basis ahead of time, it only requires that all of the voters participate once, at the end:
  1. Create a "prediction market" in which participants trade contracts, one for each candidate, that provide a fixed payout after the election if that candidate finishes first or second in vote totals.
  2. Some reasonably manipulation-proof means is used to construct a final indicative price pi for each candidate very shortly before the vote is taken.
  3. Each voter casts a ballot consisting of one real number ui for each candidate.
  4. wi=pi(ui-∑j (pj/2) uj) and then vi=wi/√∑jwj2 are calculated for each voter.
  5. Add up the number of votes vi each candidate gets from each voter.
  6. Pay out the contracts, coronate the winner.
One probably wants to put a floor on pi — indeed, you might simply have a market rule that doesn't allow orders that would sell below a certain floor —but the general idea here is that the market figures out who the viable candidates are, and the voters vote, but the voters may cast a lot of votes for (or against) the relatively non-viable candidates without losing many votes to cast for (or against) the viable ones.[2]

It's possible to recast this somewhat by effectively asking the voters for ai with a constraint on ∑i (aipi)2 and then adding up ai/pi, which is essentially vi if voters are optimizing in the way that seems right to me and believe that the pi are their best bet as to the probabilities of "viability"; this presentation has the advantage that the description I gave above is perhaps intuitively clearer, where you can see that voting for or against a candidate with a small value of pi is "cheaper" than for a candidate with a large pi. I prefer it the way I've given it in the numbered list, though, for the reason that I would prefer that the pi encapsulate the necessary strategic information but that voters never even have to take account of it. As I've presented it, provided that a voter's best assessment of the viabilities is the same as that reflected in the market prices, and provided there are enough voters that one voter (or perhaps a small conspiracy of voters) won't appreciably affect the "correct" values of pi, the voter's best strategy doesn't depend on knowing the values of pi; it only depends on the voter's preferences.

[1] As is often the case on this blog, one of the advantages of this proposal is that its drawbacks are fairly obvious; it fixes drawbacks that are important but hidden in other mechanisms. One point perhaps noting is that naive fixes can destroy important features of the solution as presented; if you find a context in which the relevant interests will allow data from a prediction market to be an input into the voting system, and you're worried about manipulation, I would particularly note that simply saying that an election will be re-run if a "nonviable" candidate wins is as likely to introduce bad behavior (by people who want to redo the election) as it is to eliminate it.
[2] Putting too high a floor on pi would make it more costly to vote for or against such a candidate, and could vitiate this feature. The result that I would like to avoid is that one of the "viable" candidates gets a lot of negative votes, most of your "nonviable" candidates get nearly zero votes, and thus your "nonviable" candidates beat the "viable" ones; in equilibrium, presumably the market participants would take account of this possibility, and would start to bid down all but perhaps one candidate — the presumptive winner — and bid up everyone else, in which case we're back in the situation where voters suffer from a great deal of strategic uncertainty.

Wednesday, September 11, 2013

more on voting

There's not, I think, a big new idea here, but a somewhat different presentation of thoughts I've had on voting systems, culminating in a point that I perhaps haven't made in this form before.

Game theory in particular has a long history of focusing on "equilibria" — that is, if everyone has correct beliefs about what everyone else is going to do, everyone will act so as to make the equilibrium come about. "Equilibrium" is essentially a self-fulfilling prophecy. In the context of plurality voting, if groups of voters have preferences over 3 candidates of A>B>C, C>B>A, B>A>C, and B>C>A, with the latter two groups somewhat smaller than the former two groups, then B is the "Condorcet" winner, but if B is expected to lose, B will receive no votes, as a result of which B will lose.  This is the classic failure of plurality voting.

Now, a lot of discussion of voting systems does not involve equilibrium, and the most common game theoretic solution concept — Nash equilibrium — supposes that every voter knows literally the final vote count before it happens, which seems a bit excessive. Much discussion of voting systems supposes almost the opposite — that voters aren't strategic at all, or if they do respond to beliefs about others' likely behavior, do so rather crudely. In particular, some voting systems (plurality among them) are criticized for being subject to "manipulation", which means that, rather than vote for their favorite candidate, voters have an incentive to vote for someone else — perhaps someone with a better chance of winning. A related property of these systems, and a different form for what on some level is the same complaint, is that if voters don't vote strategically, then the outcome doesn't reflect the voters' will.

The inclination of the game theorist is not to care about this. If we've created a system in which you may vote for one of any five candidates, and the winner will be the one with the most votes, a voter whose favorite candidate is Williams may decide that his interests are best served by voting for Johnson. To call the vote for Johnson "strategic" is ultimately to put a layer of interpretation on the action that is not implied by the rules of the voting system itself; a vote for Johnson does not, as we've just established, mean that Johnson is the voter's preferred candidate; it implies that the voter's preferences and beliefs about other's votes are in some set that may have less intuitive appeal. It may well be that this information is more valuable than simply who the voter's favorite candidate is, however, in terms of deciding who should be the winner, and indeed seems more of an indictment of the interpretation of the vote than of the vote or the voting system.  It is worth noting, in fact, that in many contexts it is likely that, in each election, most voters will have much more information about other voters' preferences than whatever committee is initially establishing the voting system does at the time the system is being established; a good system might in fact try to leverage voters' information about each other's preferences to help suss out the most preferred candidate.

Now, strategic voting can become a bigger concern if the outcome of the election will turn out to hinge sensitively on how much strategic information each voter has, and how hard it is to get that.  In particular, if voters find themselves doing more research on which candidates are likely to get votes than on which candidates would make better choices of winner, a lot of effort is being directed in socially useless directions.  Especially in some of the contexts I've suggested — namely where repeated, perhaps almost continuous voting (with totals announced) is practical — the relevant kinds of information may not be hard to gather, in which case the strategic element is fairly costless.  In this context Nash equilibrium and its close relatives becomes a more plausible equilibrium concept.

And here is ultimately where I'm going with this: the real attraction of approval voting over plurality voting is that it tends to have fewer "bad" equilibria.  Generally the equilibrium that is likely to obtain from approval voting will also be an equilibrium of plurality voting; the real benefit of the former over the latter is that approval voting is less likely to have other equilibria, and when plurality voting has other equilibria, they will tend to be "bad" in a fairly objective sense.  Some proponents of approval voting will note that, in the preferred equilibrium, voters get to better "express" their preferences, voting for candidates who aren't really in the running; that doesn't really interest me except as it's related to the forces that tend to destabilize the bad equilibria.

This property is actually fairly robust, as it's given; in certain contexts, just about any voting system in which the number of different kinds of vote a voter can cast grows "quickly" with the number of candidates will have the same, small set of equilibria, with no bad equilibria, at least in a generic setting.  With plurality voting, when there are n candidates, each voter has only n+1 choices of ballot (i.e. vote for any of the candidates or none of them).  Both approval voting and borda count allow voters to be much more expressive, and therefore eliminate the bad equilibria.

The problem, finally, that I want to note with Borda count is that it tends to produce equilibria that are too fragile; if voters' beliefs are almost but not quite correct, the outcome of the election can depend very sensitively on what those beliefs are.  If there are 5 candidates, it should be reasonably clear that if three of the candidates are essentially out of the running, voters' incentives are to vote their preferred (of the other two) first and the other one last, with the three irrelevant candidates in the middle.  This itself will tend not to be equilibrium behavior; either one of the two "major" candidates is now finishing well behind one of the "irrelevant" candidates, or they are all very close to each other, and thus the irrelevant candidates become relevant.  The actual equilibrium will result in a very close race among many candidates, with the actual winner decided by few enough votes that voters who can best figure out the final outcome will garner outsized influence.  I don't care that, in equilibrium, people are casting a last place vote for a candidate they might deem more qualified than other candidates; that's simply part of the mechanism.  It does concern me, though, that the strategizing is so sensitive to information other than who is the best candidate.