Showing posts with label honesty. Show all posts
Showing posts with label honesty. Show all posts

Tuesday, October 27, 2009

How To Decide: Where to Go For Dinner

Let me propose a situation to you: you, and eight friends of yours, all live on the same street in some city or large town. As a crazy random happenstance, you are all precisely equally distant from your nearest neighbors: two blocks away. The nine of you decide that you're going to go out for a big dinner somewhere along your street, and there are two more-or-less identically good options: you could go to ApricotBug's, over on the west end of town, or you could go to Beryl Thursday's, closer to the east end.

How do you decide? Well, let's suppose you decide to put it to a vote, since that seems most democratic. Let's further suppose that, since the restaurants are more-or-less identical, everyone simply votes for the one closest to their house. Three of you live west of ApricotBug's, four of you live east of Beryl Thursday's, and two of you live in between. Let's vote!

You can easily see that everyone west of ApricotBug's votes for it, everyone east of Beryl Thursday's votes for it, and the two in between split their votes one and one. Beryl Thursday's wins, 5 to 4.

Notice that, even though each of you used a selfish algorithm (or to put a positive spin on it, an honest, true-to-yourself algorithm) to decide how to vote (the option that minimizes your own travel time), that as a group you also voted for the globally-minimum amount of travel; it would take a total of 45 blocks traveled for everyone to get to ApricotBug's, but only 41 blocks for everyone to get to Beryl Thursday's.

Continuing with the story: You have so much fun, you decide to do it again next month. However, a new restaurant has opened down the street, CBIM (Can't Believe It's (Already) Monday).

How does CBIM change the voting?

If we used the well-known method of plurality voting, we can see that the vote for ApricotBug's stays at 4, but the 5 votes that originally all went to Beryl Thursday's are now split 3 for it and 2 for CGIM. Which means that, now, ApricotBug's wins.

This is no longer the globally-optimal solution, and if you think about it, it's really kind of stupid that adding more options, particularly an obviously bad choice like CBIM, would ruin the vote like this.

What to Do, What to Do...

After much existential gnashing of teeth, you decide to use "instant runoff voting" (because one of you heard about it on the internet and, at first glance, it sounds pretty good!) With IRV, you can pick additional options beyond just your first choice, and if your first choice doesn't win, your vote will be moved over to the next in line.

Everyone west of ApricotBug's and your friend who lives right next to it will vote A > B > C. Also, the two friends closest to CBIM will vote C > B > A. For the three in the middle, two vote B > A > C and one votes B > C > A. (Count the distances yourself if this isn't clear to you.) So which restaurant wins now? IRV tells us to eliminate the option with the fewest first-place votes. That's CBIM. We then move those votes to the voter's second choice, which in this case is Beryl Thursday's for both voters.

Those two votes puts Beryl Thursday's back over the top, which is good, since we know that it's the globally-optimal solution, with respect to total distance traveled. So it sure seems like IRV has improved things for us. (If you're curious, CBIM would have taken 81 blocks; almost twice as bad as ApricotBug's!)

Next month rolls by, and gosh darnit, you've all gotten really attached to this big night out, so you're going to do it again! One minor change though: CBIM had a little problem at their original location (it was too popular, so it wasn't large enough) and so the owner relocated four blocks over (a total distance of 53 blocks for everyone to reach.)

No problem; we'll let IRV handle this! It's still 4 for A > B > C, and 1 for B > C > A, but now we're up to 3 for C > B > A and down to 1 for B > A > C. That's 4 first-place votes for A, 3 for C, and two for B. Uh oh...

Now we're back to the exact same problem we had before under plurality. None of you or your friends have moved. ApricotBug's and Beryl Thursday's haven't moved. The only thing that changed is a that a third fringe option has moved to a slightly-more-acceptable position. The mere presence of CBIM spoiled the vote under plurality, and now its mere presence has spoiled the election in the exact same way under IRV.

Perhaps you're thinking to yourself that, no, some of the CBIM fans will see what's going to happen, and they'll instead vote for Beryl Thursday's first. But they could have just as easily done that under plurality voting; why would IRV be different? And even if it is, for some unexplained reason, different, why should they have to choose among the lesser of two evils, between ApricotBug's and Beryl Thursday's, when in their heart-of-hearts, they want CBIM? Wasn't IRV supposed to fix that problem?

IRV Isn't a Good Idea

If you think IRV is a good idea because it will allow third parties to win elections, you are wrong; it will be just like under plurality. If you think IRV is a good idea because it fixes the spoiler problem, you are wrong; it will be just like under plurality.

In the real-world, we don't have access to simple metrics like "fewest total blocks traveled" to guide us in choosing our political leaders; we only have everyone's biased, greedy, short-sighted, and misinformed opinions. I believe that, deep down, we all want what's best for everyone, but that, obviously, opinions differ on what that is. If IRV can't properly decide which of three kitsch restaurants to hang out at in a simple, one-dimensional scenario like this, I guarantee that it won't do any better in the real world.

Coming Soon!

Next up, I'll have a dinner-vote using score voting, and then maybe we'll try a two-dimensional example, which will show the problems with Condorcet methods.

Thursday, March 5, 2009

Honesty is the Best Policy. But...

Warren Smith's mamoth voting study in 2000 (abstract, pdf) revealed several exciting bits of information. Chief among these was that score voting (referred to as "range voting" in the paper) had, under all 700+ conditions, the best performance of any voting method he examined. Less significant to the voting-reform movement, but no less interesting, was his finding that performance was better with a population of honest voters than with a population of strategic ones, for every method examined.

But what does "honesty" mean, in this sense? If your only voting experience is with the plurality system (which is likely), the idea of a dishonest vote might be confusing; after all, if you prefered Barak Obama, why would you lie and say you preferred John McCain (or vice-versa)? Of course you wouldn't; but maybe you would have prefered Hillary Clinton (or Mitt Romney or Mike Huckabee or even Ron Paul) or maybe even Ralph Nader. If you honestly, in your political heart-of-hearts, preferred one of these other candidates, but voted for one of the two front-runners, then you are a dishonest voter.

You are a dishonest voter

Or, to put it a nicer way, a "strategic" voter. After all, it doesn't take a genius to realize that voting for one of the other former Democratic (or Republican) candidates is a waste of time: there's a reason why parties have primaries, and it's because our election system provides strong incentives to reduce the election to a choice between just two options, so they better make sure all their people are backing the same candidate, ensuring they'll be one of those two. The same incentives are what cause our politics to be dominated by just two parties); in fact, voting for a third party actually makes it more likely that your less-preferred choice among the "major" candidates will win. This is a fact still warm in the minds of left-leaning Americans from Nader's spoiler effect in Florida in the 2000 pressidential race (or if you prefer, among right-leaning Minnesotans in the 2008 senate race.)

So: people--probably you--vote strategically in order to increase the effect their vote will have on the outcome. You don't vote for a candidate who "can't win", and only two candidates will be able to win. Now, back to Dr. Smith's experiment. His measure of performance is called "Bayesian regret", the idea being that we take all the positive and negative effects (commonly referred to as "utilities") that every voter would experience for each candidate if they were elected, add them all togehter to get society's utility, and for each election method determine how much worse the winner is when compared to the best possible candidate. Smith's results showed that, under every election method he tested, if everyone votes honestly (i.e., as truthfully-accurate to their computer-generated utilities as allowed by the election method), then the net utility for society as a whole is better. But we just showed that, at least under our current system, vast numbers of people don't vote honestly, as the system compels them to vote for "the lesser of two evils".

Why do people do that? We can answer that by examining these same utilities: if I honestly prefer Nader over Gore (utility of, say, +9 units versus +8), and Gore over Bush (+8 units versus -5), but realize that a vote for Nader will result in Bush being elected (as occured in Florida in 2000), then I can maximize my personal utility by dishonestly voting "for" Gore (really, "against" Bush.) But if everyone follows this sort of plan, then Smith's results show that on average, across a great many elections, society's net utility will be lower. (You might ask, "Why don't we just measure everyone's utilities, and determine the optimum winner that wasy?" The answer is simple: people will strategize ("lie") about those, too. (It's okay to use them in the simulation though, since we assigned each computer voter their honest utilities programatically.))

Strategy under score voting

What about Smith's election-method-shootout winner, score voting? Well, it turns out you can lie there, too. Maybe you have in your mind some "ideal" candidate, who agrees with you on every issue; but what if none of the candidates for office matches you on more than 70% of those issues? Do you give that candidate 70% of the maximum score? Or do you lie just a bit, and give them the maximum score, increasing their chance to win? Similarly, do you give your least prefered candidate a 0, or do you give them 20% because they agree with you on a few issues? What if everyone else was doing it? That's just the tip of iceberg though. If you really wanted to maximixe the impact of your vote, you'd look at the polls, figure out who the two front runners are, and give whichever of those two candidates you prefer and every candidate you prefer better than them, the maximum score, and give the other candidate and every candidate you prefer less than them a zero; if there's any candidates left, you could scale them appropriately to fit between those extremes.

No election method (short of deep mind-reading to determine real, honest utilities) will ever be immune to strategic manipulation. But score voting is hurt much less by it than our current plurality system; strategic score voting is functionally the same as approval voting, which was also examined in Smith's study. Indeed, those two methods have identical Bayesian regret with 100% strategic voters. Furthermore, there's less for a strategic voter to gain; the chance that a strategic vote will change the outcome is lower, and there's never any reason to give your honest true favorite less than the maximum score, a property called "immunity to favorite-betrayal". So you can feel good about yourself while still maximizing your impact on the election, by giving your honest favorite "third party" candidate as well as your favorite "major" candidate both the maximum score. Given some time for the party to grow support, a third-party candidate could even win an election; we can actually escape the two-party system.

Strategic IRV = Strategic Plurality

Interestingly, instant-runoff voting (IRV), which is gaining popularity following its adoption in several parts of California, is exactly the same (which is to say, exactly as bad) as our current plurality system when we assume strategic voters. IRV and plurality are analogous to score and approval in that sense: in the worst case, they're identical. And assuming a constant percentage of honest voters, score is always better than IRV as measured by Bayesian regret. This is because, while an IRV advocate will tell you that you can honestly vote Nader > Gore > Bush without fear, this is only true up until Nader has about 20% support. At that point, a vote for Nader will cause Bush to win instead of Gore, which means we will continue to be trapped in a two-party system. While IRV is (in someways) better than plurality, score voting can actually create some change, and means you can always afford to be honest.