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 (firstname.lastname@example.org) 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.
|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|
|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|
|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|
|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|
|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.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|