Smith - Chance, Strategy, and Choice: An Introduction to the Mathematics of Games and Elections

Chance, Strategy, and Choice

Games and elections offer familiar, current, and lively subjects for a course in mathematics. With applications in a range of areas such as economics, political science, and sociology, these topics are of broad interest. This undergraduate textbook, primarily intended for a general-education course in game theory at the freshman or sophomore level, provides an elementary treatment of games and elections. Starting with basics such as gambling games, 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 SpragueGrundy Theorem and Arrows Impossibility Theorem. The book

uses an integrative approach to probability theory, game theory, and social choice theory by highlighting the mix of ideas occurring in seminal results on games and elections such as the Minimax Theorem, allowing students to develop intuition in all areas while delving deeper into the theory;

provides a gentle introduction to the logic of mathematical proof, thus equipping readers with the necessary tools for further mathematical studies, a feature not shared by most game theory texts;

contains numerous exercises and examples of varying levels of difficulty to help students learn and retain the material;

requires only a high school mathematical background, thus making the text accessible to a large range of students.

Samuel Bruce Smith is Professor and Chair of Mathematics at Saint Josephs University and a past director of the University Honors Program. In 2012, he won the Tengelmann Award for Distinguished Teaching and Research.

CAMBRIDGE MATHEMATICAL TEXTBOOKS

Cambridge Mathematical Textbooks is a program of undergraduate and beginning graduate level textbooks for core courses, new courses, and interdisciplinary courses in pure and applied mathematics. These texts provide motivation with plenty of exercises of varying difficulty, interesting examples, modern applications, and unique approaches to the material.

Advisory Board

John B. Conway, George Washington University

Lawrence Craig Evans, University of California, Berkeley

John M. Lee, University of Washington

John Meier, Lafayette College

Lawrence C. Washington, University of Maryland, College Park

Chance, Strategy, and Choice

An Introduction to the Mathematics of Games and Elections

Samuel Bruce Smith

Saint Josephs University, Philadelphia, PA, USA

32 Avenue of the Americas, New York, NY 10013-2473, USA

Cambridge University Press is part of the University of Cambridge.

It furthers the Universitys mission by disseminating knowledge in the pursuit of education, learning, and research at the highest international levels of excellence.

www.cambridge.org

Information on this title: www.cambridge.org/9781107084520

Samuel Bruce Smith 2015

This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press.

First published 2015

Printed in the United States of America

A catalog record for this publication is available from the British Library.

Library of Congress Cataloging in Publication Data

Smith, Samuel B., 1966

Chance, strategy, and choice : an introduction to the mathematics of games and elections / Samuel Bruce Smith, Saint Josephs University, Philadelphia, PA, USA.

pages cm

Includes bibliographical references and index.

ISBN 978-1-107-08452-0 (hardback)

1. Game theoryTextbooks. 2. Games of chance (Mathematics)Textbooks. I. Title.

QA269.S587 2015

519.3dc23 2015003107

ISBN 978-1-107-08452-0 Hardback

Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party Internet websites referred to in this publication and does not guarantee that any content on such websites is, or will remain, accurate or appropriate.

To Patty, David, and Ned

Contents

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 computations and emphasizes analytic reasoning skills. Most important, the study of games and elections has produced a wealth of beautiful theorems, many within 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.

There are excellent texts covering aspects of the theory of games and elections, such as those of Straffin [] . The topics are also frequently covered as chapters in liberal arts mathematics texts. This text is pitched 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 demanding course than one offered using a more specialized text.

A novelty of this book is the integrative approach taken to the three subjects: probability theory, game theory, and social choice theory. This approach highlights the mix of ideas occurring in seminal results on games and elections such as the Jury Theorem, the Minimax Theorem, and the Gibbard-Satterthwaite Theorem. 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 deeper into the theory of games and elections.

Structure of the Book

This book is divided into three parts. ballots is motivated with examples from sports and politics, and the basic voting methods are introduced.

presents Nash equilibria as a unifying concept, tying together several examples in the categories of zero-sum, partial-conflict, mixed-strategy, and electoral games.

focuses more directly on the development of mathematical theory. A chapter on logic prepares the way, with topics from the first part of the book serving as representative examples of conditional and universal statements. The method of proof by induction for game trees is illustrated with a version of Zermelos Theorem. Conditionals are explored further in the probability setting, while fairness criteria for voting methods provide exercises with universal statements and an exposure to the dichotomy between proofs and counterexamples in mathematics. Counting techniques are developed for computing the power index of a weighted voting system. The problem of determining weights for a yes-no system and the notion of a mathematical invariant are introduced, leading up to a statement of the Taylor-Zwicker Theorem.

is a return to the question of fairness for voting methods. Fairness criteria for social welfare methods including Arrows famous Independence criteria are introduced. Mays Theorem, a simplified version of Arrows Theorem, and Sens Impossibility Theorem are proved in this chapter.