[schmit]

In short:

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.

[chimeracoder]

This is correct, with one addition:

> 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.

[0] https://en.wikipedia.org/wiki/Amartya_Sen

[1] https://en.wikipedia.org/wiki/Instant-runoff_voting

[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.

[brownbat]

> (Nader, Bush, Gore) is much less likely

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.

(I was young, ok?)

[mkehrt]

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!

[kragen]

That sounds very interesting! How did your nonterminating election procedure work?

[mkehrt]

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.

[reagency]

Did work? It is still working to this day...

[sampo]

> 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.

[JoshTriplett]

Also see http://en.wikipedia.org/wiki/Category:Voting_system_criteria for other potentially desirable criteria for voting systems.

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.

[ffn]

>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.

[chimeracoder]

> 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).

[asanagi]

>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.

[jonahx]

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?

[YokoZar]

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.

[dragonwriter]

> 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.

[logicchop]

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.

[stephencanon]

http://en.wikipedia.org/wiki/Burlington_mayoral_election,_20...

[lmm]

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.