Chance, Strategy, and Choice Gamesandelectionsofferfamiliar,current,andlivelysubjectsforacourseinmathematics. Withapplicationsinarangeofareassuchaseconomics,politicalscience,andsociology, these topics are of broad interest. This undergraduate textbook, primarily intended for a general-educationcourseingametheoryatthefreshmanorsophomorelevel,providesan elementarytreatmentofgamesandelections.Startingwithbasicssuchasgamblinggames, Nash equilibria, zero-sum games, social dilemmas, combinatorial games, and fairness and impossibility theorems for elections, the text then goes further into the theory with accessible proofs of advanced topics such as the Sprague–Grundy Theorem and Arrow’s ImpossibilityTheorem.Thebook • usesanintegrativeapproachtoprobabilitytheory,gametheory,andsocialchoicetheory by highlighting the mix of ideas occurring in seminal results on games and elections suchastheMinimaxTheorem,allowingstudentstodevelopintuitioninallareaswhile delvingdeeperintothetheory; • providesagentleintroductiontothelogicofmathematicalproof,thusequippingreaders withthenecessarytoolsforfurthermathematicalstudies, afeaturenotsharedbymost gametheorytexts; • containsnumerousexercisesandexamplesofvaryinglevelsofdifficultytohelpstudents learnandretainthematerial; • requiresonlyahighschoolmathematicalbackground,thusmakingthetextaccessibleto alargerangeofstudents. SamuelBruceSmithisProfessorandChairofMathematicsatSaintJoseph’sUniversity and a past director of the University Honors Program. In 2012, he won the Tengelmann AwardforDistinguishedTeachingandResearch. CAMBRIDGEMATHEMATICALTEXTBOOKS Cambridge Mathematical Textbooks is a program of undergraduate and beginning graduate level textbooks for core courses, new courses, and interdisciplinary courses in pureandappliedmathematics.Thesetextsprovidemotivationwithplentyofexercisesof varying difficulty, interesting examples, modern applications, and unique approaches to thematerial. AdvisoryBoard JohnB.Conway,GeorgeWashingtonUniversity LawrenceCraigEvans,UniversityofCalifornia,Berkeley JohnM.Lee,UniversityofWashington JohnMeier,LafayetteCollege LawrenceC.Washington,UniversityofMaryland,CollegePark Chance, Strategy, and Choice An Introduction to the Mathematics of Games and Elections Samuel Bruce Smith SaintJoseph’sUniversity,Philadelphia,PA,USA 32AvenueoftheAmericas,NewYork,NY10013-2473,USA CambridgeUniversityPressispartoftheUniversityofCambridge. ItfurtherstheUniversity’smissionbydisseminatingknowledgeinthepursuitof education,learning,andresearchatthehighestinternationallevelsofexcellence. www.cambridge.org Informationonthistitle:www.cambridge.org/9781107084520 (cid:13)c SamuelBruceSmith2015 Thispublicationisincopyright.Subjecttostatutoryexception andtotheprovisionsofrelevantcollectivelicensingagreements, noreproductionofanypartmaytakeplacewithoutthewritten permissionofCambridgeUniversityPress. Firstpublished2015 PrintedintheUnitedStatesofAmerica AcatalogrecordforthispublicationisavailablefromtheBritishLibrary. LibraryofCongressCataloginginPublicationData Smith,SamuelB.,1966– Chance,strategy,andchoice:anintroductiontothemathematicsofgamesand elections/SamuelBruceSmith,SaintJoseph’sUniversity,Philadelphia,PA,USA. pages cm Includesbibliographicalreferencesandindex. ISBN978-1-107-08452-0(hardback) 1. Gametheory–Textbooks. 2. Gamesofchance(Mathematics)–Textbooks. I. Title. QA269.S587 2015 519.3–dc23 2015003107 ISBN978-1-107-08452-0Hardback CambridgeUniversityPresshasnoresponsibilityforthepersistenceoraccuracyof URLsforexternalorthird-partyInternetwebsitesreferredtointhispublication anddoesnotguaranteethatanycontentonsuchwebsitesis,orwillremain, accurateorappropriate. ToPatty,David,andNed Contents Preface pageix Part I First Notions 1 Introduction 3 2 GamesandElections 11 3 Chance 23 4 Strategy 37 5 Choice 57 6 StrategyandChoice 77 7 ChoiceandChance 89 8 ChanceandStrategy 105 9 NashEquilibria 119 WebResources 135 Part II Basic Theory 10 ProofsandCounterexamples 139 11 LawsofProbability 157 12 FairnessinElections 175 13 WeightedVoting 187 14 GamblingGames 203 15 Zero-SumGames 217 16 Partial-ConflictGames 233 17 TakeawayGames 251 18 FairnessandImpossibility 263 SuggestionsforFurtherReading 277 viii Contents Part III Special Topics 19 ParadoxesandPuzzlesinProbability 281 20 CombinatorialGames 299 21 BordaversusCondorcet 315 22 TheSprague–GrundyTheorem 335 23 Arrow’sImpossibilityTheorem 349 SuggestionsforFurtherReading 371 Bibliography 373 Index 377 Preface This book was written to teach an accessible and authentic mathematics course to a general audience. Games and elections are ideal topics for such a course. The motivating examples are familiar and engaging: from the 2000 U.S. presidential election, to economic pricing wars, to gambling games such as Poker and Blackjack. The elementary theory of these topics involves manageable computationsandemphasizesanalyticreasoningskills.Mostimportant,thestudy ofgamesandelectionshasproducedawealthofbeautifultheorems,manywithin the last century. Games and elections offer a wide selection of elegant results that can be approached without extensive technical background. A course on these topics provides a view of mathematics as a powerful and thriving modern discipline. Thereareexcellenttextscoveringaspectsofthetheoryofgamesandelections, such as those of Straffin [48] and Taylor and Pacelli [49]. The topics are also frequentlycoveredaschaptersinliberalartsmathematicstexts.Thistextispitched at a level between these two types of treatments. The book is designed to be more mathematically ambitious than the general textbook but to allow for a less demandingcoursethanoneofferedusingamorespecializedtext. A novelty of this book is the integrative approach taken to the three subjects: probabilitytheory,gametheory,andsocialchoicetheory.Thisapproachhighlights the mix of ideas occurring in seminal results on games and elections such as the JuryTheorem,theMinimaxTheorem,andtheGibbard-SatterthwaiteTheorem.On a practical level, the integrative approach allows for a more gradual development of material. Rather than taking a steep descent in one area, the chapters follow a spiraling path from chance to strategy to social choice and back again, exploring examples and developing techniques and intuitions in all areas while delving deeperintothetheoryofgamesandelections. Structure of the Book .............................................................................. This book is divided into three parts. Part I introduces the main devices used in the text. These are the probability tree, the game tree, the payoff matrix, and the preferencetable. Expectedvalues, dominatedstrategies, backwardinduction, and rationalplayarethendefinedforthevarioustypesofgames.Theideaofpreference