Who’s Afraid Of Arrow’s Paradox?
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 choices from a larger set of 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 ”
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?
Here are three “fairness” criteria that would seem to be axiomatic in any voting system:
- Unanimity: If every member prefers candidate over candidate , then the committee prefers over .
- Non-dictatorship: No single member possesses the power to determine the commitee’s preference in all cases.
- Focus: If every member’s preference between and remains unchanged, then the committee’s preference between and will also remain unchanged, regardless of any changes in preference between pairs or or with .
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 versus should depend only on the merits of what each individual thinks between and , 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 be the set of permutations of candidates, interpreted as rankings, and let be the number of committee members. Then a voting system is a map from to . Let be the subset of in which is ranked higher than and its complement. For any , define
where if and if . Then Arrow’s Theorem states that if always maps into and does not depend on any single argument, then there must exist such that the range of restricted to is not wholly contained in either or .
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 when every committee member gives 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 not as the minimal number of committee members, and consider candidates . The problem is what to do if the members’ permutations are , , and . Then a majority prefer , a majority prefer , and a majority prefer . 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 of seats, then non-monotone situations can arise where a few extra votes or an increase in 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?
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 , followed by a transformation they call “local Kemenization,” and gives an application for identifying spam.
How should we decide when we are on a committee and are faced with a real decision?