Alan D. Taylor

Cutting a cake, dividing up the property in an estate, determining the borders in an international dispute - such problems of fair division are ubiquitous. Fair Division treats all these problems and many more through a rigorous analysis of a variety of procedures for allocating goods (or ‘bads’ like chores), or deciding who wins on what issues, when there are disputes. Starting with an analysis of the well-known cake-cutting procedure, ‘I cut, you choose’, the authors show how it has been adapted in a number of fields and then analyze fair-division procedures applicable to situations in which there are more than two parties, or there is more than one good to be divided. In particular they focus on procedures which provide ‘envy-free’ allocations, in which everybody thinks he or she has received the largest portion and hence does not envy anybody else. They also discuss the fairness of different auction and election procedures.

Two prisoners are told that they will be brought to a room and seated so that each can see the other. Hats will be placed on their heads; each hat is either red or green. The two prisoners must simultaneously submit a guess of their own hat color, and they both go free if at least one of them guesses correctly. While no communication is allowed once the hats have been placed, they will, however, be allowed to have a strategy session before being brought to the room. Is there a strategy ensuring their release? The answer turns out to be yes, and this is the simplest non-trivial example of a “hat problem.” This book deals with the question of how successfully one can predict the value of an arbitrary function at one or more points of its domain based on some knowledge of its values at other points. Topics range from hat problems that are accessible to everyone willing to think hard, to some advanced topics in set theory and infinitary combinatorics. For example, there is a method of predicting the value f(a) of a function f mapping the reals to the reals, based only on knowledge of f's values on the open interval (a – 1, a), and for every such function the prediction is incorrect only on a countable set that is nowhere dense. The monograph progresses from topics requiring fewer prerequisites to those requiring more, with most of the text being accessible to any graduate student in mathematics. The broad range of readership includes researchers, postdocs, and graduate students in the fields of set theory, mathematical logic, and combinatorics. The hope is that this book will bring together mathematicians from different areas to think about set theory via a very broad array of coordinated inference problems.

Two prisoners are told that they will be brought to a room and seated so that each can see the other. Hats will be placed on their heads; each hat is either red or green. The two prisoners must simultaneously submit a guess of their own hat color, and they both go free if at least one of them guesses correctly. While no communication is allowed once the hats have been placed, they will, however, be allowed to have a strategy session before being brought to the room. Is there a strategy ensuring their release? The answer turns out to be yes, and this is the simplest non-trivial example of a “hat problem.” This book deals with the question of how successfully one can predict the value of an arbitrary function at one or more points of its domain based on some knowledge of its values at other points. Topics range from hat problems that are accessible to everyone willing to think hard, to some advanced topics in set theory and infinitary combinatorics. For example, there is a method of predicting the value f(a) of a function f mapping the reals to the reals, based only on knowledge of f's values on the open interval (a – 1, a), and for every such function the prediction is incorrect only on a countable set that is nowhere dense. The monograph progresses from topics requiring fewer prerequisites to those requiring more, with most of the text being accessible to any graduate student in mathematics. The broad range of readership includes researchers, postdocs, and graduate students in the fields of set theory, mathematical logic, and combinatorics. The hope is that this book will bring together mathematicians from different areas to think about set theory via a very broad array of coordinated inference problems.

Why would anyone bid $3. 25 in an auction where the prize is a single dollar bill? Can one “game” explain the apparent irrationality behind both the arms race of the 1980s and the libretto of Puccini’s opera Tosca? How can one calculation suggest the president has 4 percent of the power in the United States federal system while another s- gests that he or she controls 77 percent? Is democracy (in the sense of re?ecting the will of the people) impossible? Questionslikethesequitesurprisinglyprovideaveryniceforumfor some fundamental mathematical activities: symbolic representation and manipulation, model–theoretic analysis, quantitative represen- tionandcalculation,anddeductionasembodiedinthepresentationof mathematical proof as convincing argument. We believe that an ex- sure to aspects of mathematics such as these should be an integral part of a liberal arts education. Our hope is that this book will serve as a text for freshman-sophomore level courses, aimed primarily at students in the humanities and social sciences, that will provide this sort of exposure. A number of colleges and universities already have interdisciplinary freshman seminars where this could take place. Most mathematics texts for nonscience majors try to show that mathematics can be applied to many different disciplines. A student’s viii PREFACE interest in a particular application, however, often depends on his or hergeneralinterestintheareainwhichtheapplicationistakingplace. Our experience at Union College and Williams College has been that there is a real advantage in having students enter the course knowing that virtually all the applications will focus on a single discipline—in this case, political science.

Why would anyone bid $3. 25 in an auction where the prize is a single dollar bill? Can one “game” explain the apparent irrationality behind both the arms race of the 1980s and the libretto of Puccini’s opera Tosca? How can one calculation suggest the president has 4 percent of the power in the United States federal system while another s- gests that he or she controls 77 percent? Is democracy (in the sense of re?ecting the will of the people) impossible? Questionslikethesequitesurprisinglyprovideaveryniceforumfor some fundamental mathematical activities: symbolic representation and manipulation, model–theoretic analysis, quantitative represen- tionandcalculation,anddeductionasembodiedinthepresentationof mathematical proof as convincing argument. We believe that an ex- sure to aspects of mathematics such as these should be an integral part of a liberal arts education. Our hope is that this book will serve as a text for freshman-sophomore level courses, aimed primarily at students in the humanities and social sciences, that will provide this sort of exposure. A number of colleges and universities already have interdisciplinary freshman seminars where this could take place. Most mathematics texts for nonscience majors try to show that mathematics can be applied to many different disciplines. A student’s viii PREFACE interest in a particular application, however, often depends on his or hergeneralinterestintheareainwhichtheapplicationistakingplace. Our experience at Union College and Williams College has been that there is a real advantage in having students enter the course knowing that virtually all the applications will focus on a single discipline—in this case, political science.

Honesty in voting, it turns out, is not always the best policy. Indeed, in the early 1970s, Allan Gibbard and Mark Satterthwaite, building on the seminal work of Nobel laureate Kenneth Arrow, proved that with three or more alternatives there is no reasonable voting system that is non-manipulable; voters will always have an opportunity to benefit by submitting a disingenuous ballot. The ensuing decades produced a number of theorems of striking mathematical naturality that dealt with the manipulability of voting systems. This 2005 book presents many of these results from the last quarter of the twentieth century, especially the contributions of economists and philosophers, from a mathematical point of view, with many new proofs. The presentation is almost completely self-contained, and requires no prerequisites except a willingness to follow rigorous mathematical arguments. Mathematics students, as well as mathematicians, political scientists, economists and philosophers will learn why it is impossible to devise a completely unmanipulable voting system.

Honesty in voting, it turns out, is not always the best policy. Indeed, in the early 1970s, Allan Gibbard and Mark Satterthwaite, building on the seminal work of Nobel laureate Kenneth Arrow, proved that with three or more alternatives there is no reasonable voting system that is non-manipulable; voters will always have an opportunity to benefit by submitting a disingenuous ballot. The ensuing decades produced a number of theorems of striking mathematical naturality that dealt with the manipulability of voting systems. This 2005 book presents many of these results from the last quarter of the twentieth century, especially the contributions of economists and philosophers, from a mathematical point of view, with many new proofs. The presentation is almost completely self-contained, and requires no prerequisites except a willingness to follow rigorous mathematical arguments. Mathematics students, as well as mathematicians, political scientists, economists and philosophers will learn why it is impossible to devise a completely unmanipulable voting system.

Since the publication of Roger Fisher and William Ury's highly influential book, Getting to Yes, it has been widely recognized that there is a middle ground between winning and losing in negotiation. Yet, while Getting to Yes was long on motivation, it was short on technique. What you really want to know is on which issues you will win, on which you will lose, and on which you will have to compromise. To this question, Steven J. Brams and Alan D. Taylor bring a patented procedure that not only is fair but also actually guarantees that both parties walk away with as much of the "win-win" potential as possible. "One can hire a lawyer and spend years and thousands of dollars fighting [in a divorce], or one can make use of a neat new formula devised by Steven Brams and Alan Taylor."—The New Yorker

Simple games are mathematical structures inspired by voting systems in which a single alternative, such as a bill, is pitted against the status quo. The first in-depth mathematical study of the subject as a coherent subfield of finite combinatorics--one with its own organized body of techniques and results--this book blends new theorems with some of the striking results from threshold logic, making all of it accessible to game theorists. Introductory material receives a fresh treatment, with an emphasis on Boolean subgames and the Rudin-Keisler order as unifying concepts. Advanced material focuses on the surprisingly wide variety of properties related to the weightedness of a game. A desirability relation orders the individuals or coalitions of a game according to their influence in the corresponding voting system. As Taylor and Zwicker show, acyclicity of such a relation approximates weightedness--the more sensitive the relation, the closer the approximation. A trade is an exchange of players among coalitions, and robustness under such trades is equivalent to weightedness of the game. Robustness under trades that fit some restrictive exchange pattern typically characterizes a wider class of simple games--for example, games for which some particular desirability order is acyclic. Finally, one can often describe these wider classes of simple games by weakening the total additivity of a weighting to obtain what is called a pseudoweighting. In providing such uniform explanations for many of the structural properties of simple games, this book showcases numerous new techniques and results.

interest in a particular application, however, often depends on his or hergeneralinterestintheareainwhichtheapplicationistakingplace. My experience at Union College has been that there is a real advan­ tage in having students enter the course knowing thatvirtually all the applications will focus on a single discipline-in this case, political science. The level ofpresentation assumes no college-level mathematicalor social science prerequisites. The philosophy underlying the approach we have taken in this book is based on the sense that we (mathemati­ cians)havetendedtomaketwoerrorsinteachingnonsciencestudents: wehaveoverestimatedtheircomfortwithcomputationalmaterial,and we have underestimated their ability to handle conceptual material. Thus, while there is very little algebra (and certainly no calculus) in our presentation, we have included numerous logical arguments that students in the humanitiesand the socialscienceswill find accessible, but not trivial. The book contains five main topics: a m.odel of escalation, game­ theoretic models of international conflict, yes-no voting systems, political power, and social choice. The first partofthe text is made up of a single chapter devoted to each topic. The second part of the text revisits each topic, again with a single chapter devoted to each. The organizationofthe bookisbasedonpedagogicalconsiderations, with the material becoming somewhat more sophisticated as one moves through the ten chapters. On the other hand, within any given chap­ terthere is little reliance on material from earlierchapters, except for those devoted to the same topic.