Arrow's Impossibility Theorem

Sometimes known as the Arrow Paradox, after Kenneth J. Arrow. Three candidates are vying for the position of Governor: Achilles, Carroll, and Zeno. In a poll, 2/3 of the voters polled prefer Achilles over Carrol, and 2/3 prefer Carroll over Zeno. You would expect that most voters would therefore prefer Achilles over Zeno. Not necessarily...
If the voters ranked their preferences as follows, most preferred to least preferred, each candidate can say he is preferred over another candidate:
   1/3: A C Z
   1/3: C Z A
   1/3: Z A C

This seeming paradox occurs because we expect the problem to obey the mathematical law of transitivity. As a problem in Game Theory, it is not bound by transitivity.

Any situation where at least 3 alternatives are ranked pairwise by at least 3 criteria can give rise to this sort of paradox. For instance, a man choosing between three possible brides may evaluate their respective strengths in sexual skill, economic advantage, and social grace. Assuming each criterion carries equal weight, he may find himself in the predicament of preferring Amy to Bev, Bev to Chrissy, and Chrissy to Amy.

A Blather of Paradoxes

<-- Arcology | Transhumanist Terminology Index | Artilect -->

---

In 1952, mathematical economist Kenneth J. Arrow proved a rather remarkable theorem.

"There is no consistent method by which a democratic society can make a choice (when voting) that is always fair when that choice must be made from among 3 or more alternatives."

Given that society has a habit of using various voting methods to determine anything from political office, to the location of large events such as the Olympics, to ranking of sports teams, this is a big deal. But it has been proven that using any method of voting, it is possible to get a set of results whereas the winner is in some manner irrational given the votes submitted. Every voting system in existence - and every system that has yet to be invented - has a flaw. This has been proven, mathematically.

Here's a simple example. We'll use the voting method employed in the United States, where each voter only votes for their top choice. There are three candidates, A, B, and C.

The results? A gets 27% of the vote. B gets 33% of the vote. This leaves C with 40% of the vote. Now, C would be declared the winner - this, even though a majority voted AGAINST C.

A better example... suppose we let the voters list the three candidates in their order of preference.

             49% Voters    45% Voters    6% Voters

  1st Choice      C             B            A

  2nd Choice      B             A            B

  3rd Choice      A             C            C 

Now, candiate C obviously won the decision here. However, if you look at the last choice among the voters, the 51% who did not put candidate C as their first choice put him as their LAST choice.

Candidate B would be able to argue, rather convingly, that he is in fact the favorite, as he was not listed as anyone's last choice. Yet he wasn't the winner.

For those with knowledge in this area, here's something more formal.

Let Prefers_i(a,b) mean that person i prefers a to b. Let Prefers be some joint decision procedure that, thus, generates either Prefers(a,b) or Prefers(b,a) for any a, b in some decision set, Set.

Then Arrow's impossibility Theorem says that the following 5 reasonable conditions on the joint preference relation Prefers cannot all be met by any single decision process:

1.Prefers is independent of irrelevant alternatives that is to say, the ordering of any 2 items in Prefers is a function only of their ordering with respect to each other within each of the Prefers_i.
2.Prefers is non-dictatorial that is to say, Prefers is not necessarily identical to Prefers_i for some i.
3.Prefers is pareto-inclusive that is to say, Prefers will rank 2 elements of Set in a particular order if all Prefers_i do.
4.Prefers is transitive.
5.Prefers is a complete ordering on Set.

This theorem was first published in A Difficulty in The Concept of Social Welfare.

_{Sources:
Social Axiom, http://www.geocities.com/TimesSquare/Lair/3936/theme/axiom_social.html
Arrow's Impossibility Theorem, http://www.personal.psu.edu/staff/m/j/mjd1/arrowimpossibilitytheorem.htm}

I'm not sure the above writeup gives the full story, so allow me to jump in.
As stated above, Arrow puts forth 4 burdens on an ideal voting system for a democracy:

1. Universal Domain - The system should be able to contain any possible social choice
2. Independence of Irrelevent Alternatives - An individual preference stated in binary terms (one over the other) shouldn't affect his/her or other's ordering of other preferences. Ex: Liberal voters in America considering the choice between Ralph Nader and Al Gore shouldn't have to worry about inadvertently electing George W. Bush with their vote for Nader.
3. Pareto Optimality - If every individual votes the same way, the society is decisive.
4. Nondictatorship - More than one person's vote should be used in determining social choice

The Arrow Theorem, in simple terms, says that no voting system can satisfy all 4 above criteria. The only way voting systems work, then, is by relaxing one of the criteria (which in practice is usually universal domain). The proof of the theorem is rather simple and elegant. It makes use of two principles:

• If everyone agrees to one choice of a set, then the society is decisive. (This is a corollary of the Pareto Principle)
• If a group of two or more people are decisive, than any smaller groups contained in this this group are also decisive.

The problem? If each larger group is subdivided into smaller groups of identical preference, the second principle says that group can be subdivided as well. Thus, when the process is over we arrive at the vote of one person. This person is the dictator of the system, thus failing the fourth criterion.

---

Sources:
Sen, Amartya. Rationality and Social Choice. American Economic Review, March 1995. Vol 85, No. 1
http://www.cs.byu.edu/info/mikeg/CS501R/lectures/Arrow.html