1In 2016, on two occasions, humanity witnessed major changes in the organization of the world due to the outcomes of voting. First, on June 23, 2016, the U.K. electorate (in fact 52% of this electorate) voted to leave the E.U. In my view, contrary to a common belief, referenda are a threat against democracy because the statements on which voters must take a decision are often ambiguous (if not totally irrelevant, as in the case of the previous U.K. referendum regarding Alternative Vote on May 5, 2011, where the choice was only between Plurality Rule—a.k.a. “First Past The Post”—and “Alternative Vote” method, leaving aside all other possible voting methods) and, equally often, voters make their decisions on the basis of facts entirely foreign to these statements (for instance, in the so-called Brexit referendum, on the basis of their degree of fear and hatred of immigrants). Second, on November 8, 2016, Donald Trump was elected President of the United States of America. It was a surprise win and Trump was the fifth person in U.S. history to be elected in spite of having less votes than some other candidate. The cause of this paradox is the so-called “Electoral College” system. This system is a two-stage system, the President being in fact elected by members of the Electoral College. In most states, the State Electoral College is not reflecting the results of the “popular vote”: it is uniquely composed of members who are supposed to be in favour of the given State plurality winner. So while Hillary Clinton received 2.9 million more votes than Trump, she was defeated by 304 votes against 227. In these two cases, it is obvious that something is deeply wrong. Trump’s election prompted a number of reactions from social choice specialists. Probably the most discussed of these reactions was the publication of a paper in the January 19, 2017 issue of the New York Review of Books by two Nobel laureates and Harvard professors: Eric Maskin and Amartya Sen. They do not hesitate to suggest the replacement of the current procedure by majority rule à la Condorcet. They appropriately mention that one should take into consideration the preference of voters over the candidates, rather than restrict the ballot to a single name. Of course, they know that majority rule can fail to provide a solution:

Certainly majority rule is not a perfect system, and Condorcet himself showed that there are circumstances—rare in practice—in which no candidate can beat every other candidate in a head-to-head contest... In that case a tie-breaking method would be needed, such as having a runoff between the two top candidates.

2Incidentally, I must admit that I did not understand this tie-breaking thing. In large elections, it would be a miracle if two candidates had exactly the same number of votes. It is even impossible if the number of voters is odd and individual preferences are given by a strict ranking—no ties. The problem with majority rule is that it can generate a strict preference cycle at the social preference level—the Condorcet paradox—and a problem arises in the kind of elections considered by Maskin and Sen if there is a top cycle. A strict preference cycle of two candidates is clearly impossible with majority rule, so the tie-breaking method must apply to at least three candidates. It is, of course, possible to design a tie-breaking rule, such as Dodgson’s rule. But further difficulties arise with Dodgson’s rule, as will be seen shortly.

3There is obviously in the world at this time many discussions about voting methods. In France, during the campaigns of the last two presidential elections, nearly all the candidates proposed modifications of the electoral rules regarding parliamentary elections. Most often, the proposed modifications took the form of the replacement of the current method by proportional representation, or at least a procedure including some proportional representation. But these suggestions ignore that, again, the voters only express in their ballots the choice of a single list (unless mixing candidates of various lists is allowed, which, I suppose, would be rejected by most of our politicians, not to mention the difficulties of calculations).

5All these voting procedures (and others) were generally compared according to their properties and computations of frequencies of violation of these properties were provided. However, one aspect was neglected: the difficulty to compute solutions. The emergence of computational social choice should be appreciated in the light of these efforts to explore alternative voting procedures.

[u]nder either a Dodgson election or a Kemeny election, it is NP hard (that is, at least as hard as an NP complete problem) to determine whether any particular candidate has won! Thus these schemes are capable of taking an impractically long time to determine a winner.

7Dodgson’s method requires that, given voters’ preference orders, if there is no Condorcet winner, the winner is a candidate “who requires the fewest [pairwise] interchanges to become a Condorcet winner”. As a kind of joke, the authors remark: “We think Lewis Carroll [Dodgson’s pen name] would have appreciated the idea that a candidate’s mandate might have expired before it was even recognized.” It seems that Dodgson’s rule could be the voting method which Maskin and Sen could prefer. But computer scientists demonstrate that there is a difficulty with this rule. One way to avoid this difficulty would be to use another procedure to deal with top cycles.

8As is often the case with path-breaking research, it took nearly twenty years before computational social choice emerged as a branch of social choice, branch focusing on the actual computation of social-choice-theoretic solutions when these solutions exist, or the design of approximation algorithms when clear-cut solutions fail to exist or are hard to compute: computational problems are among the most important questions that must be resolved and that is why the Handbook of Computational Social Choice seems to be a highly timely publication.

9At the outset, let me say that this is a very impressive text. Although the editors are (well-known) computer scientists, they all made contributions not only to computational social choice, but also to what I can call “general” social choice. The book is divided into four parts: voting (I), fair allocation (II), coalition formation (III), and additional topics (IV), the first part on voting approximately representing half of the book. Parts I and II have introductory chapters written by two pre-eminent scholars in “general” social choice, respectively William Zwicker and William Thomson. Zwicker is a mathematician and Thomson a mathematical economist. Otherwise, the contributors are all, like the editors, computer scientists, with the possible exception (this is my personal perception!) of Olivier Hudry (mathematician), Bettina Klaus (mathematical economist), and Arkadii Slinko (mathematician).

10A major challenge that the editors had to face is the possible diversity of the Handbook readership. It is aimed at “general” social choice theorists and computer scientists interested in social choice: it is, from the perspective of a “general” social choice theorist, a complete success. Of course, it is necessary to have some knowledge of mathematics, but not more than one can expect from someone working in the most basic part of social choice. Furthermore, in a very useful preliminary chapter, one can find a brief section on computational complexity.

11The chapter on the theory of voting by Zwicker is an authentic gem. It is quite useful for the chapters of the first part (as it should be), but can even be recommended to all mathematically-inclined social scientists to have a brief but deep survey of the subject with notions such as anonymity, neutrality, Pareto conditions, Condorcet winner, various voting rules—scoring rules such as Borda’s rule or Condorcet extensions based on majority relations such as Kemeny’s rule and Dodgson’s rule, approval voting—, strategy-proofness… clearly defined and presented with several interesting results in passing.

12Two chapters are devoted to tournaments. Voters have preferences over options (alternatives/candidates), that are generally given by linear orders (no indifference). A majority relation is defined by considering, for each two-alternative subset {x, y}, the number of voters who prefer x to y and the number of voters who prefer y to x. Clearly, the majority relation is complete and not necessarily asymmetric. Taking into account only the asymmetric part of the majority relation, that is to say excluding ties, one gets a tournament (given the set of alternatives). Many solution concepts have been devised for tournaments, one of which is the Copeland set: Copeland's rule selects the alternatives which defeat the most alternatives. Felix Brandt, Markus Brill, and Paul Herrenstein provide in Chapter 3 an excellent survey of solution concepts and for each solution give results regarding the computation of the solution.

13Chapter 4, by Felix Fischer, Olivier Hudry, and Rolf Niedermeier, deals with weighted tournaments where a majority margin — for alternatives x and y, the difference between the number of voters who prefer x to y and the number of voters who prefer y to x — is taken into account. The considered solutions depend on pairwise majority margins but are not tournament solutions. The authors study Kemeny’s rule (where one must find a linear order which maximizes the number of agreements with the voters’ preferences) and other median orders, mainly regarding computational complexity. They also briefly comment on Borda’s rule and other rules.

14Chapter 5 (authored by Ioannis Caragiannis, Edith Hemaspaandra, and Lane Hemaspaandra) is devoted to Dodgson’s rule and Young’s rule. The difficulty regarding Dodgson’s rule has already been mentioned. However, the authors propose nice ways to escape this apparently fatal flaw. In particular, they introduce parametrized algorithms and approximation algorithms. Young’s rule was suggested by H. Peyton Young in (Young, 1977). It is based on scores attributed to alternatives which, in some sense, are a measure of a kind of distance between the alternatives and their possibility to be a Condorcet winner. If an alternative is a Condorcet winner, its score is 0. Otherwise, the score is defined from the number of removals of individual preferences from the set of individual preferences, which creates a new set of individual preferences for which the alternative is a Condorcet winner. The score of the alternative is then the smallest of these numbers. Computing these numbers, even in simple examples, can be intricate, so that the computational complexity result presented by the authors is hardly unexpected.

15In Chapter 6, Vincent Conitzer and Toby Walsh consider strategic voting. In particular, they tackle the interesting view that computational hardness could be a barrier to manipulation. This question dates back to Bartholdi, Tovey, and Trick (1989a)—one of the papers at the origin of computational social choice. One should note, however, that this computational problem has not been a major obstacle for voters to try to manipulate voting rules. Furthermore, in a large general election, a single voter cannot expect to change the outcome in her favour by misrepresenting her preference.

17The next chapter, by Edith Elkind and Arkadii Slinko, tackles computational problems only in passing. The authors deal with theoretical questions regarding what they call “rationalizations”, a notion which is related to the rationalization of choice functions/correspondences by binary relations in revealed preference analysis. Two approaches are distinguished. A first approach whose origin can be found in Condorcet (Condorcet Jury Theorem) aims at designing “a voting rule which maximizes the probability of identifying the best choice.” This approach is the so-called maximum likelihood estimation in statistics. A second approach, originating in Dodgson’s papers, is called “consensus-based” by the authors. A notion of consensus is considered, and an election outcome is viewed as an approximation of this consensus. It can be seen that there is a double problem to solve: the choice of the notion of consensus on the basis of individual preferences, and the definition of a notion of closeness among lists of individual preferences.

18In Chapter 9, Jerôme Lang and Lirong Xia show that if one imposes some structure on the set of alternatives (for instance a Cartesian product structure), the computational difficulties increase. Then, to obtain reasonable outcomes, one should make restrictions (such as using a separability property). Although the contexts are different, this is, in my view, reminiscent of the assumptions made in microeconomic theory regarding individual preferences or utility functions, such as convexity conditions, and the difficulty of defining Pareto optimal allocations (the preference of an individual over allocations being implicitly given by the preference of this individual over her components in the allocations).

19In French presidential elections, is it possible to use a postulate saying that all voters are able to rank all the candidates? The obvious answer leads to assume that individual preferences are incomplete. In Chapter 10, Craig Boutilier and Jeffrey Rochenschein deal with this difficulty from a more practical point of view than the point of view of several social choice theorists such as Amartya Sen or John Weymark (not to mention the problems generated by the vagueness of preferences). The authors also consider the cases where it is unnecessary to have complete information to reach a decision, and the cases where the set of alternatives itself is uncertain or changing with time.

20Part II is devoted to fair allocations. One can consider that this domain belongs more or less to welfare economics, where qualitative statements matter more than quantitative ones, and, accordingly, that computational problems are not primordial. However, the recent development of so-called “solutions” in this literature naturally leads to the research of precise “fair” allocations, especially in specific cases such as fair division, claims following divorces or bankruptcy, matching in various situations, and so on, so that computational complexity had to be investigated.

21In Chapter 11, William Thomson provides a survey which is, as usual in his case, a masterpiece of exposition. This chapter can be recommended to all social scientists, not only social choice specialists, and to computer scientists interested in social sciences issues.

22The particular case of the fair division of indivisible goods is described in Chapter 12 (by Sylvain Bouveret, Yann Chevaleyre, and Nicolas Maudet), culminating in a section on the computation of fair allocations and a section on the analysis of procedures permitting to reach allocations satisfying “good” properties.

23In Chapter 13, Ariel Procaccia tackles the famous cake cutting problem and discusses a number of algorithms, some of which were introduced rather long ago (for instance, a famous algorithm due to Lester Dubins and Edwin Spanier, which was exposed in (Dubins and Spanier, 1961)—Spanier was a very well-known mathematician, author of a major textbook on algebraic topology.)

24Part III is entitled “Coalition Formation”. I am not sure that this title is appropriate. In particular, one expects that time should play a major role in the formation of coalitions while time plays no role or a very minor role in the issues considered in this part of the Handbook. However, the chapters in this part are as excellent as all the other chapters in the Handbook.

25In Chapter 14, Bettina Klaus, David Manlove, and Francesca Rossi consider matching problems when individuals have preferences over various sets of alternatives. They cover this domain in a very efficient way: two-sided preferences (hospitals/residents, stable marriage, school choice problems) and one-sided preferences (house allocations, housing market).

26In hedonic games, agents have preferences over coalitions, an agent caring only about who is in the coalition in which she is herself. One can see that, in spite of what I previously mentioned, hedonic games can claim to be a description of coalition formation. Chapter 15, by Haris Aziz and Rahul Savani, culminates in their Section 4 on algorithms and computational complexity regarding solution concepts such as core stability or other stability concepts associated to Nash’s name.

27Chapter 16, by Georgios Chalkiadakis and Michael Woodridge, is devoted to weighted voting games. In such games, each player has a weight and a quota is given: if, for the players in a coalition, the sum of the weights of the players is greater than or equal to the quota, then the coalition is said to be winning (said differently, the coalition has full power). Solution concepts such as the core, the Shapley value, the Banzhaf index are presented and the complexity of computing these solutions is considered.

28In Part IV, further topics are presented. The first one (Chapter 17 by Ulle Endriss) is entitled “Judgment Aggregation”. Judgment aggregation can be considered as a sub-domain of social choice theory and, as such, I consider that it was one of the major advances of this theory in the last two decades. This sub-domain is strongly related to formal logic. Since formal logic (not necessarily restricted to what is called mathematical logic) has undergone tremendous developments in the recent years due to some parallel developments in computer science, it could be expected that the interest of computer scientists in social choice would incite some of them to use their expertise in judgment aggregation. Ulle Endriss and his chapter demonstrate that my remark is perfectly right. Of course, the author emphasizes the computational problems. He recalls what the discursive dilemma (based on majority rule) is, and he describes “the computational difficulty of recognizing whether an agenda is sufficiently simple to avoid all occurrences of the discursive dilemma for a given aggregation procedure.”

29The purpose of Chapter 18 (by Moshe Tennenholtz and Haviv Zohar) on the axiomatic approach and the internet is to demonstrate how tools borrowed from the theory of social choice can be used to clarify various systems which are of common usage in the internet environment, for instance, ranking and reputation systems. Famous examples “are Google’s PageRank algorithm which ranks web pages, and eBay’s reputation system in which both buyers and sellers are ranked based on trustworthiness.” This chapter offers a fascinating example of topics where one did not expect that social choice theory could be of any help.

31The last chapter (Chapter 19) by Virginia Vassilevska Williams is about a special type of tournaments, the knock-out tournaments. In such tournaments, no ties are permitted, and a losing alternative is eliminated. The author mainly considers agenda control which is, of course, crucial in such a setting (think of the order of binary contests).

32It seems interesting to compare the contents of this Handbook with the contents of Arrow, Sen, and Suzumura (2002 and 2011). The most obvious fact is that the intersection is almost empty regarding the topics related to rights, welfare, justice, poverty, capability, opportunity, freedom, responsibility, and so on. A comparison with (Sen, 2017) leads to the same conclusion. On the other hand, a comparison with (Heckelman and Miller, 2015), which is more focused on political science, shows a strong convergence of topics. Of course, this is not surprising, since computations are not necessary in many theoretical developments. However, I wish to emphasize that, because some computer scientists are also well versed in logic, beautiful theoretical papers were authored by computer scientists (some of whom contribute to this Handbook)—see, for instance, Grandi and Endriss (2013).

33As a final comment, let me say that this Handbook is a most remarkable volume. I was unable to detect defects or weaknesses. All chapters are well written, with an obvious objective regarding readership. Introduction sections are clear. The authors are capable of transmitting their knowledge, whatever the difficulty. I can only repeat myself by saying that it is highly recommended to all social scientists and all computer scientists interested in voting and in social choice in general.