You are here

Social Choice and the Mathematics of Manipulation

Alan D. Taylor
Publisher: 
Mathematical Association of America and Cambridge University Press
Publication Date: 
2005
Number of Pages: 
176
Format: 
Paperback
Series: 
Outlooks
Price: 
24.99
ISBN: 
0-521-00883-2
Category: 
Monograph
[Reviewed by
Darren Glass
, on
12/28/2005
]

It seems like every election cycle brings with it a growing interest in the mathematics of elections. Whether it is due to an increased effort among mathematicians to sell our field, an increased use of mathematics and statistics by political scientists, or the presence of strong third party candidates in three of the last four elections (not to mention those hanging chads...), it seems to me that accounts of Arrow's Theorem and similar results have been showing up with increasing frequency in colloquium talks for students, articles in the newspaper (not to mention MAA Online), as well as in textbooks for math courses aimed at humanities students. When you also throw in the large number of articles about the Bowl Championship Series and related issues in sports, it becomes clear that there is a growing interest in the mathematics of voting systems, also known as social choice theory.

However, until recently there has been a problem facing mathematicians who are interested in learning about this field. While there are lots of short expository articles which give you a flavor of the field (I particularly enjoyed Dana Mackenzie's article in Discover magazine in November of 2000), and lots of research papers which go into many technical details but do not give significant background information or an overview of the field, there has been a lack of much in the middle. If you wanted a book that started at the first step and went through a detailed treatment of the mathematics, there were not very many choices, and many of those choices were in the Political Science or Economics literature and did not do as much justice to the mathematics as many mathematicians would like. I am pleased to say that this is no longer the case, as Alan D. Taylor's recently released Social Choice and the Mathematics of Manipulation fits this bill perfectly.

Make no mistake about it — this is a serious math book, which develops things in a serious way. I started reading this book in bed, and quickly found that I needed to be sitting at my desk scribbling notes to keep track of all of the definitions and notation to follow his development of the material. But if you put the energy into the book, it pays off, as Taylor gives an excellent overview of the field of voting theory. He begins with a chapter filled with motivating examples and a small amount of history before diving right into a description of Arrow's Theorem, which (roughly) says that in an election between three or more candidates there is no voting system which satisfies a handful of nice properties. The final section of the first chapter gives the details for twenty different possible rules for a voting system, including the unanimity rule (an option has to be everyone's first choice — or tied for their first choice — to win), the dictator rule (in which a single person's first choice wins regardless of what anybody else wants), the antidictator rule (where a single voter's last choice wins), the plurality rule, and sixteen others. He also lists in detail six properties that we may want a voting rule to satisfy (including anonymity, which the dictatorship and antidictatorship certainly fail, and neutrality, for example).

The second chapter introduces the notion of manipulability and set preferences. We would all agree that honesty is the best policy, and therefore that we would like a voting system in which it is never to your advantage to lie about who your preferred candidate is in order to get a more desirable outcome. [Insert snarky comment about people who voted for Nader in 2000 here.] In the second chapter of his book, Taylor makes these notions more precise, discussing concepts such as single-winner manipulability, manipulability by optimists or pessimists, and agenda manipulability. The third chapter of the book continues the discussion of manipulabilty by giving a detailed treatment of the Gibbard-Satterthwaite Theorem, which was established independently by a philosopher (Gibbard) and an economist (Satterthwaite) in the 1970s and which says (again very roughly) that the only non-manipulable voting schemes are dictatorships.

This ends the first part of the book, all of which is very accessible. Taylor litters the first half of the book with many exercises, some of which are computational, while others are more theoretical. These exercises, along with the thorough yet accessible treatment of the subject material, would make this book very useful as a textbook in a course on these theories, perhaps taught jointly with a political science department. The second part of the book gets even more technical, and would likely be much more difficult for a non-mathematician to follow. Chapter Four looks at the situation where the outcome of an election is no longer a single winner but instead may be a set of winners. While Taylor does not discuss how this would work in real life — this reviewer cannot help but think of Saturday Night Live's 'Presidential Odd Couple' skit from November of 2000 — he does discuss some interesting generalizations of the Gibbard-Satterthwaite theorem and similar results. There is also a nice section which discusses expected utility results in the context of non-resolute voting systems, and how voters might choose to prefer certain sets of winners over other sets of winers, depending on the tie-breaking procedures.

The fifth chapter of the book delves deeper into the idea of social choice functions — that is, a scenario where out of a given set of preferences we want to determine not a winner (or set of winners) but rather a way of choosing a winner (or set of winners) from any nonempty subset of the original collection of choices. Again, we are concerned with which methods for determining a social choice function are manipulable, and more specifically what it even means for these to be manipulable. The final chapter in part two moves into the realm of the infinite, and asks what we can say if there are either an infinite number of voters or an infinite number of candidates on the ballot, a scenario approximated by the 2003 California Gubernatorial race, though Taylor does not prove the conjecture that these scenarios will always lead to movie stars getting elected. Instead, he focuses on results such as an infinite version of Arrow's Theorem and the Gibbard-Satterthwaite Theorem, which requires introducing the concept of ultrafilters — collections of subsets which have certain nice properties that imply nice properties of the related social welfare functions — to make them precise.

The third part of the book consists of three more technical chapters on a variety of results which are interesting, though not as integral to the cohesive narrative throughout the rest of the book. These sections read much more as though they are excerpts from papers in the literature of the field, and in the final chapter of the book, the author changes the very definition of what elections look like, considering situations such as approval voting and quota systems. It is hard to imagine using these later chapters in a course, but they make for very interesting reading, at the level of articles in American Mathematical Monthly — highly readable, yet technical enough that they require real thought rather than just skimming through the results.

I thoroughly enjoyed reading Social Choice and the Mathematics of Manipulation. Several times while reading it, I would find myself popping over to visit my colleagues in the Political Science department, as I was eager to hear their thoughts on these subjects to learn about the field from their perspective. However, full disclosure forces me to note that when I showed Taylor's book to one of these colleagues, he recoiled in fear upon seeing some of the technical mathematics contained even early on in the book. So there is little doubt in my mind that this is a book for mathematicians, or at the very least people who are mathematically inclined. But for those of us who are mathematically inclined (which I imagine is true of most perusers of MAA Online) and wish to learn some of the serious mathematics happening in the field of political science, Taylor's book provides a great introduction.


Darren Glass (dglass@gettysburg.edu) is an Assistant Professor at Gettysburg College. His mathematical interests include number theory, cryptography, algebraic geometry, and Galois theory, but please don't make him put those in order of preference.

 

Preface
  PART ONE
1   An Introduction to Social Choice Theory 3
  1.1  Some Intuitions, Terminology, and an Example 3
  1.2  A Little History 9
  1.3  Arrow’s Theorem 13
  1.4  Twenty Voting Rules 20
  1.5  Exercises 29
2   An Introduction to Manipulability 37
  2.1  Set Preferences and Manipulability 37
  2.2  Specific Examples of Manipulation 44
  2.3  Summary of the Main Results 51
  2.4  Agenda Manipulability and Transitive Rationality 53
  2.5  Exercises 56
3   Resolute Voting Rules 60
  3.1  The Gibbard–Satterthwaite Theorem 60
  3.2  Ties in the Ballots 68
  3.3  The Equivalence of Arrow’s Theorem and the Gibbard–Satterthwaite Theorem 69
  3.4  Reflections on the Proof of the Gibbard–Satterthwaite Theorem 72
  3.5  Exercises 77
  PART TWO
4   Non-Resolute Voting Rules 81
  4.1  The Duggan–Schwartz Theorem 81
  4.2  Ties in the Ballots 87
  4.3  Feldman’s Theorem 88
  4.4  Expected Utility Results 95
5   Social Choice Functions 102
  5.1  The Barberá–Kelly Theorem 102
  5.2  Ties in the Ballots 109
  5.3  Another Barberá Theorem 110
  5.4  The MacIntyre–Pattanaik Theorem 113
6   Ultrafilters and the Infinite 118
  6.1  The Infinite Version of Arrow’s Theorem 118
  6.2  Infinite Gibbard–Satterthwaite without Invisible Dictators 122
  6.3  Invisible Dictators Resurrected 123
  6.4  Infinitely Many Voters and Infinitely Many Alternatives 125
  PART THREE
7   More on Resolute Procedures 133
  7.1  Combinatorial Equivalents 133
  7.2  Characterization Theorems for Resolute Voting Rules 136
  7.3  Characterization Theorems for Resolute Social Choice Functions 140
  7.4  Characterizations for Resolute Social Welfare Functions 142
8   More on Non-Resolute Procedures 147
  8.1  Gärdenfors’ Theorem 147
  8.2  Characterization Theorems for Non-Resolute Voting Rules 152
  8.3  Another Feldman Theorem 154
  8.4  Characterization Theorems for Non-Resolute Social Choice Functions 157
9   Other Election-Theoretic Contexts 160
  9.1  Introduction 160
  9.2  Ballots That Are Sets: Approval Voting and Quota Systems 160
  9.3  The Barberá–Sonnenschein–Zhou Theorem 163
  9.4  Outcomes That Are Probabilistic Vectors: Gibbard’s Theorem 164
  References 167
  Index 173