Christoph Börgers
SIAM 2010, 250 PAGES
PRICE (PAPERBACK) £22.00 ISBN 978-0-89-871695-5
This book is an introduction to, as the title suggests, the mathematics of voting, compensation and division. Each section is self-contained, consisting of short and snappy chapters without being over-concise, and accompanied by mercifully doable exercises which not only tie in well with the text, but are mostly provided with that rare luxury of worked solutions in the back. The text is quite discursive in presentation, with plenty of examples to keep the concepts under discussion firmly grounded in the concrete. Some of the finer details of proof are omitted, but then again, the book does not purport to be a text on analysis. That is not to say that the more technical material is overlooked: for example, a full proof of Hall’s celebrated Marriage Theorem is given in the section on division motivated by, unsurprisingly, trying to pair up a list of girls with suitors matching their tastes.
The first section on voting is, perhaps unavoidably, rather definition- heavy. This does mean when confronted with a ‘Pareto-efficient, monotonic single-winner method satisfying the ICC criterion of dictatorship’, some quick revision of earlier chapters would probably be recommended before embarking on the proof of the Muller-Satterthwaite Theorem. This section of the book highlights some of the difficulties that occur in choosing a winner within any voting system in such a way that is fair. Personally, I found the ‘dictatorship’ method most appealing, certainly from a mathematical point of view anyway. Having said that, I do not think there was any fear of this becoming a contender with the first-past-the-post and alternative vote methods in the recently debated electoral reforms.
A brief second section addresses compensation problems, where an indivisible item is owned by several people equally, but must be assigned to one of them with monetary compensation paid to the others. Of course there is no hard-and-fast mathematical answer as to how this should or can be achieved, but calculations on the basis of envy (which happens to be a non-transitive property – see Chapter 13) and fairness give an algorithm for working out a sensible compensation scheme. It vindicates intuition to discover that an envy-free arrangement is one in which all compensation amounts are equal, albeit after a bit of mathematical legwork. This section continues to discuss more technical notions of equitability and Pareto-Optimality, concluding with Knaster’s Procedure as a compromise between equitability and equality.
The third and final section discusses the problem of sharing a divisible resource among several people. The standard example of sharing a cake is used, but only in a text of this sort would you find the sentence ‘We assume that the cake can be divided into arbitrarily small pieces’. This is compounded by identifying the slices of cake with subsets of R3 and associated probability density integrals, formalising the old adage of ‘I cut, you choose’.
This method can be extended to three people by Steinhaus’s Method of appointing a ‘divider’ randomly, the remaining two being appointed ‘choosers’. The former cuts the cake into three pieces he considers to be of equal size and lets the latter choose a slice each. In the case that two distinct slices are chosen, the choosers keep their selected slices and give the remaining slice to the divider. In the case of both choosers selecting the same slice, the divider selects an unchosen slice for themselves, combines the two remaining slices, and makes the original choosers play ‘I cut, you choose’. It is more complicated to generalise this further, but there is a nice little exercise at the end of the chapter on Hall’s Marriage Theorem to show the theorem in action, fairly assigning pieces of cake. The remainder of this section explores other methods of generalising these ideas.
This book does not need a high level of technical knowledge, and so I would recommend it to anyone who is looking for something a bit fun and different, especially those students who may be so bogged down with abstract concepts that they have lost sight of useful and interesting real world applications of relatively simple concepts.
George Matthews AMIMA
Mathematics Today October 2011
Mathematics of Social Choice: Voting, Compensation, and Division can be purchased at Amazon.co.uk
