Better Know a Theorem: Arrow’s Voting Theorem

02Feb10

The following is a book review I wrote thanks to a blog-based call for volunteers (technically I got paid with a free book). One of the main themes in the book is a theorem known colloquially as “Arrow’s Impossibility Theorem” for voting, which says that every voting system fails one of three simple axioms: non-dictatorship, agreement with unanimous pairwise comparisons, and “irrelevance of independent alternatives.” However, after reading the book, my view became that the last axiom is much too strong to expect any reasonable system to have. Also, this is the first math book I have ever read to involve Michele Kwan.

The review appeared in the SIGACT NEWS Book Review Column.

Review of Decisions and Elections: Explaining the Unexpected by Donald G. Saari

Reviewed by David Pritchard

In Decisions and Elections: Explaining the Unexpected, Donald Saari gives a highly accessible introductory tour of decision theory: the study of mechanisms that amalgamate several separate preferences into a single preference (for example elections, in which voters’ preferences over candidates are combined). The book has an excellent style that combines a deep understanding of mathematics, good pedagogy, and lighthearted prose; Saari provides compelling arguments, high-level insights, and interesting applications.

The book combines the nice flavors of paradoxes and puzzles, important real-world applications, and a good sense of humor. There are a number of examples drawn from engineering and group dynamics which make interesting food for thought. One example is about a non-voting chair of a meeting: even if she has no vote and thus seems powerless, she can tremendously determine the outcome of an election (page 91). Another example (page 54) is that in an engineering company, when solving a huge problem like the design of an aircraft, divide-and-conquer/decentralization is not always a good idea, as it can introduce new problems due to having to combine the answers to the various parts.

The book is aimed at undergraduates and professionals according to its introduction, and it seems it would serve this purpose well. I think many other people (e.g. researchers from related fields) would appreciate the book as an interesting, relatively quick read. The pedagogical style mostly eschews formality except where it is needed. Saari introduces new terms only after providing enough background to warrant them; I wish all mathematics authors had this skill! An example of the level of discourse is that Saari takes the time to explain a proof by contradiction (“If the Moon were Purple,” page 47). Thus, for example, I think that the book would make nice secondary reading material for a game theory class aimed at people from other disciplines. I would urgently recommend any future teachers/researchers in decision theory to read this book.

Summary of Contents

The central formal result in the book is Arrow’s theorem (1951): any group ranking mechanism with at least 3 candidates is either a dictatorship, fails to respect unanimous pairwise rankings, or allows some pairwise rankings to interact with others, i.e. fails to have “Independence of Irrelevant Alternatives.” Saari gives a full proof, but defers it to the appendix due to its technical nature. Literature references also occur only in the appendix, giving the book high readability but also giving the interested reader pointers to more details. Proofs are usually sketched, and sometimes omitted. The flip-side of this approach is that sometimes the reader is not precisely sure what Saari means; although usually, ambiguities either can be clarified with a little effort of the reader, or are made clear later in the book.

Saari spends a considerable amount of time looking at the ramifications of Arrow’s theorem, and discussing variants. Over the course of the book, one accumulates the view that Arrow’s theorem should be thought of as saying that Independence of Irrelevant Alternatives (IIA) is too strong to expect from a reasonable voting system. Here are two nice results in this vein: first, even with a weaker version of IIA where we consider triples instead of pairs, Arrow’s theorem still holds (Section 5.4); second, if we replace IIA by a more detailed variant “Intensity of Binary Independence,” then Arrow’s theorem fails to hold (Section 6.5). The book acts in part as an introduction to some of Saari’s research from the last two decades, e.g. both of the aforementioned results come from publications of Saari and coauthors.

Sen’s theorem (1970) is discussed at length. In a decision mechanism, a given voter is “decisive” over two given alternatives if the mechanism’s ranking of those two always agrees with that voter. Then Sen’s theorem says that for any ranking mechanism with at least two decisive voters (over any two pairs of alternatives), that mechanism will sometimes disagree with a pairwise ranking agreed on unanimously by all voters. Saari phrases this differently: if unanimous pairwise rankings are to be respected, then the mechanism sometimes produces cyclic preferences (i.e., not a ranking). Saari gives a number of examples which illustrate applications — sharing an apartment, book censorship, and a stock-buying club — which at same time illustrate the most important ideas in the full proof of Sen’s theorem.

An explicit mantra in the book has to do with what goes wrong in the standard impossibility results of Arrow, Sen, and others. Saari notes that in many cases, a potential explanation is that we are disregarding valuable information: e.g. in Arrow’s theorem, we essentially throw away the voters’ full preference lists and focus only on pairwise rankings. We read on page 97 that “suspect outcomes can occur should the decision procedure ignore portions of the available information.” Saari notes more concretely that even irrational voters with cyclic preferences can submit pairwise rankings, but if we want to think rationally about a good voting procedure, we should certainly demand that the voters be rational!

Saari pinpoints a certain sub-structure, a “Condorcet tuple,” as the source of many problems. E.g. in a Condorcet triple, we have three players, one of whom prefers outcome A to outcome B to outcome C, another who prefers B to C to A, and a third who prefers C to A to B; then any global ordering upsets a majority of the voters in at least one pairwise comparison. Small modifications to this sort of example are fodder for the book, and Saari describes a certain result saying that indeed all impossibility results of a certain type come from modifications of Condorcet tuples, although I did not find his description of this result clear enough to properly parse.

If one were to read Saari’s book with the goal of choosing a voting system to put in to practice, the reader would be very persuaded to use the Borda Count: each voter ranks all n candidates and gives n points to their top-ranked one, n-1 to their second-ranked one, and so forth; then we order the candidates by total points. This avoids some problems of the usual plurality vote (where each voter contributes just one point to their favorite candidate) and has several other nice properties, for example the Borda Count is the only ranking mechanism which is never backwards in all pairwise comparisons, i.e. it ranks at least one pair of candidates in accordance with the majority of voters (Section 5.4.3). On page 193 Saari mentions a few other natural conditions that together get “close to creating an axiomatic representation of the Borda Count” although he later (in Section 8.3.2) tempers this by pointing out that axiomatic representations alone do not warrant a given protocol is best. For the election-designer, Saari’s book has no explicit advice (unfortunately) on what to do if more than one candidate should be elected, although there is certainly lots of implicit advice in the book. I should also note that, according to Wikipedia, the Borda Count is generally not used in practice, but replaced by other mechanisms with better properties; it would have been nice if Saari attempted to describe what sort of sophisticated voting methods are used in practice and what distinguishes them from the Borda Count.

Style and My Opinion

The book is sprinkled with a lot of specific small abstract examples, and also relevant real-world examples steeped in modern culture. The initial abstract examples in the first couple of chapters illustrate that even for a fixed set of preferences, different choices of reasonable-looking voting procedures can yield drastically different results; and often, the results of a vote seem clearly not to agree with the intent of the voters. Some of the real-world examples include Ross Perot’s Reform Party, the election of Jesse “The Body” Ventura, and scoring in professional figure skating (where IIA fails to hold). It is quite helpful to see these connections between theory and real life. The ubiquitous Prisoner’s Dilemma is given an atypical presentation — usually notions from strategic games are used but since this is the only strategic game in the book it would not make sense. I liked the Prisoner’s Dilemma example of two lanes merging on the highway, which I had not seen before. (Here two drivers may either be polite or a jerk, where each driver gets home faster as a jerk regardless of the other drivers, but two polite drivers get home faster than two jerks.)

I have a few general criticisms of the book. The lack of formality is a promising approach but sometimes important terms are used before they are introduced or informally defined.  E.g. I was several times confused whether a “decision procedure” or “choice procedure” is supposed to give a ranking of candidates, or just a (possibly cyclic) list of pairwise rankings. Smoothing problems like this would save readers time. Likewise, there are a number of grammatical and numerical bugs which slow the reader down. At a higher level, I found the numerous small examples in the first couple chapters to lack structure, in the sense that I didn’t quite see how each one differed from the other, and so they appeared repetitive. Likewise, the discussion and corollaries surrounding the discussion of Arrow’s theorem in Chapter 2 seemed repetitive. Section 7.2 mentioned some nice theorems involving “strong” rankings; but since this term was never even precisely defined informally, that section only read like a mathematical parable, taking the details on faith.

The book sometimes has too many “scare quotes” in a small section. Let me take one funny quote from page 185 as an example:

All this “coordinate component” and “fractional voter” tech talk makes Theorem 10 seem impractical and restricted only to those weird “number-crunchers” whose sense of a “hot Saturday night” is checking new web features while designing a C++ program. Fortunately, this is not the case. What saves us from this nerdy fate is [a property of the Borda Count.]

To conclude I will mention the top reasons that I liked the book. It shed light on fundamental results that I never fully understood before (Arrow’s theorem, Sen’s theorem, Black’s single-peaked condition). I learned of new interesting fundamental theorems (e.g. the extensions of Arrow’s theorem to quasi-transitive or restricted preferences in Chapter 6, where a dictator is respectively replaced with an oligarchy or partial dictator). Its mantras gave new high-level perspectives which would be useful for guiding research or in practice. Finally, I enjoyed the folksy writing style; if you appreciate real-life (or plausible-fake) stories in mathematical discussion, then you probably would enjoy this book.

Advertisements


4 Responses to “Better Know a Theorem: Arrow’s Voting Theorem”

  1. I gather you’ve also read about the Gibbard–Satterthwaite theorem? It’s fairly similar to Arrow’s, but a little clearer, I think.

    • Up until reading this book I had heard all of them but would be hard pressed to identify one from the other in a line-up. After reading it on Wikipedia, I would say G-S avoids talking about pairwise comparisons but on the other hand you need to assume a voter has full information about others to describe the result.

      The link you included seems nice… sort of like Doodle for elections?

      • Hrm. Hadn’t seen Doodle before, but I can see the similarities. They’re both for elections, but Doodle is geared towards a specific use-case. It has a two-stage vote: a 0-2 range vote for the When, and a 0-1 range vote (aka approval) for the What.

        I see this approach breaking down in some edge cases where the What and the Where are coupled. Consider a case where people slightly lean to Friday over Saturday, but strongly prefer restaurant A over B. Unfortunately, B isn’t open on Friday. Such cases might not arise frequently, but it’s worth noting.

      • Hey, I went to Waterloo too! Graduated in CS with a minor in C&O back in 2003. Small world. 🙂


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


%d bloggers like this: