You are here

Handbook of Computational Social Choice

Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors
Cambridge University Press
Publication Date: 
Number of Pages: 
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Karl-Dieter Crisman
, on

Regular readers of MAA Reviews might be familiar with the concept of social choice. Briefly, social choice (as a discipline) seeks to understand mechanisms by which one might aggregate preferences of various kinds into a societal decision. Examples might include how we aggregate preferences in an election to a winner, or aggregating preferences for teaching different courses into a course schedule for a semester.

That said, social choice today encompasses a huge variety of questions, many of which are far from topics such as voting theory or fair division of resources which appear in many “liberal arts mathematics” collections. Now enter the computer age; we can say “computational social choice” is that discipline which is at the interface of computer science (as a discipline) and social choice (an already interdisciplinary effort). As the editors of the book under review reinforce, this could either be in terms of algorithmic analysis (not just computational complexity) of, e.g., voting systems, or in terms of finding new vistas for choice ideas. For an example of the latter, look no further than your Netflix queue or eBay rating, which aggregate other users’ predilections into a personal choice for your search.

If you are looking for a textbook for teaching a course (for majors or not) in voting and choice with a flair for computation, you will need to look elsewhere, as that book has not yet been written. But this isn’t the point of this book. Let me quote the introduction: “This book aims to provide an authoritative overview of the field of computational social choice.” To that I say, mission accomplished.

For those who have some knowledge of (or interest in) voting theory and social choice, I will indulge in some more detailed comments about the content momentarily. For everyone else, I recommend you to be aware of this rapidly expanding field and stay tuned for coming attractions. For instance, one of the editors has already begun a startup based on providing easy use of many fair division algorithms to groups of roommates or Uber customers sharing a cab. Luckily, you’ll be be able to catch up with things easily if you need to, since as of May 2017, the editors announced to their community that, “Now that the Handbook of Computational Social Choice has been out for a full year, Cambridge University Press has just made available a free online version of the book that does not require a password.”

As the reader may have guessed, this book falls squarely in the comprehensive “handbook” tradition. Although “[T]he coverage of this book cannot be exhaustive,” given the limitations of this format it sure comes close. Recall that this subfield is about 20 years old and yet the handbook weighs in at a dense 500+ pages! In addition, the references give a who’s who of the field, and the individual chapters (on topics from the axiomatics of PageRank to complexity analysis of classical voting rules) are written by highly regarded (and, relatively speaking, young) experts from the computer science community. As one would expect in such a book, there is quite a bit of overlap at times; in this case it also assists in viewing the various voting concepts and examples from many vantage points — mathematical, algorithmic, and applied.

From a mathematician’s point of view, this does give the book a very interesting feel. Social choice has always had at least one foot squarely within economics, and computer science similarly has a tradition of putting proofs in appendices. But this also leads to new perspectives. For instance, I like how Chapter 8 makes one think of the Condorcet Jury Theorem as a version of May’s Theorem, but for maximum likelihood estimation. I also appreciate some refocusing — for instance, Fishburn’s C1, C2, and C3 classification (of how much pairwise majority information is necessary for a given voting rule) gains more prominence in a computational setting. There are many proofs, or proof outlines, though the level varies very widely from showing that a given procedure is \(\Theta_2^P\)-hard to fairly straightforward examples.

A strength is giving full weight to more unusual (but fertile) topics beyond “voting”, such as judgment aggregation or selecting committees. Also, the editors and authors constantly look to coming attractions, to the point that most chapters acknowledge current work that simply can’t be included yet because of its newness. (A casual glance at the editors’ websites shows how much work has been done in the field since editing commenced.) Taking the longer view, in Chapter 11 (on fair allocation) the author suggests “This interest [by computer scientists] has been uneven … other facets of the theory … on which it has not yet brought to bear its own perspective and techniques … we hope that this survey will help further cross-fertilization.”

Despite the fact that the writing is often too terse (most chapters are not for the faint of heart), anyone who knows a fair amount about the field will find much enjoyable reading in any given chapter. Those who wish to know more should first read the compact but well-organized overview of many of the classical questions in Chapter 2, and then skip to a self-contained chapter of one’s choice. Bribery? The internet? Cake cutting? It’s all there, waiting for discovery.

Karl-Dieter Crisman teaches mathematics at Gordon College in Massachusetts, where he also gets to work on open source software, the mathematics of voting, and examining connections between all of these and issues of belief and faith.

Foreword Hervé Moulin
1. Introduction to computational social choice Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang and Ariel D. Procaccia
Part I. Voting:
2. Introduction to the theory of voting William S. Zwicker
3. Tournament solutions Felix Brandt, Markus Brill and Paul Harrenstein
4. Weighted tournament solutions Felix Fischer, Olivier Hudry and Rolf Niedermeier
5. Dodgson's rule and Young's rule Ioannis Caragiannis, Edith Hemaspaandra and Lane A. Hemaspaandra
6. Barriers to manipulation in voting Vincent Conitzer and Toby Walsh
7. Control and bribery in voting Piotr Faliszewski and Jörg Rothe
8. Rationalizations of voting rules Edith Elkind and Arkadii Slinko
9. Voting in combinatorial domains Jérôme Lang and Lirong Xia
10. Incomplete information and communication in voting Craig Boutilier and Jeffrey S. Rosenschein
Part II. Fair Allocation:
11. Introduction to the theory of fair allocation William Thomson
12. Fair allocation of indivisible goods Sylvain Bouveret, Yann Chevaleyre and Nicolas Maudet
13. Cake cutting algorithms Ariel D. Procaccia
Part III. Coalition Formation:
14. Matching under preferences Bettina Klaus, David F. Manlove and Francesca Rossi
15. Hedonic games Haris Aziz and Rahul Savani
16. Weighted voting games Georgios Chalkiadakis and Michael Wooldridge
Part IV. Additional Topics:
17. Judgment aggregation Ulle Endriss
18. The axiomatic approach and the internet Moshe Tennenholtz and Aviv Zohar
19. Knockout tournaments Virginia Vassilevska-Williams.