I am no longer confident in the arguments presented in two parts of this paper:
1) Section 7.1, when I argue that it is impossible to translate all of the paradox regions outside the unit simplex. As I try to visualize it, I am sure that the statement is correct, but I don't know that the method of argument is correct.
2) Section 8, where I argue that Type 1b stages must be point systems with quotas. I argue that if we think of it as a Type 1 stage augmented with Type 2 inequalities, then the Type 1 stage must always return a winner to avoid FBC violations, in accordance with the results of section 7.1. (Note that my concerns in section 8 are independent of the validity of the theorem in section 7.1. Even if the theorem is correct, I might not be applying it correctly.) Suppose that the Type 1 stage sometimes returns no winner, but only in cases where the Type 2 inequalities don't return a winner either? Then it's the non-satisfaction of the Type 2 inequalities that moves the method to the next stage, not the non-satisfaction of the Type 1 inequalities. So I have to figure out whether this is possible. I can prove that it's impossible in a restricted case, but I don't know about the general case.
Wednesday, December 29, 2010
Wednesday, August 25, 2010
Open thread for comments on manuscript
If you have something to say about my manuscript (linked at the top of the page), feel free to say it here.
Tuesday, August 24, 2010
What are ranked voting methods?
We're all familiar with voting: You punch your chad or fill in the bubble or pull the lever next to the name of your candidate, and the candidate with the most votes wins. Simple enough. However, this is not the only way to do an election.
To see why, suppose we have 3 candidates, and candidate A gets 40%, candidate B gets 45%, and candidate C gets 15%. Candidate B wins in our normal voting method in the US. However, many people are bothered by the fact that candidate B lacks majority support.
One answer would be to hold a runoff election between A and B, to figure out who has majority support. B can still win, if at least a third of C's supporters (5% or more) support B and push him over the edge. However, A could also win, depending on how C's supporters vote.
Now, holding a second election is cumbersome. What if on election day every voter had to indicate his or her first choice, second choice, 3rd choice, etc.? We could look and see if anybody is the favorite of a majority. If so, great, that candidate wins. If not, we could eliminate the candidate with the fewest first place votes from consideration, look at ballots that listed that candidate first, and see who those voters' second choice is. With their first choice gone, their vote goes to their second choice, and we again see if anybody is the favorite of a majority. We keep doing this until somebody has a majority.
There is a name for this approach: Instant Runoff Voting (IRV). It's used in a few US locales, and there are organizations that want to use it in more places. It has some problems (which I will talk about in another post) but it's an intuitive illustration of a ranked voting method. Everybody ranks candidates (1st choice, 2nd choice, 3rd choice, etc.) and that ranking information is used to determine the winner.
It isn't the only ranked voting method, however. Consider a few more possibilities:
1) We again cast ballots where we indicate 1st choice, 2nd choice, 3rd choice, etc., and then those choices get points. In a simple example, the 1st choice gets 2 points, the 2nd choice gets 1 point, and the last choice gets 0 points. This would be an example of the Borda Count, which has been extensively studied by Donald Saari, a mathematician at UC Irvine. It isn't the only possible point system, of course. We could have a point system where 1st choice gets 5 points, 2nd choice gets a token 1 point, and the others get 0 points. Or point systems with any number of other possible scoring rules. The key thing to understand is that, again, each voter indicates a ranking of candidates, and based on the number of people giving each ranking we figure out the winner.
2) Condorcet: Again, we all rank the candidates. Then, the people counting the votes look at our ballots and see if a majority prefers A to B or B to A. They look at our ballots and figure out if a majority prefers A to C or C to A. They do the same with B and C. And if there are more candidates, they keep doing this until every pair of candidates has been compared.
If somebody wins every contest, that person is the winner. But what if A beats B, B beats C, and C beats A? It can happen. In technical terms, it can happen with rational voters if issue space is more than 2D (more on that in another post). But the idea is paper, rock, scissors. When it happens, you need a backup plan. And if you Google for information on Condorcet Voting you'll discover that every fan of Condorcet has a preferred way of resolving that dilemma.
The key thing for my work is that Condorcet, much like IRV, is a multi-stage method. In IRV, you first check to see if anybody has a majority. If not, you do eliminations and transfers. In Condorcet, you check to see if anybody beats all of the other candidates one-on-one. If not, you do something else.
And, as you can imagine, there are countless more examples of ranked voting methods. For my work, I just take it as a given that voters rank candidates, and based on those rankings a decision is made. I don't care about the specifics of how the decision is made, as long as it satisfies a few criteria. The key thing is that the election concept has been expanded from just voting for a single candidate, to a situation where voters indicate much more detailed information, and that information is processed according to (possibly quite complicated) rules.
Future topics (in no particular order):
*Arrow's Theorem
*Issue space, squeezed centrists, and Condorcet paradoxes
*Gibbard-Satterthwaite Theorem
*Elections and geometry.
To see why, suppose we have 3 candidates, and candidate A gets 40%, candidate B gets 45%, and candidate C gets 15%. Candidate B wins in our normal voting method in the US. However, many people are bothered by the fact that candidate B lacks majority support.
One answer would be to hold a runoff election between A and B, to figure out who has majority support. B can still win, if at least a third of C's supporters (5% or more) support B and push him over the edge. However, A could also win, depending on how C's supporters vote.
Now, holding a second election is cumbersome. What if on election day every voter had to indicate his or her first choice, second choice, 3rd choice, etc.? We could look and see if anybody is the favorite of a majority. If so, great, that candidate wins. If not, we could eliminate the candidate with the fewest first place votes from consideration, look at ballots that listed that candidate first, and see who those voters' second choice is. With their first choice gone, their vote goes to their second choice, and we again see if anybody is the favorite of a majority. We keep doing this until somebody has a majority.
There is a name for this approach: Instant Runoff Voting (IRV). It's used in a few US locales, and there are organizations that want to use it in more places. It has some problems (which I will talk about in another post) but it's an intuitive illustration of a ranked voting method. Everybody ranks candidates (1st choice, 2nd choice, 3rd choice, etc.) and that ranking information is used to determine the winner.
It isn't the only ranked voting method, however. Consider a few more possibilities:
1) We again cast ballots where we indicate 1st choice, 2nd choice, 3rd choice, etc., and then those choices get points. In a simple example, the 1st choice gets 2 points, the 2nd choice gets 1 point, and the last choice gets 0 points. This would be an example of the Borda Count, which has been extensively studied by Donald Saari, a mathematician at UC Irvine. It isn't the only possible point system, of course. We could have a point system where 1st choice gets 5 points, 2nd choice gets a token 1 point, and the others get 0 points. Or point systems with any number of other possible scoring rules. The key thing to understand is that, again, each voter indicates a ranking of candidates, and based on the number of people giving each ranking we figure out the winner.
2) Condorcet: Again, we all rank the candidates. Then, the people counting the votes look at our ballots and see if a majority prefers A to B or B to A. They look at our ballots and figure out if a majority prefers A to C or C to A. They do the same with B and C. And if there are more candidates, they keep doing this until every pair of candidates has been compared.
If somebody wins every contest, that person is the winner. But what if A beats B, B beats C, and C beats A? It can happen. In technical terms, it can happen with rational voters if issue space is more than 2D (more on that in another post). But the idea is paper, rock, scissors. When it happens, you need a backup plan. And if you Google for information on Condorcet Voting you'll discover that every fan of Condorcet has a preferred way of resolving that dilemma.
The key thing for my work is that Condorcet, much like IRV, is a multi-stage method. In IRV, you first check to see if anybody has a majority. If not, you do eliminations and transfers. In Condorcet, you check to see if anybody beats all of the other candidates one-on-one. If not, you do something else.
And, as you can imagine, there are countless more examples of ranked voting methods. For my work, I just take it as a given that voters rank candidates, and based on those rankings a decision is made. I don't care about the specifics of how the decision is made, as long as it satisfies a few criteria. The key thing is that the election concept has been expanded from just voting for a single candidate, to a situation where voters indicate much more detailed information, and that information is processed according to (possibly quite complicated) rules.
Future topics (in no particular order):
*Arrow's Theorem
*Issue space, squeezed centrists, and Condorcet paradoxes
*Gibbard-Satterthwaite Theorem
*Elections and geometry.
Sunday, August 22, 2010
First post!
Welcome to Arrows Fear Him, my blog for discussing election mathematics. I'm a physicist who at some point became interested in third parties. When this happened, I become interested in alternative election methods, stuff like Approval Voting and Instant Runoff and Borda and Condorect and all that. Turns out, these topics have a lot of math behind them, so I got interested in that. Then I got interested in a very specific problem: Favorite betrayal (see an upcoming post).
We know from the Gibbard-Satterthwaite Theorem that ranked voting methods will always give incentives to vote insincerely (if you don't know what that means, don't worry, I plan to do a post on this for the layman, eventually). However, could you at least make it so that while you might have an incentive to lie, at least you only have an incentive to lie about your second favorite? This way you could still throw your support behind your favorite without penalty.
It turns out that there are such systems. Anti-plurality (the candidate ranked last by the fewest voters is the one who wins) and Approval Voting (you vote yes or no on each candidate, most yeses wins, and saying "yes" to multiple candidates is allowed) are examples. Mike Ossipoff and Warren Smith (see the Center for Range Voting in the links to the right) came up with some more. However, these systems are hard to find. My paper (link at top of page) addresses just how many there are and what sorts of families they fall into. The paper has not been through peer review, but I'm putting it up to get feedback and comments.
So, what do I plan to post on here?
1) My manuscript, of course, as I go through revisions and get feedback. Most of the posts will be on that.
2) For the layman, what are ranked voting methods? What is the Gibbard-Satterthwaite Theorem? What is Favorite Betrayal, and why do you need so much math to study it?
3) Nash equilibria and the Gibbard-Satterthwaite Theorem. I'm not a professional game theorist, but I think I've come up with a neat little insight along these lines, and eventually I'll blog about it.
4) The Electoral College. Not so much the politics of it (it is what it is) but a theoretical and strategic understanding of how it shapes incentives.
5) Any other interesting stuff related to election methods that I feel like blogging.
What won't I be blogging?
1) The IRV vs. other methods food fight. I'll weigh in to a certain extent (in brief, I prefer Approval Voting to Instant Runoff Voting) and explain why, but skirmishing over the efforts to implement IRV is not my thing. I'm glad that there are people pushing for alternative election methods, and I'm not going to get in their way.
2) Politics. My views are what they are, and I admit to having leanings that are a mix of left and libertarian, but I don't want to take that up here.
So, welcome, and stay tuned.
We know from the Gibbard-Satterthwaite Theorem that ranked voting methods will always give incentives to vote insincerely (if you don't know what that means, don't worry, I plan to do a post on this for the layman, eventually). However, could you at least make it so that while you might have an incentive to lie, at least you only have an incentive to lie about your second favorite? This way you could still throw your support behind your favorite without penalty.
It turns out that there are such systems. Anti-plurality (the candidate ranked last by the fewest voters is the one who wins) and Approval Voting (you vote yes or no on each candidate, most yeses wins, and saying "yes" to multiple candidates is allowed) are examples. Mike Ossipoff and Warren Smith (see the Center for Range Voting in the links to the right) came up with some more. However, these systems are hard to find. My paper (link at top of page) addresses just how many there are and what sorts of families they fall into. The paper has not been through peer review, but I'm putting it up to get feedback and comments.
So, what do I plan to post on here?
1) My manuscript, of course, as I go through revisions and get feedback. Most of the posts will be on that.
2) For the layman, what are ranked voting methods? What is the Gibbard-Satterthwaite Theorem? What is Favorite Betrayal, and why do you need so much math to study it?
3) Nash equilibria and the Gibbard-Satterthwaite Theorem. I'm not a professional game theorist, but I think I've come up with a neat little insight along these lines, and eventually I'll blog about it.
4) The Electoral College. Not so much the politics of it (it is what it is) but a theoretical and strategic understanding of how it shapes incentives.
5) Any other interesting stuff related to election methods that I feel like blogging.
What won't I be blogging?
1) The IRV vs. other methods food fight. I'll weigh in to a certain extent (in brief, I prefer Approval Voting to Instant Runoff Voting) and explain why, but skirmishing over the efforts to implement IRV is not my thing. I'm glad that there are people pushing for alternative election methods, and I'm not going to get in their way.
2) Politics. My views are what they are, and I admit to having leanings that are a mix of left and libertarian, but I don't want to take that up here.
So, welcome, and stay tuned.
Subscribe to:
Posts (Atom)