Skip to content

Who’s Afraid Of Arrow’s Paradox?

November 3, 2011


How to decide, when you really have to decide.

Kenneth Arrow was a co-recipient of the 1972 Nobel Memorial Prize in Economics—note this is a “Nobel” prize, but is a bit different from the original ones. It still is immensely prestigious, but it is a more recent creation. Arrow is famous for his impossibility result, which shows that there is no “good” voting system.

Today I want to talk about what should we do if we have to vote?

I often find myself on committees whose sole purpose is to make a multiple-choice decision, meaning to select {k} choices from a larger set of {n} choices. This happens for award committees, for membership committees, for program committees, and for various other committees. The key is that the committee is charged with selecting more than one choice from a large number of choices.

I also often find myself on committees whose sole purpose is unclear—perhaps there is no purpose. While I was at Princeton an administrator called a meeting that Hector-Garcia Molina and I had to attend. We ran into the administrator, a few days before his meeting, and after saying hello Hector asked, “what is the agenda of the upcoming meeting?” The answer was “two hours.” Unfortunately this was a short clear answer that was honest and correct.

The Voting Dilemma

Back to committees that do make decisions. The famous Arrow Theorem, see below if you are not familiar with it, shows that there is no voting system that really works. All systems can lead to “paradoxical” outcomes. But decisions need to be made: awards have to be given, members selected, papers accepted, and so on. The puzzle is:

What should we do in practice?

My experience on committees is very mixed. Some seem to operate in a rational manner, while others use strange ad-hoc techniques to make their decisions. The usual approach is to rank the choices—let’s call them candidates—and then select the top ones and drop the bottom ones. This { } initial selection can often be done with fairly good agreement—of course the ones on the border of that can still be hard. Then the committee has the difficult job of selecting from the remaining candidates. They are usually very close, and it can be extremely hard to make the final choices.

This final step of deciding on the “middle” candidates is where the strange techniques appear. My experience is that the chair usually has a pet or in-house tie-breaking scheme. It may be a voting method based on points, for instance your first choice gets 1 point, the second 2 points, and so on, with the lowest ones being selected. Sometimes voting methods are created on the fly—a member of the committee will say, “why don’t we {\dots}

I know that there is no “best” method, and all methods can be “gamed,” but I still wonder what we should do? Are there in some sense methods that are better than others?

Arrow’s Theorem

Here are three “fairness” criteria that would seem to be axiomatic in any voting system:

  • Unanimity: If every member prefers candidate {X} over candidate {Y}, then the committee prefers {X} over {Y}.
  • Non-dictatorship: No single member possesses the power to determine the commitee’s preference in all cases.
  • Focus: If every member’s preference between {X} and {Y} remains unchanged, then the committee’s preference between {X} and {Y} will also remain unchanged, regardless of any changes in preference between pairs {X,Z} or {Y,Z} or {Z,W} with {Z,W \notin \{X,Y\}}.

The first two seem especially basic. If there were a dictator, then perhaps we could just skip the meeting. Perhaps no, since the meeting still has an agenda, even if the agenda is just “two hours.” The third is more commonly called the “Independence of Irrelevant Alternatives” (IIA) axiom. It sounds reasonable because surely the group preference for {X} versus {Y} should depend only on the merits of what each individual thinks between {X} and {Y}, no? No:

Theorem: When there are at least two committee members and at least three candidates, there does not exist a system of voting that meets the above three axioms.

Formally, let {P} be the set of permutations of {n} candidates, interpreted as rankings, and let {m} be the number of committee members. Then a voting system is a map {f} from {P^m} to {P}. Let {P_{x>y}} be the subset of {P} in which {x} is ranked higher than {y} and {P_{x<y}} its complement. For any {a \in \{0,1\}^m}, define

\displaystyle  R_{x,y}(a) = P_1 \times \cdots \times P_i \times \cdots \times P_m

where {P_i = P_{x>y}} if {a_i = 1} and {P_i = P_{x<y}} if {a_i = 0}. Then Arrow’s Theorem states that if {f} always maps {R_{x,y}(1^m) = P_{x>y}^m} into {P_{x>y}} and does not depend on any single argument, then there must exist {x,y,a} such that the range of {f} restricted to {R_{x,y}(a)} is not wholly contained in either {P_{x>y}} or {P_{x<y}}.

There is a related theorem by Allan Gibbard and Mark Satterthwaite that extends to systems that work by members giving points rather than preference rankings. Even if the goal is to select just a single winner, the theorem says that every system that always selects {x} when every committee member gives {x} highest points, and that isn’t dictated by a single committee member, is susceptible to being “gamed” by a member seeking an outcome different from the ranking given by the member’s points.

The Aggravation of Aggregation

The root of all the difficulty is well known. To avoid tiebreak issues we regard {m=3} not {m=2} as the minimal number of committee members, and consider {n = 3} candidates {x,y,z}. The problem is what to do if the members’ permutations are {p_1 = x > y > z}, {p_2 = y > z > x}, and {p_3 = z > x > y}. Then a majority prefer {x > y}, a majority prefer {y > z}, and a majority prefer {z > x}. Who should win?

Related issues involve parliamentary systems that allocate seats to parties based on proportions of the total vote. If you follow the quota rule of giving each party either the integer floor or the integer ceiling of its share of the vote times the total number {N} of seats, then non-monotone situations can arise where a few extra votes or an increase in {N} can cause a party to lose a seat. These situations also affect the number of Congressmen given to states after each U.S. Census.

In committee situations, of course, one usually weeds out the lowest choices altogether. Then the problem becomes, how to re-evaluate the rankings or points given by the members who preferred them? This leads to the issue of runoff methods for elections with more than two candidates, which are also fraught with paradoxes.

For one example, in the women’s figure skating final group at the 2002 Winter Olympics in Salt Lake City, Sarah Hughes stormed from 4th place to win ahead of co-favorite Michelle Kwan, who was pushed to 3rd behind Irina Slutskaya. This article explains that had Slutskaya suffered one more fall, Kwan would have won the gold, despite the feeling based on IIA that how badly a third skater performed should not disturb the focus between Kwan and Hughes. (This had nothing to do with the ice-dancing judging scandal from the same Olympics, but did play into the creation of the new ISU Points System in 2004.)

A term more general than voting for the problem is aggregation of multiple preferences into one rank order. Every time one searches on Google, one sees the rank result of an aggregate score based on a “commmittee” of page-rating criteria. Google has evidently chosen an aggregation method that suits its own criteria, at least most of the time. That leads to our query: can we identify situations for committees in which there does exist a procedure that is (nearly) always satisfactory?

Voting Methods

There are a vast array of voting methods that committees can use. All can have paradoxes, but all have some properties that make them interesting. Many are used in real situations, but the fact that the list of methods is so long suggest that this is far from a solved problem. Here are some:

  • Highest averages
  • D’Hondt method
  • Sainte-Laguë method
  • Largest remainder
  • Hare quota
  • Droop quota
  • Wright system
  • Parallel voting

This problem has been studied through the centuries, and even Lewis Carroll contributed theory to it. What we ask is whether there has been a good mapping of methods to categories of applications where they are most appropriate. We note for instance this paper by Cynthia Dwork, Ravi Kumar, Moni Naor, and Ken’s former student D. Sivakumar while he was at Google. This proposes using Markov Chains to combine the initially-given {P_i}, followed by a transformation they call “local Kemenization,” and gives an application for identifying spam.

Open Problems

How should we decide when we are on a committee and are faced with a real decision?

18 Comments leave one →
  1. Mogden permalink
    November 3, 2011 11:55 pm

    It’s hard to determine the best system – we should probably vote on it.

  2. November 4, 2011 2:19 am

    I am glad you mentioned figure skating, as the same things happen in sports. In most team sports there is a group stage of which the top few qualify and it is inevitable that whether A or B qualifies may depend on a match between C and D. The same holds for boards games, where a decision of C can determine whether A or B wins.

  3. Petter permalink
    November 4, 2011 10:21 am

    Arrow’s theorem only applies to complete orderings of candidates. I think approval voting is a good voting system.

  4. Jeff U permalink
    November 4, 2011 10:50 am

    Actually, the no-dictatorship assumption is not as innocuous as it seems. It is appealing because if one person controls all outcomes then the whole process appears irrelevant. This would be true if a particular individual had the power a priori to determine the outcome, but the no-dictatorship assumption comes into play combinatorially in a rather more subtle way. Specifically, it may be the case that the group is divided in such a way that a particular individual’s vote “happens” to tilt the preference one way or the other in all cases. There may be several individuals for whom a switch of vote will switch the preference in most cases, but it turns out that among these there will be one whose switch of vote happens to impact all cases. That individual wouldn’t be recognized in the context of, say a committee, as being a “dictator” but the cards may just happen to fall in a way that his is the determinative vote. If the no-dictatorship assumption is dropped – or changed to “no a priori dictatorship” – then the paradox goes away.

    • September 20, 2014 7:47 am

      Umm, no I don’t believe that works.

      The non-dictatorship assumption simply requires that for every committee member Bob at least one possible set of preferences of the committee members results in a ranking of the outcomes that isn’t equal to Bob’s ranking.

      In other words for Bob to be a dictator *requires* that even if everyone but bob agrees on some other preference ranking they still always do what Bob wants.

      Unless one imagines that the mechanism for aggregating preferences is kept secret this also entails that if a voting system is deterministic and fails to satisfy the non-dictatorship condition then everyone can deduce (without knowledge of anyone’s preferences) both that there is a dictator and which individual is the dictator.

      Obviously, one can avoid this if you simply randomly select a committee member and let them be the dictator but short of non-determinism anything that fails the non-dictatorship clause has a dictator in the natural language sense.

  5. November 4, 2011 12:04 pm

    Does range voting fix the problem?

    http://en.wikipedia.org/wiki/Range_voting#Properties

  6. Anonymous permalink
    November 4, 2011 2:30 pm

    A sad intro to a giant, whom the distinguished Yale professor, Herbert Scarf, had called “the smartest man on Earth!”

  7. November 4, 2011 3:12 pm

    sorry, i can’t help myself. this is too fun to alternatively parse:

    Q: How should we decide when we are on a committee and are faced with a real decision?

    A: When you’re in a room with a lot of other people and someone asks you something interesting.

    s.

  8. November 6, 2011 10:56 am

    You might enjoy the following paper, by Emily Shen and myself:
    http://people.csail.mit.edu/rivest/gt/latest_conf.pdf
    which proposes that you can use two-person game theory to arrive
    at the “best” voting system.
    Cheers,
    Ron Rivest

  9. Joe permalink
    November 7, 2011 4:38 pm

    Here’s an interesting discussion on Hacker News about using a random ballot approach.

    http://news.ycombinator.com/item?id=2484677

  10. November 15, 2011 10:07 am

    In the special case of academic comitees, I can report heavy use of completely objective, but arbitrary external stimuli. For instance, imagine you were to decide which person to make a professor and you (the comitee) can not rank a woman and a man definitely. External stimuli are: you have to justify rejecting the woman far more than the man because of gender mainstreaming policies (–> more work). The woman will be better funded because there are special funds for female researchers (–> more money, more people, more research done). Ergo you decide for the woman even iff both candidates can not be separated for their own value.

  11. December 1, 2011 4:31 pm

    I had an experiece with a committee needing to select several people among a list. (You can think about it as several foorball managers selecting together a football team.)

    One of the methods I used in the process is a variant of approval voting. In approval voting each voter gives each candadate a score which is 0 or 1. In my variants the score was 0 or a polynomial of the form 1+t+t^2+…+t^k. (we used only k<=2) The votes were added to form a polynomial in t with integers coefficients and t was regarded as infinitesimally small.

    Another variants of approval voting I tried to use is "approval voting with constraints" so a voter can also make constraints of the form "I approve A,B,and C individually but at most two out of A,B,C".

Trackbacks

  1. …And To Make A Long Story Short— « Gödel’s Lost Letter and P=NP
  2. A Negative Impossibility Theorem | Gödel's Lost Letter and P=NP
  3. Enriching the Frankl Conjecture | Gödel's Lost Letter and P=NP
  4. Two Versus Three | Gödel's Lost Letter and P=NP
  5. The Anti-Pigeonhole Conjecture | Gödel's Lost Letter and P=NP
  6. Rankings Versus Ratings | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s