Unfortunately according to Arrow’s theorem, you can’t have a perfect system. Non-monotonicity is, in my view, a reasonable trade-off for the extra information about preferences that gets put into the system. Approval voting also means some people’s votes count more than others (a criticism that has been falsely raised against AV).
Either way, the choice being presented isn’t between all possible voting systems (I’d support STV myself) but between FPTP and AV, so I’m only discussing that choice rather than a choice over all voting-system space...
Isn’t this the fallacy of gray? I agree that the disadvantages of AV over Condorcet are entirely irrelevant on 5 May, but that’s not to say that a Condorcet system wouldn’t be clearly superior. The only advantage of AV is that people would find a transition to STV easier to understand.
It is, but I was pointing out that “AV has downsides” isn’t itself an argument.
Approval voting, of course, isn’t a Condorcet system either. In fact it can pick the Condorcet loser—even in a situation with a strong Nash equilibrium.
Approval voting, of course, isn’t a Condorcet system either. In fact it can pick the Condorcet loser—even in a situation with a strong Nash equilibrium.
Really? This isn’t obvious to me, and a quick attempt to construct a counterexample has failed and Google doesn’t turn anything up either. Could you give a hint about how to construct this?
I got the result from http://dimacs.rutgers.edu/Workshops/DecisionTheory2/laslier.pdf . This deals with the preferences of the voters as utility functions (in such a way that it’s not all that easy for me to turn it into “X voters want candidate Y”), but has at least one example that would elect the Condorcet winner with probability only 1/64 while the Condorcet loser would be elected with probability 31⁄64...
Makes sense, though we probably couldn’t have got that through a referendum. Any preferential system is preferable (to me) to a non-preferential system, though (barring trivially absurd cases of both, like a preferential system where the least-preferred candidate wins).
Arrow’s theorem has overly restrictive assumptions. It allows the voter to specify that A > B > C, but not that 50% chance of A plus 50% chance of C is better than B. If you relax these assumptions and allow each voter to specify their preferences over all weighted combinations of outcomes (aka specify a VNM utility function), then you can satisfy all desiderata of Arrow’s theorem. The simplest scheme is just giving each user 1 vote and allowing them to assign portions of that vote to different candidates, e.g. 0.7 of my vote goes to A and 0.3 to B. The candidate with the highest sum of votes wins.
ETA: this system satisfies independence of irrelevant alternatives only in a certain overly restrictive sense, so it’s not satisfactory. See the comment thread with Khoth and the links there.
You might be right (though I’ve never seen that objection before). I’ll have to think it out.
However, I think in that circumstance, you’d have a massive incentive to put all your vote onto one candidate who is most likely to win out of the choices you prefer, because anything else would be splitting the vote (in a way that you can’t split a vote under AV, because your lower preferences only get counted if your higher ones have already been knocked out).
So in practice, that system would collapse into something very like FPTP.
I’m skeptical of this, in that there are voting systems like this (10 seats open, you get ten votes to distribute however you want, etc.) and while they are limited by integer choices, they don’t come close to satisfying the desiderata.
One thing that comes to mind is that it would be quite gameable; putting all your vote in one candidate will often be a better decision than comes to mind, but this is off the top of my head and it does seem within the realm of possibility that it could be “Arrow’s no integral points on ideal voting systems theorem.” Which is a great name for a theorem.
How does that satisfy independence of irrelevant alternatives? Candidate C can steal votes from candidate A, allowing B to win where A would have won otherwise.
It satisfies independence of irrelevant alternatives in the following sense: if A has more total vote than B, and you tweak each voter’s individual allocations in any way but without touching their allocations toward A and B, you can’t make B have more total vote than A. The proof is obvious. I’m not sure what you mean by vote-stealing, or by independence of irrelevant alternatives for that matter. Please expand.
As I understand it, your voting proposal is that each voter gives a number of votes for each candidate, totalling 1. (eg, 0.7 for A, 0.3 for B, or 0.2 for A, 0.3 for B and 0.5 for C). Then, each candidate’s totals are added up and the highest wins. If that’s not what you’re proposing, disregard the rest of this comment.
Suppose there are three candidates, A, B and C. A and C are extremely similar, so nobody has much of a preference between them. 60% of people would like one of them to win, and 40% would rather B won. Under your scheme, as far as I can tell, A and C each get about 30% of the vote each, and B 40%, so B wins. But if C wasn’t standing, then A would get 60% and win against B’s 40%.
Wikipedia defines “independence of irrelevant alternatives” in the context of Arrow’s theorem as follows:
Arrow’s IIA requires that whenever a pair of alternatives is ranked the same way in two preference profiles (over the same choice set), then the aggregation rule must order these two alternatives identically across the two profiles.
Also see the subsequent notes on that page about changing the choice set.
In your scenario the choice set changes, and as a consequence many people change their allocation for A. It seems you want something much stronger than independence of irrelevant alternatives. You want a system where removing a candidate and then allowing all voters to adjust their behavior strategically (both of which are disallowed under Arrow’s IIA) doesn’t change the outcome.
Of course I may be wrong here and in fact I consider myself likely to be wrong because this is a new topic to me, so feel free to correct.
The reason you’re seeing these multiple definitions of IIA is because with the appropriate setup, they’re equivalent. To be specific:
Let’s say we have a finite set of candidates C and a set V of voters. (The set of voters will remain fixed throughout.) Then we can define a (type 1) voting system for C to be a function taking (maps from V to linear orders on C) and returning a linear order on C. With this definition, the natural notion of IIA is the one you describe above.
(Note: Obviously, “type 1”, “type 2″, “type 3” are all ad-hoc terminology.)
Now we could define a type 2 voting system for a (potentially infinite) set of candidates C to be a family of type 1 voting systems, one for each finite subset of C. Then you have a natural notion of IIA for type 2 voting systems, namely, restricting from one subset of C to a smaller subset shouldn’t change the induced order on this smaller subset.
Finally we can consider type 3 voting systems for C, which we will define to be a family of voting systems, one for each finite subset of C, but these all just return single winners, not whole linear orders. The natural notion of IIA for this sort of voting system is the one Khoth describes.
It’s then trivial that every type 2 voting system induces a type 1 and a type 3 voting system, and if the type 2 system satisfies its IIA then so do the induced systems. What is less obvious but still not too hard is that if a type 1 or type 3 system satisfies its appropriate notion of IIA, then in fact it must come from an IIA-satisfying type 2 system. (Going from type 1 to type 2 is obvious; to go from type 3 to one of the other types, you run the election, put the winner in 1st, remove him, run again, put the new winner in 2nd, etc.)
So on a finite set of candidates all 3 notions are equivalent and on infinite set of candidates the 2 notions that make sense are equivalent.
I don’t have a reference on hand, which is why I don’t know if there’s standard terminology for this; this is just something I worked out some time ago when trying to figure out why I’d seen IIA defined differently in different places. :)
Ah, it seems like there are multiple definitions for the thing. I’d thought the relevant one was (from the same wikipedia page):
There are other requirements that go by the name of “IIA”.
One such requirement is as follows: If A is preferred to B out of the choice set {A,B}, then introducing a third alternative X, thus expanding the choice set to {A,B,X}, must not make B preferable to A. In other words, preferences for A or B should not be changed by the inclusion of X, i.e., X is irrelevant to the choice between A and B. This formulation appears in bargaining theory, theories of individual choice, and voting theory. Some theorists find it too strict an axiom; experiments by Amos Tversky, Daniel Kahneman, and others have shown that human behavior rarely adheres to this axiom.
In any case, whether Arrow meant this one or not, it’s still something that most people (including me) would think desirable for a voting system to have. I think Arrow’s Theorem (and IIA as he has it) is defined in terms of mapping from everyone’s complete ordering of preferences to a winner. If your original objection was that an ordering of preferences isn’t the proper place to start, you’ll also have to change your definition of IIA to fit your new probabilistic starting point.
Yeah, I gave a version of IIA in a previous comment, and I think it’s a pretty faithful translation of Arrow’s IIA to my formalism. Do you think some other translation would be better?
I think your “tweaking” is too restrictive. Your version forces the allocations to A and B to be unchanged, whereas I think a more accurate translation would be that the ordering doesn’t change (or perhaps that the new allocations to A and B are in the same proportion as the old allocations). Those translations produce versions which are broken by your proposed voting system.
ETA: I think we (or at least I) am at risk of falling into the trap of arguing over definitions. Any way of defining IIA needs to be accompanied by a reason why anyone should care about that definition. So, a rough explanation of my position:
The reason we care about Arrow’s Theorem is that it basically says “any voting system will have some undesirable properties”
The reason IIA is desirable is that it’s a formalisation of the notion that candidates who don’t win can’t act as “spoilers” that change which candidate does win.
I suspect that by using your probability scheme, even if you can get around the specific definitions of undesirable properties that Arrow used, any voting system based on it will still have analogous bad properties.
In particular, the voting system you propose, third(or more)-party candidates can act as spoilers.
ETA2: Add formatting, and note that my first ETA would likely have been a bit different had I seen your reply first.
On rereading, you’re right that my translation was overly strict, and it’s obvious that the more lenient translations immediately fail. Thanks.
I googled some more and found a very nice discussion of this topic here on LW: Arrow’s Theorem is a Lie. Tommccabe’s idea, a reinvention of range voting, is better than mine by pretty much all criteria.
ETA: the rationale for Arrow’s IIA still seems different from what you say, because it doesn’t allow changing the set of candidates. I’m not sure how to express the rationale for Arrow’s IIA so it carries over to other settings.
Thanks for the links, I hadn’t come across range voting before.
Like pretty much every voting system ever, it still allows for tactical voting (You naturally give your preferred candidate the highest possible score, but the optimal scores to give for the other depends on how other people are voting). It makes me wonder if that’s a thing that voting systems can’t get rid of (well, apart from degenerate things like the “dictator” voting scheme).
How about a system that picks a voter at random and uses their choice? This way there’s no incentive for tactical voting. But it still violates your strengthened version of IIA because a candidate can steal votes from another.
Unfortunately according to Arrow’s theorem, you can’t have a perfect system. Non-monotonicity is, in my view, a reasonable trade-off for the extra information about preferences that gets put into the system. Approval voting also means some people’s votes count more than others (a criticism that has been falsely raised against AV). Either way, the choice being presented isn’t between all possible voting systems (I’d support STV myself) but between FPTP and AV, so I’m only discussing that choice rather than a choice over all voting-system space...
Arrow’s theorem only applies to ordinal voting systems. It has nothing to say about range voting, e.g.
Isn’t this the fallacy of gray? I agree that the disadvantages of AV over Condorcet are entirely irrelevant on 5 May, but that’s not to say that a Condorcet system wouldn’t be clearly superior. The only advantage of AV is that people would find a transition to STV easier to understand.
It is, but I was pointing out that “AV has downsides” isn’t itself an argument. Approval voting, of course, isn’t a Condorcet system either. In fact it can pick the Condorcet loser—even in a situation with a strong Nash equilibrium.
Really? This isn’t obvious to me, and a quick attempt to construct a counterexample has failed and Google doesn’t turn anything up either. Could you give a hint about how to construct this?
I got the result from http://dimacs.rutgers.edu/Workshops/DecisionTheory2/laslier.pdf . This deals with the preferences of the voters as utility functions (in such a way that it’s not all that easy for me to turn it into “X voters want candidate Y”), but has at least one example that would elect the Condorcet winner with probability only 1/64 while the Condorcet loser would be elected with probability 31⁄64...
Sure; if it had been my choice I would have chosen Ranked Pairs.
Makes sense, though we probably couldn’t have got that through a referendum. Any preferential system is preferable (to me) to a non-preferential system, though (barring trivially absurd cases of both, like a preferential system where the least-preferred candidate wins).
Arrow’s theorem has overly restrictive assumptions. It allows the voter to specify that A > B > C, but not that 50% chance of A plus 50% chance of C is better than B. If you relax these assumptions and allow each voter to specify their preferences over all weighted combinations of outcomes (aka specify a VNM utility function), then you can satisfy all desiderata of Arrow’s theorem. The simplest scheme is just giving each user 1 vote and allowing them to assign portions of that vote to different candidates, e.g. 0.7 of my vote goes to A and 0.3 to B. The candidate with the highest sum of votes wins.
ETA: this system satisfies independence of irrelevant alternatives only in a certain overly restrictive sense, so it’s not satisfactory. See the comment thread with Khoth and the links there.
You might be right (though I’ve never seen that objection before). I’ll have to think it out. However, I think in that circumstance, you’d have a massive incentive to put all your vote onto one candidate who is most likely to win out of the choices you prefer, because anything else would be splitting the vote (in a way that you can’t split a vote under AV, because your lower preferences only get counted if your higher ones have already been knocked out). So in practice, that system would collapse into something very like FPTP.
I’m skeptical of this, in that there are voting systems like this (10 seats open, you get ten votes to distribute however you want, etc.) and while they are limited by integer choices, they don’t come close to satisfying the desiderata.
One thing that comes to mind is that it would be quite gameable; putting all your vote in one candidate will often be a better decision than comes to mind, but this is off the top of my head and it does seem within the realm of possibility that it could be “Arrow’s no integral points on ideal voting systems theorem.” Which is a great name for a theorem.
How does that satisfy independence of irrelevant alternatives? Candidate C can steal votes from candidate A, allowing B to win where A would have won otherwise.
It satisfies independence of irrelevant alternatives in the following sense: if A has more total vote than B, and you tweak each voter’s individual allocations in any way but without touching their allocations toward A and B, you can’t make B have more total vote than A. The proof is obvious. I’m not sure what you mean by vote-stealing, or by independence of irrelevant alternatives for that matter. Please expand.
As I understand it, your voting proposal is that each voter gives a number of votes for each candidate, totalling 1. (eg, 0.7 for A, 0.3 for B, or 0.2 for A, 0.3 for B and 0.5 for C). Then, each candidate’s totals are added up and the highest wins. If that’s not what you’re proposing, disregard the rest of this comment.
Suppose there are three candidates, A, B and C. A and C are extremely similar, so nobody has much of a preference between them. 60% of people would like one of them to win, and 40% would rather B won. Under your scheme, as far as I can tell, A and C each get about 30% of the vote each, and B 40%, so B wins. But if C wasn’t standing, then A would get 60% and win against B’s 40%.
Wikipedia defines “independence of irrelevant alternatives” in the context of Arrow’s theorem as follows:
Also see the subsequent notes on that page about changing the choice set.
In your scenario the choice set changes, and as a consequence many people change their allocation for A. It seems you want something much stronger than independence of irrelevant alternatives. You want a system where removing a candidate and then allowing all voters to adjust their behavior strategically (both of which are disallowed under Arrow’s IIA) doesn’t change the outcome.
Of course I may be wrong here and in fact I consider myself likely to be wrong because this is a new topic to me, so feel free to correct.
The reason you’re seeing these multiple definitions of IIA is because with the appropriate setup, they’re equivalent. To be specific:
Let’s say we have a finite set of candidates C and a set V of voters. (The set of voters will remain fixed throughout.) Then we can define a (type 1) voting system for C to be a function taking (maps from V to linear orders on C) and returning a linear order on C. With this definition, the natural notion of IIA is the one you describe above.
(Note: Obviously, “type 1”, “type 2″, “type 3” are all ad-hoc terminology.)
Now we could define a type 2 voting system for a (potentially infinite) set of candidates C to be a family of type 1 voting systems, one for each finite subset of C. Then you have a natural notion of IIA for type 2 voting systems, namely, restricting from one subset of C to a smaller subset shouldn’t change the induced order on this smaller subset.
Finally we can consider type 3 voting systems for C, which we will define to be a family of voting systems, one for each finite subset of C, but these all just return single winners, not whole linear orders. The natural notion of IIA for this sort of voting system is the one Khoth describes.
It’s then trivial that every type 2 voting system induces a type 1 and a type 3 voting system, and if the type 2 system satisfies its IIA then so do the induced systems. What is less obvious but still not too hard is that if a type 1 or type 3 system satisfies its appropriate notion of IIA, then in fact it must come from an IIA-satisfying type 2 system. (Going from type 1 to type 2 is obvious; to go from type 3 to one of the other types, you run the election, put the winner in 1st, remove him, run again, put the new winner in 2nd, etc.)
So on a finite set of candidates all 3 notions are equivalent and on infinite set of candidates the 2 notions that make sense are equivalent.
I don’t have a reference on hand, which is why I don’t know if there’s standard terminology for this; this is just something I worked out some time ago when trying to figure out why I’d seen IIA defined differently in different places. :)
Ah, it seems like there are multiple definitions for the thing. I’d thought the relevant one was (from the same wikipedia page):
In any case, whether Arrow meant this one or not, it’s still something that most people (including me) would think desirable for a voting system to have. I think Arrow’s Theorem (and IIA as he has it) is defined in terms of mapping from everyone’s complete ordering of preferences to a winner. If your original objection was that an ordering of preferences isn’t the proper place to start, you’ll also have to change your definition of IIA to fit your new probabilistic starting point.
Yeah, I gave a version of IIA in a previous comment, and I think it’s a pretty faithful translation of Arrow’s IIA to my formalism. Do you think some other translation would be better?
I think your “tweaking” is too restrictive. Your version forces the allocations to A and B to be unchanged, whereas I think a more accurate translation would be that the ordering doesn’t change (or perhaps that the new allocations to A and B are in the same proportion as the old allocations). Those translations produce versions which are broken by your proposed voting system.
ETA: I think we (or at least I) am at risk of falling into the trap of arguing over definitions. Any way of defining IIA needs to be accompanied by a reason why anyone should care about that definition. So, a rough explanation of my position:
The reason we care about Arrow’s Theorem is that it basically says “any voting system will have some undesirable properties”
The reason IIA is desirable is that it’s a formalisation of the notion that candidates who don’t win can’t act as “spoilers” that change which candidate does win.
I suspect that by using your probability scheme, even if you can get around the specific definitions of undesirable properties that Arrow used, any voting system based on it will still have analogous bad properties.
In particular, the voting system you propose, third(or more)-party candidates can act as spoilers.
ETA2: Add formatting, and note that my first ETA would likely have been a bit different had I seen your reply first.
On rereading, you’re right that my translation was overly strict, and it’s obvious that the more lenient translations immediately fail. Thanks.
I googled some more and found a very nice discussion of this topic here on LW: Arrow’s Theorem is a Lie. Tommccabe’s idea, a reinvention of range voting, is better than mine by pretty much all criteria.
ETA: the rationale for Arrow’s IIA still seems different from what you say, because it doesn’t allow changing the set of candidates. I’m not sure how to express the rationale for Arrow’s IIA so it carries over to other settings.
Thanks for the links, I hadn’t come across range voting before.
Like pretty much every voting system ever, it still allows for tactical voting (You naturally give your preferred candidate the highest possible score, but the optimal scores to give for the other depends on how other people are voting). It makes me wonder if that’s a thing that voting systems can’t get rid of (well, apart from degenerate things like the “dictator” voting scheme).
How about a system that picks a voter at random and uses their choice? This way there’s no incentive for tactical voting. But it still violates your strengthened version of IIA because a candidate can steal votes from another.