Game theory : an introduction

Game Theory

Wiley Series in

OPERATIONS RESEARCH AND MANAGEMENT SCIENCE

Operations Research and Management Science (ORMS) is a broad, interdisciplinary branch

of applied mathematics concerned with improving the quality of decisions and processes

and is a major component of the global modern movement towards the use of advanced

analytics in industry and scientific research. The Wiley Series in Operations Research and

Management Science features a broad collection of books that meet the varied needs of

researchers, practitioners, policy makers, and students who use or need to improve their use

of analytics. Reflecting the wide range of current research within the ORMS community,

the Series encompasses application, methodology, and theory and provides coverage of both

classical and cutting edge ORMS concepts and developments. Written by recognized

international experts in the field, this collection is appropriate for students as well as

professionals from private and public sectors including industry, government, and nonprofit

organization who are interested in ORMS at a technical level. The Series is comprised of

three sections: Decision and Risk Analysis; Optimization Models; and Stochastic Models.

Advisory Editors Decision and Risk Analysis

Gilberto Montibeller, London School of Economics

Gregory S. Parnell, United States Military Academy at West Point

Founding Series Editor

James J. Cochran, Louisiana Tech University

Decision and Risk Analysis

Barron Game Theory: An Introduction, Second Edition

Forthcoming Titles

Nussbaum and Mislick Cost Estimation: Methods and Tools Optimization Models

Optimization Models

Ghiani, Laporte, and Musmanno Introduction to Logistics Systems Management,

Second Edition

Stochastic Models

Game Theory

An Introduction

SECOND EDITION

E.N. Barron

Loyola University Chicago

Chicago, Illinois

Copyright C 2013 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.

Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means,

electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108

of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization

through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive,

Danvers, MA 01923, (978) 750-8400, fax (978) 646-8600, or on the web at www.copyright.com. Requests to the

Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street,

Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this

book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this

book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty

may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein

may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher

nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special,

incidental, consequential, or other damages.

For general information on our other products and services please contact our Customer Care Department within the

U.S. at 877-762-2974, outside the U.S. at 317-572-3993 or fax 317-572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print, however, may not be

available in electronic format.

Library of Congress Cataloging-in-Publication Data:

Barron, E. N. (Emmanual N.), 1949–

Game theory : an introduction / Emmanuel N. Barron. – Second edition.

pages cm

Includes bibliographical references and index.

ISBN 978-1-118-21693-4 (cloth)

1. Game theory. I. Title.

QA269.B27 2013

519.3–dc23

2013008270

Printed in the United States of America.

ISBN: 9781118216934

10 9 8 7 6 5 4 3 2 1

To Christina, Michael, and

Anastasia; and Fotini and

Michael

Contents

Preface for the Second Edition xi

Preface for the First Edition xv

Acknowledgments xvii

Introduction 1

1 Matrix Two-Person Games 5

1.1 The Basics, 5

Problems, 16

1.2 The von Neumann Minimax Theorem, 18

1.2.1 Proof of von Neumann’s Minimax Theorem

(Optional), 21

Problems, 24

1.3 Mixed Strategies, 25

1.3.1 Properties of Optimal Strategies, 35

1.3.2 Dominated Strategies, 38

1.4 Solving 2 × 2 Games Graphically, 41

Problems, 43

1.5 Graphical Solution of 2 × m and n × 2 Games, 44

Problems, 50

1.6 Best Response Strategies, 53

Problems, 57

1.6.1 MapleTM/MathematicaR , 58

Bibliographic Notes, 59

2 Solution Methods for Matrix Games 60

2.1 Solution of Some Special Games, 60

2.1.1 2 × 2 Games Revisited, 60

Problems, 64

2.2 Invertible Matrix Games, 65

2.2.1 Completely Mixed Games, 68

Problems, 74

vii

viii Contents

2.3 Symmetric Games, 76

Problems, 81

2.4 Matrix Games and Linear Programming, 82

2.4.1 Setting Up the Linear Program: Method 1, 83

2.4.2 A Direct Formulation Without Transforming:

Method 2, 89

Problems, 94

2.5 Appendix: Linear Programming and the Simplex Method, 98

2.5.1 The Simplex Method Step by Step, 101

Problems, 108

2.6 Review Problems, 108

2.7 Maple/Mathematica, 109

2.7.1 Invertible Matrices, 109

2.7.2 Linear Programming: Method 1, 110

2.7.3 Linear Programming: Method 2, 111

Bibliographic Notes, 113

3 Two-Person Nonzero Sum Games 115

3.1 The Basics, 115

Problems, 123

3.2 2 × 2 Bimatrix Games, Best Response, Equality

of Payoffs, 125

3.2.1 Calculation of the Rational Reaction Sets for

2 × 2 Games, 125

Problems, 132

3.3 Interior Mixed Nash Points by Calculus, 135

3.3.1 Calculus Method for Interior Nash, 135

Problems, 143

3.3.2 Proof that There is a Nash Equilibrium for Bimatrix Games

(Optional), 146

3.4 Nonlinear Programming Method for Nonzero Sum Two-Person

Games, 148

3.4.1 Summary of Methods for Finding Mixed Nash

Equilibria, 156

Problems, 158

3.5 Correlated Equilibria, 159

3.5.1 LP Problem for a Correlated Equilibrium, 165

Problems, 166

3.6 Choosing Among Several Nash Equilibria (Optional), 167

Problems, 172

3.6.1 Maple/Mathematica, 173

3.6.2 Mathematica for Lemke–Howson Algorithm, 173

Bibliographic Notes, 175

Contents ix

4 Games in Extensive Form: Sequential

Decision Making 176

4.1 Introduction to Game Trees—Gambit, 176

Problems, 189

4.2 Backward Induction and Subgame Perfect Equilibrium, 190

Problems, 193

4.2.1 Subgame Perfect Equilibrium, 194

4.2.2 Examples of Extensive Games Using Gambit, 200

Problems, 209

Bibliographic Notes, 212

5 n-Person Nonzero Sum Games and Games

with a Continuum of Strategies 213

5.1 The Basics, 213

Problems, 235

5.2 Economics Applications of Nash Equilibria, 242

5.2.1 Cournot Duopoly, 243

5.2.2 A Slight Generalization of Cournot, 245

5.2.3 Cournot Model with Uncertain Costs, 247

5.2.4 The Bertrand Model, 250

5.2.5 The Stackelberg Model, 252

5.2.6 Entry Deterrence, 254

Problems, 256

5.3 Duels (Optional), 259

5.3.1 Silent Duel on [0,1] (Optional), 262

Problem, 266

5.4 Auctions (Optional), 266

5.4.1 Complete Information, 271

Problems, 272

5.4.2 Incomplete Information, 272

5.4.3 Symmetric Independent Private Value

Auctions, 275

Problem, 286

Bibliographic Notes, 287

6 Cooperative Games 288

6.1 Coalitions and Characteristic Functions, 288

Problems, 307

6.1.1 More on the Core and Least Core, 310

Problems, 317

6.2 The Nucleolus, 319

6.2.1 An Exact Nucleolus for Three-Player Games, 327

Problems, 333

x Contents

6.3 The Shapley Value, 335

Problems, 347

6.4 Bargaining, 352

6.4.1 The Nash Model with Security Point, 358

6.4.2 Threats, 365

6.4.3 The Kalai–Smorodinsky Bargaining Solution, 377

6.4.4 Sequential Bargaining, 379

Problems, 384

Review Problems, 386

6.5 Maple/Mathematica, 386

6.5.1 Finding the Nucleolus One Step at a Time, 386

6.5.2 Mathematica Code for Three-Person Nucleolus, 391

6.5.3 The Shapley Value with Maple, 393

6.5.4 Maple and Bargaining, 393

Bibliographic Notes, 394

7 Evolutionary Stable Strategies and

Population Games 395

7.1 Evolution, 395

7.1.1 Properties of an ESS, 402

Problems, 408

7.2 Population Games, 409

Problems, 428

Bibliographic Notes, 430

Appendix A: The Essentials of Matrix Analysis 432

Appendix B: The Essentials of Probability 436

Appendix C: The Essentials of Maple 442

Appendix D: The Mathematica Commands 448

Appendix E: Biographies 463

Problem Solutions 465

References 549

Index 551

Preface for the Second Edition

This second edition expands the book in several ways. There is a new chapter on extensive

games that takes advantage of the open-source software package GAMBIT1 to both draw the

trees and solve the games. Even simple examples will show that doing this by hand is not

really feasible and that’s why it was skipped in the first edition. These games are now included

in this edition because it provides a significant expansion of the number of game models that

the student can think about and implement. It is an important modeling experience and one

cannot avoid thinking about the game and the details to get it right.

Many more exercises have been added to the end of most sections. Some material has

been expanded upon and some new results have been discussed. For instance, the book now

has a section on correlated equilibria and a new section on explicit solutions of three player

cooperative games due to recent results of Leng and Parlar (2010). The use of software makes

these topics tractable. Finding a correlated equilibrium depends on solving a linear pro￾gramming problem that becomes a trivial task with MapleTM/MathematicaR or any linear

programming package.

Once again there is more material in the book than can be covered in one semester,

especially if one now wants to include extensive games. Nevertheless, all of the important

topics can be covered in one semester if one does not get sidetracked into linear programming

or economics. The major topics forming the core of the course are zero sum games, nonzero

sum games, and cooperative games. A course covering these topics could be completed in

one quarter.

The foundation of this class is examples. Every concept is either introduced by or

expanded upon and then illustrated with examples. Even though proofs of the main theorems

are included, in my own course I skip virtually all of them and focus on their use. In a

more advanced course, one might include proofs and more advanced material. For example,

I have included a brief discussion of mixed strategies for continuous games but this is a topic

that actually requires knowledge of measure theory to present properly. Even knowing about

Stieltjes integrals is beyond the prerequisites of the class. Incidentally, the prerequisites for

the book are very elementary probability, calculus, and a basic knowledge of matrices (like

multiplying and inverses).

Another new feature of the second edition is the availability of a solution manual that

includes solutions to all of the problems in the book. The new edition of the book contains

answers to odd-numbered problems. Some instructors have indicated that they would prefer

to not have all the solutions in the book so that they could assign homework for grades

1McKelvey RD, McLennan AM, Turocy TL. Gambit: software tools for game theory, Version 0.2010.09.01;

2010. Available at: http://www.gambit-project.org (accessed on 2012 Nov 15), and which can also be

obtained from website www.math.luc.edu/∼enb.

xi

xii Preface for the Second Edition

without making up all new problems. I am persuaded by this argument after teaching this

course many times.

All the software in the book in both Maple and Mathematica is available for download

from my website:

www.math.luc.edu/∼enb

My classes in game theory have had a mix of students with majors in mathematics,

economics, biology, chemistry, but even French, theology, philosophy, and English. Most

of the students had college mathematics prerequisites, but some had only taken calculus

and probability/statistics in high school. The prerequisites are not a strong impediment for

this course.

I have recently begun my course with introducing extensive games almost from the first

lecture. In fact, when I introduce the Russian Roulette and 2 × 2 Nim examples in Chapter 1,

I take that opportunity to present them in Gambit in a classroom demonstration. From that

point on extensive games are just part of the course and they are intermingled with matrix the￾ory as a way to model a game and come up with the game matrix. In fact, demonstrating the

construction using Gambit of a few examples in class is enough for students to be able to con￾struct their own models. Exercises on extensive games can be assigned from the first week. In

fact, the chapter on extensive games does not have to be covered as a separate chapter but used

as a source of problems and homework. The only concepts I discuss in that chapter are back￾ward induction and subgame perfect equilibrium that can easily be covered through examples.

A suggested syllabus for this course may be useful:

1. Chapters 1, 2 (3 weeks)

(a) Upper and lower values, mixed strategies, introduction to game trees and Gambit

(b) Expected payoffs, minimax theorem, graphical method

(c) Invertible matrix games, symmetric games, linear programming method

2. Chapter 3 (2 weeks)

(a) Nonzero sum two-person games, pure and mixed Nash equilibrium

(b) Best responses, equality of payoffs

(c) Calculus method, Lemke-Howson, correlated equilibrium

3. Chapter 4 (1 week)

(a) Extensive form games

(i) Trees in Gambit, information sets, examples

(ii) Subgame perfect equilibrium, backward induction, examples

(b) Exam 1

4. Chapter 5 (2 weeks)

(a) Pure Nash equilibrium for games with a continuum of strategies

(b) Selected examples: Cournot, Stackelberg, Traveler’s paradox, Braess’ paradox, War of

Attrition

5. Chapter 6 (3 weeks)

(a) Cooperative games

(i) Characteristic functions, imputations, core, least core

(ii) Nucleolus, Shapley value.

Preface for the Second Edition xiii

(b) Bargaining, Nash solution, threats

(c) Exam 2

6. Chapter 7 (1 week)

(a) Evolutionary stable strategies

(b) Population games and stability

(c) Review

Naturally, instructors may choose from the many peripheral topics available in the book

if they have time, or for assignment as extra credit or projects. I have made no attempt to make

the book exhaustive of topics that should be covered, and I think that would be impossible

in any case. The topics I have chosen I consider to be foundational for all of game theory

and within the constraints of the prerequisites of an undergraduate course. For further topics,

there are many excellent books on the subject, some of which are listed in the references.

As a final note on software, this class does not require the writing of any programs. All

one needs is a basic facility with using software packages. In all cases, solving any of the games

in Maple or Mathematica involves looking at the examples and modifying the matrices as

warranted. The use of software has not been a deterrent to any student I have had in any

game theory class, and in fact, the class can be designed without the use of any software.

In the first edition I listed some of the game theorists who have been awarded the Nobel

Prize in Economics. In 2012, Lloyd Shapley and Alvin Roth, both pioneers in game theory

and behavioral economics, were awarded the Nobel prize, continuing the recognition of the

contributions of game theory to economics.

Acknowledgment: I am very grateful to everyone who has contacted me with possible errors

in the first edition. I am particularly grateful to Professor Kevin Easley at Truman State, for

his many suggestions, comments, and improvements for the book over the time he has been

teaching game theory. His comments and the comments from his class were invaluable to

me. I am grateful to all of those instructors who have adopted the book for use in their course

and I hope that the second edition removes some of the deficiencies in the first and makes

the course better for everyone.

As part of an independent project, I assigned my student Zachary Schaefer the problem

of writing some very useful Mathematica programs to do various tasks. The projects ranged

from setting up the graphs for any appropriate, sized matrix game, solving any game with

linear programming by both methods, automating the search for Nash equilibria in a nonzero

sum game, and finding the nucleolus and Shapley value for any cooperative game (this last

one is a real tour de force). All these projects are available from my website. Zachary did a

great job.

I also thank the National Science Foundation for partial support of this project under

grant 1008602.

I would be grateful for notification of any errors found.

Chicago, Illinois E.N. Barron

ebarron@luc.edu

2012

Preface for the First Edition

Man is a gaming animal. He must always be trying to get the better in something or other.

—Charles Lamb, Essays of Elia, 1823

Why do countries insist on obtaining nuclear weapons? What is a fair allocation of

property taxes in a community? Should armies ever be divided, and in what way in order

to attack more than one target? How should a rat run to avoid capture by a cat? Why do

conspiracies almost always fail? What percentage of offensive plays in football should be passes,

and what percentage of defensive plays should be blitzes? How should the assets of a bankrupt

company be allocated to the debtors? These are the questions that game theory can answer.

Game theory arises in almost every facet of human interaction (and inhuman interaction as

well). Either every interaction involves objectives that are directly opposed, or the possibility of

cooperation presents itself. Modern game theory is a rich area of mathematics for economics,

political science, military science, finance, biological science (because of competing species

and evolution), and so on.1

This book is intended as a mathematical introduction to the basic theory of games,

including noncooperative and cooperative games. The topics build from zero sum matrix

games, to nonzero sum, to cooperative games, to population games. Applications are presented

to the basic models of competition in economics: Cournot, Bertrand, and Stackelberg models.

The theory of auctions is introduced and the theory of duels is a theme example used in

both matrix games, nonzero sum games, and games with continuous strategies. Cooperative

games are concerned with the distribution of payoffs when players cooperate. Applications of

cooperative game theory to scheduling, cost savings, negotiating, bargaining, and so on, are

introduced and covered in detail.

The prerequisites for this course or book include a year of calculus, and very small parts

of linear algebra and probability. For a more mathematical reading of the book, it would

be helpful to have a class in advanced calculus, or real analysis. Chapter 7 uses ordinary

differential equations. All of these courses are usually completed by the end of the sophomore

year, and many can be taken concurrently with this course. Exercises are included at the

end of almost every section, and odd-numbered problems have solutions at the end of the

book. I have also included appendixes on the basics of linear algebra, probability, Maple,2

and Mathematica,3 commands for the code discussed in the book using Maple.

1In an ironic twist, game theory cannot help with most common games, like chess, because of the large

number of strategies involved.

2Trademark of Maplesoft Corporation.

3Trademark of Wolfram Research Corp.

xv

xvi Preface for the First Edition

One of the unique features of this book is the use of Maple1 or Mathematica2 to find

the values and strategies of games, both zero and nonzero sum, and noncooperative and

cooperative. The major computational impediment to solving a game is the roadblock of

solving a linear or nonlinear program. Maple/Mathematica gets rid of those problems and

the theories of linear and nonlinear programming do not need to be presented to do the

computations. To help present some insight into the basic simplex method, which is used

in solving matrix games and in finding the nucleolus, a section on the simplex method

specialized to solving matrix games is included. If a reader does not have access to Maple or

Mathematica, it is still possible to do most of the problems by hand, or using the free software

Gambit,3 or Gams.4

The approach I took in the software in this book is to not reduce the procedure to a

canned program in which the student simply enters the matrix and the software does the rest

(Gambit does that). To use Maple/Mathematica and the commands to solve any of the games

in this book, the student has to know the procedure, that is, what is going on with the game

theory part of it, and then invoke the software to do the computations.

My experience with game theory for undergraduates is that students greatly enjoy both

the theory and applications, which are so obviously relevant and fun. I hope that instructors

who offer this course as either a regular part of the curriculum, or as a topics course, will find

that this is a very fun class to teach, and maybe to turn students on to a subject developed

mostly in this century and still under hot pursuit. I also like to point out to students that

they are studying the work of Nobel Prize winners: Herbert Simon5 in 1979, John Nash,6

J.C. Harsanyi7 and R. Selten8 in 1994, William Vickrey9 and James Mirrlees10 in 1996, and

Robert Aumann11 and Thomas Schelling12 in 2005. In 2007 the Nobel Prize in economics

was awarded to game theorists Roger Myerson,13 Leonid Hurwicz,14 and Erik Maskin.15 In

addition, game theory was pretty much invented by John von Neumann,16 one of the true

geniuses of the twentieth century.

Chicago, Illinois E.N. Barron

2007

1Version 10.0 or later.

2Version 8.0.

3Available from www.gambit.sourceforge.net/.

4Available from www.gams.com.

5June 15, 1916−February 9, 2001, a political scientist who founded organizational decision making. 6See the short biography in the Appendix E.

7May 29, 1920−August 9, 2000, Professor of Economics at University of California, Berkeley, instrumental

in equilibrium selection.

8Born October 5, 1930, Professor Emeritus, University of Bonn, known for his work on bounded rationality.

9June 21, 1914−October 11, 1996, Professor of Economics at Columbia University, known for his work

on auction theory.

10Born July 5, 1936, Professor Emeritus at University of Cambridge.

11Born June 8, 1930, Professor at Hebrew University.

12Born April 14, 1921, Professor in School of Public Policy, University of Maryland.

13Born March 29, 1951, Professor at University of Chicago.

14Born August 21, 1917, Regents Professor of Economics Emeritus at the University of Minnesota.

15Born December 12, 1950, Professor of Social Science at Institute for Advanced Study, Princeton.

16See a short biography in the Appendix E and MacRae (1999) for a full biography.