This is how I was taught it (or understood I was taught it) - at law school, so it might have been dumbed down.
The impossibility is the impossibility of ensuring rational (transitive) outcomes amongst ranked preferences and adhering to a set of fair and democratic norms.
A rational transitive outcomes is one in which votes result in option A being preferred over option B and option B being preferred over option C, such that A is preferred over C (eg, A > B > C). Option A is known as the Condorcet winner.
But there may be cases where the vote yields no Condorcet winner (eg, A > B > C > A). This is illustrated by the following table:
Two voters prefer C over V and two prefer V over S, but two also prefer S over C.
To ensure transitivity, we can introduce voting rules, but it is impossible to introduce rules that do not violate the fair and democratic norms (referred to as the pre-specified criteria in the Wikipedia article: unrestricted domain, non-dictatorship, Pareto efficiency, and independence of irrelevant alternatives).
Yeah, but that takes the punch out of the theorem. It's saying, "hey, sometimes you have really screwy preferences, too bad."
Realistically, that kind of situation doesn't break a voting system. We can say "we don't care about that case -- just pick a random winner then", but it's no longer deterministic.
Is there a stronger version of the theorem that says there's no sane procedure even ignoring those cases?
No, of course not. It's really easy to come up with a system that always comes up with "good" results if you rule out "screwy" voter preferences, with a sufficiently restrictive value of "screwy".
That is all the punch he theorem has. Arrows theorem shows that aggregate preferences have ties even when individuals don't, and strategic voting can tip the results in those cases.
For a voting system (ranking of some candidates based on preferences of voters), it would be nice if:
- A single voter cannot determine the ranking (as a dictator)
- For every possible set of voter preferences, there is an outcome (not random)
- If everyone likes candidate A over candidate B, then in the final ranking candidate A should be ranked higher than candidate B
- If one prefers A over B when comparing just A and B, then one should also prefer A over B when an additional option C is offered
Sounds like some reasonable properties for a voting system, right?
Well, the theorem states that if there are more than 2 candidates, then there is no voting system that has all 4 properties above.
> Well, the theorem states that if there are more than 2 candidates, then there is no voting system that has all 4 properties above in the general case.
Nobel Laureate Amartya Sen[0] has demonstrated that, while there is no system that satisfies all four characteristics in the general case, there are systems that either satisfy all four conditions either probabilistically or satisfy all four conditions subject to some very weak assumptions.
The example I've heard him use is of the 2000 election in Florida, with Bush, Gore, and Nader (let's ignore Buchanan for simplicity). While technically there are 3! = 6 possible ways to rank the candidates, in practice, the ranking (Nader, Bush, Gore) is much less likely than (Nader, Gore, Bush) or (Gore, Nader, Bush). If we introduce one minor assumption about the relative frequencies of the rankings, we can prove that instant-runoff voting[1] does always satisfy all four of Arrow's criteria[2].
To use an analogy from computer science, the halting problem is undecidable in the general case, but that doesn't prevent static analysis tools from spotting many infinite loops; it just means it can't spot all infinite loops with 100% accuracy.
[2] A different example: instead of making assumptions about the relative frequencies, we could make assumptions about the number of axes that candidates may have and the way they cluster around them. This realistically depicts both two-party and multiparty elections in most parts of the world, since political positions are not uniformly distributed along n dimensions.
You're right that it was a smaller group, of course, but it wasn't an empty one.
Jello Biafra's endorsement of Nader plus Gore's attack on Twisted Sister for the Parents Music Resource Council means N-B-G was actually the order of preference for anyone where "the right to rock out" was their single voting issue.
In college I was part of a club that had an elaborate election procedure for officers. I'm pretty sure it violates Arrow's Theorem, but it was also nonterminating!
Oh, god. I don't remember the details, but it involved crossing off the bottom third of candidates every round until there was only one left. But somehow, this didn't always get rid of everyone, and you could get stuck in a state where there was no bottom third.
> the theorem states that if there are more than 2 candidates, then there is no voting system that has all 4 properties above.
There is no rank order voting system that has all those properties. (Rank order means, that the voter puts the candidates in the the order of preference: 1., 2., 3. etc.)
But there are other voting systems, e.g. a system where you give each candidate points between 1-100 or whatever, and you can give the same amount of points to several candidates if you want.
Regarding Arrow's theorem, most voting systems regarded as better than first-past-the-post tend to choose to violate the third criteria, commonly called "independence of irrelevant alternatives": adding another candidate shouldn't change the preference order of existing candidates.
>If one prefers A over B when comparing just A and B, then one should also prefer A over B when an additional option C is offered
That assumption seems fishy to me if in a real life application, in particular because we assume offering new choices can't fundamentally change the agent/voter's preferences isn't exactly true to life. I'll give a real life, but slightly historically oversimplified example:
Say I am a poor serf living in pre-revolution Russia about a century ago. I am usually offered the following two choices:
A. serve the bourgeois royal family and live off of their scraps
B. die like a dog
Then, one day, Lenin (or similar revolutionary) comes along and offers me:
C. fight for glorious USSR communism
In real life, I would think the offered choice of C would absolutely change my preferences for A and B.
Granted this doesn't invalidate the Arrow paradox in any way, I'm just saying the paradox isn't true to life because one of its core tenants doesn't quite hold.
> Granted this doesn't invalidate the Arrow paradox in any way, I'm just saying the paradox isn't true to life because one of its core tenants doesn't quite hold.
However, this plays rather fast and loose with the principles behind Arrow's theorem. First, you're violating the nondictatorial condition (you are the only person voting on your own choice), so it's kind of silly to apply the theorem here in the first place.
Secondly, you're saying that, as soon as Communism becomes an option (but only then), you'd rather die than serve the royal family.
I can see how this might be the case, but if so, you're fundamentally changing the meaning of choice B. It's no longer just the default state ("die of starvation"), but rather dying for a cause (Communism). It's not that the introduction of choice C suddenly means that you're now choosing B over A; it's that it also introduces choice D ("die as a martyr in the name of Communism", as contrasted with "die for no particular cause"). Your ranking is now C > D > A > B.
You have to understand that Arrow's theorem came about as the result of an effort to understand the way that firms make decisions, and the ways that voting structures of boards can influence corporations to make non-optimal decisions for the corporation. Your situation doesn't really apply to the definition of independence of irrelevant alternatives as implied by the context in which Arrow's theorem is applied (or the formal proof thereof).
>Secondly, you're saying that, as soon as Communism becomes an option (but only then), you'd rather die than serve the royal family.
Well, maybe. Supposing there's some information contained in option C, or the mere availability of option C, that reveals to you the futility of option A.
In other words, your preferences aren't necessarily transitive because the availability or unavailability of particular options are themselves a little information payload that could influence the decision.
Are the counterexamples offered by the theorem pathological, in the sense that they are unlikely to occur in practice but are theoretically possible? Or would they arise in practice frequently using standard rank voting systems?
As long as politics is not one-dimensional, there are completely reasonable cases where you get a rock-paper-scissors situation between 3 top candidates if voters select whomever is closest to them. That in turn violates the criteria that says the election result can't change if you add a non-winning candiate (rock beats scissors, but when paper enters the race now scissors is computed the winner).
This criteria is called "independence of irrelevant alternatives". A common criticism of Arrow's theorems usefulness is that it is a bit of a stretch to call paper an "irrelevant alternative" when rock-paper-scissors forms a cycle of preferences like that.
If politics is one-dimensional ("single-peaked preferences" in the article), then you never get this situation.
It's also important to note that a much more reasonable criteria exists called "local independence of irrelevant alternatives". This is the idea that total losers joining the race don't affect the result, however someone who is in the top rock-paper-scissors cycle (the "Smith Set") can still affect the result even if they don't win themselves. This is far more reasonable, as it's fairly arbitrary which of the candidates in that top cycle should win.
When there is no top cycle, the Smith Set is a single person (the "Condorcet Winner"). When there is a Smith Set, most reasonable voting systems will pick their winner somewhat arbitrarily as a member of the Smith Set, since everyone in the Smith Set beats everyone outside the Smith Set.
> Are the counterexamples offered by the theorem pathological, in the sense that they are unlikely to occur in practice but are theoretically possible? Or would they arise in practice frequently using standard rank voting systems?
Which particular problems occur, and the frequency with which they occur, depend on the particular voting system.
Plurality and majority/runoff (which are ranked preference voting systems with a vary narrow constraint on the preferences that are expressed on the input ballots, which is pretty much the same constraint as on the preferences reflected in the output of any single-winner voting system) hits problems fairly frequently in practice, but most of the common voting systems that most people think of as ranked-preference systems (IRV, etc.) still hit them in practice as well, though not generally as frequently and in ways which create as clear incentives to tactical voting.
The "worry" is not that this-or-that fantastical scenario might play out. It is that, as it turns out, the very mechanisms we use to measure group preferences simply cannot satisfy a list of very basic requirements. For example, the reason we do not use random drawings to determine who gets elected president is that we want the choice to "reflect" our preferences on the whole: but the result shows that this kind of "reflection" is probably not possible, and is always distorted in some fashion by the very procedures we adopt to make these decisions.
In "standard" FPTP-like systems we frequently see real-world cases that encourage tactical voting. E.g. look at the French Presidential election where Le Pen went through to the final round because there were four leftist candidates that split the leftist vote.
Here's the version of the story with respect to voting:
Democracy requires voting. Voting involves an objective measurement of group preference with respect to choices. Arrow's theorem and related theorems (see Gibbard-Satterthwaite theorem) show that there is no way to objectively measure group preferences.
It is a theorem about the properties of all possible voting systems with preference rankings. The basic idea is there are a few desirable properties for any such voting system, but that it is mathematically impossible for any voting system to satisfy all of them.
> It is a theorem about the properties of all possible voting systems with preference rankings.
More accurately, it is a theorem about the properties of all possible voting systems where the input is voters preference rankings and the output is also a preference ranking.
There is a simple explanation in the introduction:
In short, the theorem states that no rank-order voting system can be
designed that always satisfies these three "fairness" criteria:
1. If every voter prefers alternative X over alternative Y, then the
group prefers X over Y.
2. 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).
3. There is no "dictator": no single voter possesses the power to
always determine the group's preference.
A "rank-order voting system" is one in which all voters order the possible choices, from most preferred to least preferred. The idea is that based on everyone's votes, and some set of rules on how to evaluate those votes, you can come up with a decision for the entire group that respects those preferences, in some way that is considered fair.
All of these requirements listed above seem like fairly simple requirements for a voting system to have; if there's unanimous agreement about the ordering of two of the choices, then the voting system should order them that way. If a voter changes preferences about one choice C (maybe changing between them being ranked above or below D, or above or below one of A or B), without changing their ordering between choices A and B, that shouldn't affect the outcome of the A/B ordering that the voting system gives you. And finally, there is not dictator; no single voter is able to always determine the group ordering unilaterally.
The first requirement seems pretty obvious; if everyone is unanimous that we should pick one option over another, then the group should pick that option.
The second is a little trickier; but it basically states that there shouldn't be able to be "spoiler"; someone whose ordering in people's preferences affects the ordering of to other choices. Think about, say, the 2000 election, with Bush and Gore and a couple of third party candidates; now, that used just single choices per voter rather than a ranking, but imagine it used a ranking. So let's say Bush and Gore are fairly close, but 51% of voters prefer Gore over Bush. Their preferences for other candidates should not affect the fact that Gore wins over Bush. If I rank candidates Nader > Gore > Bush, that should not change the Gore/Bush result compared to if I ranked the candidates Gore > Bush > Nader.
And the last is pretty trivially desirable; generally a democracy wants to democratically make a choice, in which everyone's vote has the same weight in affecting the final outcome.
The fact that these conditions are impossible to achieve together is fairly profound, and means that almost any voting system will have serious flaws under certain circumstances.
The impossibility is the impossibility of ensuring rational (transitive) outcomes amongst ranked preferences and adhering to a set of fair and democratic norms.
A rational transitive outcomes is one in which votes result in option A being preferred over option B and option B being preferred over option C, such that A is preferred over C (eg, A > B > C). Option A is known as the Condorcet winner.
But there may be cases where the vote yields no Condorcet winner (eg, A > B > C > A). This is illustrated by the following table:
Preferences Voter 1 Choc Vanil Strwb Voter 2 Vanil Strwb Choc Voter 3 Strwb Choc Vanil
Two voters prefer C over V and two prefer V over S, but two also prefer S over C.
To ensure transitivity, we can introduce voting rules, but it is impossible to introduce rules that do not violate the fair and democratic norms (referred to as the pre-specified criteria in the Wikipedia article: unrestricted domain, non-dictatorship, Pareto efficiency, and independence of irrelevant alternatives).