Frontmatter and preface of "An introduction to game theory" by Martin J.
Osborne (Oxford
University Press, 2004). Copyright © 2004 Martin J. Osborne.
No part of this Work may be reproduced by any electronic or mechanical means (including
photocopying, recording, or information storage and retrieval) without permission in writing
from the Publisher, except that one copy, of up to six chapters, may be made by any
individual for private study.
AN INTRODUCTION TO
GAME THEORY
M ARTIN J. O SBORNE
University of Toronto
N EW YORK OXFORD
OXFORD UNIVERSITY PRESS
2004
Oxford University Press
Oxford New York
Auckland Bangkok Buenos Aires Cape Town Chennai
Dar es Salaam Delhi Hong Kong Istanbul Karachi Kolkata
Kuala Lumpur Madrid Melbourne Mexico City Mumbai
Nairobi São Paolo Shanghai Taipei Tokyo Toronto
Copyright © 2004 Martin J. Osborne
Published by Oxford University Press, Inc.
198 Madison Avenue, New York, New York, 10016
http://www.oup-usa.org
Oxford is a registered trademark of Oxford University Press
All rights reserved. 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, or otherwise,
without the prior permission of Oxford University Press.
Library of Congress Cataloging-in-Publication Data
Osborne, Martin J.
An introduction to game theory / Martin J. Osborne.
p. cm.
Includes bibliographical references and index.
ISBN 0-19-512895-8 (cloth : acid-free paper)
1. Game Theory. I. Title.
QA269.O78 2004
519.3–dc21 2003042981
Photograph of John von Neumann on page 3 kindly supplied by the
Los Alamos National Laboratory, New Mexico, U.S.A.
Photograph of John Nash on page 23 copyright © The Nobel Foundation.
This book was typeset by the author, who is greatly indebted to
Donald Knuth (TEX), Leslie Lamport (LATEX), Diego Puga (mathpazo),
Christian Schenk (MiKTEX), Ed Sznyter (ppctr), Timothy van Zandt (PSTricks),
Vincent Zoonekynd (boites), and others, for generously making superlative
software freely available. The main font is 10pt Palatino.
Printing number: 20 19 18 17
Printed in the United States of America
on acid-free paper
Contents
Preface xi
1 Introduction 1
1.1 What is game theory? 1
An outline of the history of game theory 2
John von Neumann 3
1.2 The theory of rational choice 4
1.3 Coming attractions: interacting decision-makers 7
Notes 9
I Games with Perfect Information 11
2 Nash Equilibrium: Theory 13
2.1 Strategic games 13
2.2 Example: the Prisoner’s Dilemma 14
2.3 Example: Bach or Stravinsky? 18
2.4 Example: Matching Pennies 19
2.5 Example: the Stag Hunt 20
2.6 Nash equilibrium 21
John F. Nash, Jr. 23
Studying Nash equilibrium experimentally 24
2.7 Examples of Nash equilibrium 26
Experimental evidence on the Prisoner’s Dilemma 28
Focal points 32
2.8 Best response functions 35
2.9 Dominated actions 45
2.10 Equilibrium in a single population: symmetric games and
symmetric equilibria 50
Notes 53
3 Nash Equilibrium: Illustrations 55
3.1 Cournot’s model of oligopoly 55
3.2 Bertrand’s model of oligopoly 63
Cournot, Bertrand, and Nash: some historical notes 69
3.3 Electoral competition 70
3.4 The War of Attrition 77
v
vi Contents
3.5 Auctions 80
Auctions from Babylonia to eBay 81
3.6 Accident law 91
Notes 97
4 Mixed Strategy Equilibrium 99
4.1 Introduction 99
Some evidence on expected payoff functions 104
4.2 Strategic games in which players may randomize 106
4.3 Mixed strategy Nash equilibrium 107
4.4 Dominated actions 120
4.5 Pure equilibria when randomization is allowed 122
4.6 Illustration: expert diagnosis 123
4.7 Equilibrium in a single population 128
4.8 Illustration: reporting a crime 131
Reporting a crime: social psychology and game theory 133
4.9 The formation of players’ beliefs 134
4.10 Extension: finding all mixed strategy Nash equilibria 137
4.11 Extension: games in which each player has a continuum of actions 142
4.12 Appendix: representing preferences by expected payoffs 146
Notes 150
5 Extensive Games with Perfect Information: Theory 153
5.1 Extensive games with perfect information 153
5.2 Strategies and outcomes 159
5.3 Nash equilibrium 161
5.4 Subgame perfect equilibrium 164
5.5 Finding subgame perfect equilibria of finite horizon games:
backward induction 169
Ticktacktoe, chess, and related games 178
Notes 179
6 Extensive Games with Perfect Information: Illustrations 181
6.1 The ultimatum game, the holdup game, and agenda control 181
Experiments on the ultimatum game 183
6.2 Stackelberg’s model of duopoly 187
6.3 Buying votes 192
6.4 A race 197
Notes 203
7 Extensive Games with Perfect Information: Extensions and Discussion 205
7.1 Allowing for simultaneous moves 205
More experimental evidence on subgame perfect equilibrium 211
7.2 Illustration: entry into a monopolized industry 213
7.3 Illustration: electoral competition with strategic voters 215
Contents vii
7.4 Illustration: committee decision-making 217
7.5 Illustration: exit from a declining industry 221
7.6 Allowing for exogenous uncertainty 225
7.7 Discussion: subgame perfect equilibrium and backward induction 231
Experimental evidence on the centipede game 234
Notes 236
8 Coalitional Games and the Core 239
8.1 Coalitional games 239
8.2 The core 243
8.3 Illustration: ownership and the distribution of wealth 247
8.4 Illustration: exchanging homogeneous horses 251
8.5 Illustration: exchanging heterogeneous houses 256
8.6 Illustration: voting 260
8.7 Illustration: matching 263
Matching doctors with hospitals 268
8.8 Discussion: other solution concepts 269
Notes 270
II Games with Imperfect Information 271
9 Bayesian Games 273
9.1 Motivational examples 273
9.2 General definitions 278
9.3 Two examples concerning information 282
9.4 Illustration: Cournot’s duopoly game with imperfect information 285
9.5 Illustration: providing a public good 289
9.6 Illustration: auctions 291
Auctions of the radio spectrum 300
9.7 Illustration: juries 301
9.8 Appendix: auctions with an arbitrary distribution of valuations 307
Notes 311
10 Extensive Games with Imperfect Information 313
10.1 Extensive games with imperfect information 313
10.2 Strategies 317
10.3 Nash equilibrium 318
10.4 Beliefs and sequential equilibrium 323
10.5 Signaling games 331
10.6 Illustration: conspicuous expenditure as a signal of quality 336
10.7 Illustration: education as a signal of ability 340
10.8 Illustration: strategic information transmission 343
10.9 Illustration: agenda control with imperfect information 351
Notes 357
viii Contents
III Variants and Extensions 359
11 Strictly Competitive Games and Maxminimization 361
11.1 Maxminimization 361
11.2 Maxminimization and Nash equilibrium 364
11.3 Strictly competitive games 365
11.4 Maxminimization and Nash equilibrium in strictly competitive games 367
Maxminimization: some history 370
Empirical tests: experiments, tennis, and soccer 373
Notes 375
12 Rationalizability 377
12.1 Rationalizability 377
12.2 Iterated elimination of strictly dominated actions 385
12.3 Iterated elimination of weakly dominated actions 388
12.4 Dominance solvability 391
Notes 392
13 Evolutionary Equilibrium 393
13.1 Monomorphic pure strategy equilibrium 394
Evolutionary game theory: some history 399
13.2 Mixed strategies and polymorphic equilibrium 400
13.3 Asymmetric contests 406
Side-blotched lizards 407
Explaining the outcomes of contests in nature 409
13.4 Variation on a theme: sibling behavior 411
13.5 Variation on a theme: the nesting behavior of wasps 414
13.6 Variation on a theme: the evolution of the sex ratio 416
Notes 417
14 Repeated Games: The Prisoner’s Dilemma 419
14.1 The main idea 419
14.2 Preferences 421
14.3 Repeated games 423
14.4 Finitely repeated Prisoner’s Dilemma 424
14.5 Infinitely repeated Prisoner’s Dilemma 426
14.6 Strategies in an infinitely repeated Prisoner’s Dilemma 426
14.7 Some Nash equilibria of an infinitely repeated Prisoner’s Dilemma 428
14.8 Nash equilibrium payoffs of an infinitely repeated Prisoner’s Dilemma 431
Experimental evidence 436
14.9 Subgame perfect equilibria and the one-deviation property 437
Axelrod’s tournaments 439
Contents ix
14.10 Some subgame perfect equilibria of an infinitely repeated
Prisoner’s Dilemma 441
Reciprocal altruism among sticklebacks 445
14.11 Subgame perfect equilibrium payoffs of an infinitely repeated
Prisoner’s Dilemma 446
Medieval trade fairs 448
14.12 Concluding remarks 449
Notes 449
15 Repeated Games: General Results 451
15.1 Nash equilibria of general infinitely repeated games 451
15.2 Subgame perfect equilibria of general infinitely repeated games 455
15.3 Finitely repeated games 460
15.4 Variation on a theme: imperfect observability 461
Notes 463
16 Bargaining 465
16.1 Bargaining as an extensive game 465
16.2 Illustration: trade in a market 477
16.3 Nash’s axiomatic model 481
16.4 Relation between strategic and axiomatic models 489
Notes 491
17 Appendix: Mathematics 493
17.1 Numbers 493
17.2 Sets 494
17.3 Functions 495
17.4 Profiles 498
17.5 Sequences 499
17.6 Probability 499
17.7 Proofs 505
References 507
Index 525
Preface
AME - THEORETIC REASONING pervades economic theory and is used widely
G in other social and behavioral sciences. This book presents the main ideas
of game theory and shows how they can be used to understand economic, social,
political, and biological phenomena. It assumes no knowledge of economics, po-
litical science, or any other social or behavioral science. It emphasizes the ideas be-
hind the theory rather than their mathematical expression and assumes no specific
mathematical knowledge beyond that typically taught in U.S. and Canadian high
schools. (Chapter 17 reviews the mathematical concepts used in the book.) In par-
ticular, calculus is not used, except in the appendix of Chapter 9 (Section 9.8). Nev-
ertheless, all concepts are defined precisely, and logical reasoning is used through-
out. My aim is to explain the main ideas of game theory as simply as possible
while maintaining complete precision; the more comfortable you are with tight
logical analysis, the easier you will find the arguments.
The only way to appreciate the theory is to see it in action, or better still to put
it into action. So the book includes a wide variety of illustrations from the social
and behavioral sciences, and over 280 exercises.
The structure of the book is illustrated in the figure on the next page. The
gray boxes indicate core chapters (the darker gray, the more important). A black
arrow from Chapter i to Chapter j means that Chapter j depends on Chapter i.
The gray arrow from Chapter 4 to Chapter 9 means that the latter depends weakly
on the former; for all but Section 9.7 only an understanding of expected payoffs
(Section 4.1.3) is required, not a knowledge of mixed strategy Nash equilibrium.
(Two chapters are not included in this figure: Chapter 1 reviews the theory of a
single rational decision-maker, and Chapter 17 reviews the mathematical concepts
used in the book.)
Each topic is presented with the aid of “Examples”, which highlight theoreti-
cal points, and “Illustrations”, which demonstrate how the theory may be used to
understand social, economic, political, and biological phenomena. The “Illustra-
tions” introduce no new theoretical points, and any or all of them may be skipped
without loss of continuity. The “Illustrations” for the key models of strategic and
extensive games are grouped in separate chapters (3 and 6).
The limited dependencies between chapters mean that several routes may be
taken through the book.
• At a minimum, you should study Chapters 2 (Nash Equilibrium: Theory)
and 5 (Extensive Games with Perfect Information: Theory).
• Optionally you may sample some sections of Chapters 3 (Nash Equilibrium:
Illustrations) and 6 (Extensive Games with Perfect Information: Illustrations).
xi
xii Preface
Strategic games
3: Illustrations (55)
4: Mixed strategies (99)
Imperfect information
2: Theory (13) 9: Bayesian games (273)
Topics
11: Maxminimization (361)
12: Rationalizability (377)
13: Evolutionary equilibrium (393)
Extensive games
6: Illustrations (181)
7: Extensions (205)
Imperfect information
5: Theory (153) 10: Signaling games (313)
Topics
14, 15: Repeated games (419, 451)
16: Bargaining (465)
Coalitional games
8: Core (239)
The structure of the book. Each chapter is represented by a box whose area is proportional to the length
of the chapter; the number in parentheses is the page on which the chapter begins. Boxes shaded
gray correspond to core chapters; dark gray chapters are more central than light gray ones. An arrow
from Chapter i to Chapter j means that Chapter i is a prerequisite for Chapter j. The gray arrow from
Chapter 4 to Chapter 9 means that the latter depends only weakly on the former.
Preface xiii
• You may add to this plan any combination of Chapters 4 (Mixed Strategy
Equilibrium), 9 (Bayesian Games, except Section 9.7, which requires Chap-
ter 4), 7 (Extensive Games with Perfect Information: Extensions and Discus-
sion), 8 (Coalitional Games and the Core), and 16 (Bargaining).
• If you read Chapter 4 (Mixed Strategy Equilibrium), then you may in ad-
dition study any combination of the remaining chapters covering strategic
games, and if you study Chapter 7 (Extensive Games with Perfect Informa-
tion: Extensions and Discussion), then you are ready to tackle Chapters 14
and 15 (Repeated Games).
Whichever route you take, you can choose the examples and illustrations to fit
one of several themes. You can, for instance, study all the economic examples, or
all the political or biological ones. Alternatively, you can build a course around
all the examples on a more narrow topic; two possibilities are auction theory and
oligopoly theory.
All the material is intended to be accessible to undergraduate students. A one-
semester course for third or fourth year North American economics majors (who
have been exposed to a few of the main ideas in first and second year courses)
could cover up to about half the material in the book in moderate detail.
Osborne and Rubinstein (1994), a graduate text, offers a more advanced treat-
ment of the field. With few exceptions, the two books use the same notation and
terminology. The exceptions are noted on the website for this book (see the end of
the preface).
Examples modeling economic, political, and biological phenomena
The main examples that involve economic, political, or biological phenomena
are listed below. (Examples used to make a primarily game-theoretic point are
omitted.)
Economic phenomena
Accident law: Section 3.6
Adverse selection: Exercise 282.3
Auctions: Section 3.5 (perfect information), Example 143.1 (all-pay), Section 9.6
(imperfect information), Section 9.8 (imperfect information)
Bertrand’s model of oligopoly: Section 3.2, Exercise 136.2, Exercise 146.1,
Exercise 192.1, Exercise 214.1, Exercise 392.1 (dominance solvability),
Exercise 454.3 (repeated game), Exercise 459.1, Exercise 459.2, Section 15.4
(repeated game with imperfectly observable actions)
Chain-store game: Example 231.1
Collective decision-making: Section 2.9.4
Common property: Section 3.1.5
xiv Preface
Competition in product characteristics: Exercise 76.1
Cournot’s model of oligopoly: Section 3.1, Exercise 136.1, Section 9.4 (imperfect
information), Exercise 388.2 (rationalizability)
Entry into an industry by a financially-constrained challenger: Exercise 174.2
Entry into a monopolized industry: Section 7.2
Exit from a declining industry: Section 7.5
Expert diagnosis: Section 4.6
Firm–union bargaining: Exercise 177.1, Exercise 227.2, Exercise 489.1
Holdup game: Section 6.1.2
Market games: Exercise 211.2, Example 245.5, Section 8.4, Section 8.5, Section 16.2
Matching: Example 242.2, Section 8.7
Ownership and the distribution of wealth: Example 240.2, Example 244.2,
Section 8.3
Price competition between sellers: Exercise 128.1, Exercise 212.1
Provision of a public good: Exercise 33.1, Section 2.8.4, Exercise 44.1,
Exercise 132.3, Section 9.5, Exercise 388.1 (rationalizability)
Reporting a crime (private provision of a public good): Section 4.8
“Rotten kid theorem”: Exercise 177.2
Signaling ability with education: Section 10.7
Signaling quality with conspicuous expenditure: Section 10.6
Stackelberg’s model of duopoly: Section 6.2
Strategic information transmission: Section 10.8
Timing product release: Exercise 80.1
Political phenomena
Agenda control: Section 6.1.3 (perfect information), Section 10.9 (imperfect
information)
Allocating resources in election campaigns: Exercise 141.3
Approval voting: Exercise 49.2
Buying votes in a legislature: Section 6.3
Cohesion of governing coalitions in legislatures: Exercise 228.1
Collective decision-making: Section 2.9.4
Committee decision-making: Section 7.4
Electoral competition between citizen-candidates: Exercise 75.2
Electoral competition between policy-motivated candidates: Exercise 75.1
Hotelling’s model of electoral competition: Section 3.3, Exercise 196.3,
Exercise 196.4, Section 7.3 (strategic voters), Exercise 387.5 (rationalizability),
Exercise 454.2 (repeated game)
Juries: Section 9.7
Lobbying as an auction: Exercise 91.1
Majority game: Example 240.3, Exercise 245.1
Vote trading: Exercise 247.1
Voter participation: Exercise 34.2, Exercise 118.2
Preface xv
Voting: Section 2.9.3 (strategic game), Section 8.6 (coalitional game),
Exercise 307.1 (swing voter’s curse), Exercise 391.3 (dominance solvability)
Voting by alternating veto: Exercise 173.3
Biological phenomena
Evolution of sex ratio: Section 13.6
Hawk–Dove: Example 398.2, Example 404.2, Example 409.1
Hermaphroditic fish: Exercise 18.1
Nesting behavior of wasps: Section 13.5
Reciprocal altruism: Box on page 445
Sibling competition: Section 13.4
Signaling hunger (Sir Philip Sydney game): Exercise 335.2
War of Attrition: Section 3.4
Personal pronouns
The English language lacks a third person singular pronoun widely interpreted
to be sex neutral. In particular, many experiments have shown that “he” is not
neutral1 , a finding consistent with the observation that whereas people may say
“when an airplane pilot is working, he needs to concentrate”, they do not usually
say “when a flight attendant is working, he needs to concentrate” or “when a secre-
tary is working, he needs to concentrate”. To quote the American Heritage Dictionary
(third edition, page 831), “Thus he is not really a gender-neutral pronoun; rather
it refers to a male who is to be taken as the representative member of the group
referred to by its antecedent. The traditional usage, then, is not simply a gram-
matical convention; it also suggests a particular pattern of thought.” Like many
writers, I regard as unacceptable the bias implicit in the use of “he” for individu-
als of unspecified sex. The New Oxford Dictionary of English states the case clearly:
“[the use of he to refer to a person of unspecified sex] has become . . . a hallmark of
old-fashioned language or sexism in language.” Writers have become sensitive to
this issue in the last fifty years, but the lack of a sex-neutral pronoun “has been felt
since at least as far back as Middle English” (Webster’s Dictionary of English Usage,
Merriam-Webster Inc. 1989, 499). A common solution has been to use “they”,2 a
usage that the New Oxford Dictionary of English endorses (and employs). In some
contexts this usage sounds natural, but in others it does not; it can also create am-
biguity when the pronoun follows references to more than one person. I choose a
different solution: I use “she” exclusively. Obviously this usage, like that of “he”,
1 See, for example, Janice Moulton, George M. Robinson, and Cherin Elias, “Sex bias in language
use: ‘neutral’ pronouns that aren’t”, American Psychologist 33 (1978), 1032–1036; Janet Shibley Hyde,
“Children’s understanding of sexist language”, Development Psychology 20 (1984), 697–706; and John
Gastil, “Generic pronouns and sexist language: the oxymoronic character of masculine generics”, Sex
Roles 23 (1990), 629–643.
2
For a discussion of the history of the use of “they”, see Ann Bodine, “Androcentrism in prescriptive
grammar: singular ‘they’, sex-indefinite ‘he’, and ‘he or she’ ”, Language in Society 4 (1975), 129–146.
xvi Preface
is not sex neutral, but it may help to counterbalance the widespread use of “he”,
and seems unlikely to do any harm.
References
The “Notes” section at the end of each chapter attempts to assign credit for the
ideas discussed. Several cases present difficulties. In some cases, ideas evolved
over a long period of time, with contributions by many people, making their ori-
gins hard to summarize in a sentence or two. In a few cases, my research has led
to a conclusion about the origins of an idea different from the standard one. In all
cases, I cite the relevant papers without regard to their difficulty.
Over the years, I have taken exercises from many sources. I have attempted to
remember the origins of the ones I use in this book, and give credit appropriately.
Conventions, numbering, and nomenclature
I use the term “dollar” for a unit of money because it is probably recognizable as
such to a majority of readers of this book, even if they pay their bills in rupees,
yuan, or pa’anga.
In formal definitions, the terms being defined are set in boldface. Terms set in
italics are informal definitions.
Definitions, propositions, lemmas, examples, exercises, and equations are num-
bered according to the page on which they appear. If the first such object on
page n is an exercise, for example, it is called Exercise n.1; if the next object on
that page is a definition, it is called Definition n.2. For example, the definition
of a strategic game with ordinal preferences on page 13 is Definition 13.1. Fig-
ures are numbered separately, using the same page-based system. The scheme
allows numbered items to be found rapidly and enhances the precision of index
entries.
Symbol/term Meaning
? Exercise, with solution on website
?? Hard exercise, with solution on website
? Exercise, with solution available only to instructors
(see website for conditions)
?? Hard exercise, with solution available only to instructors
(see website for conditions)
◮ Definition
Result
Example: a game that illustrates a game-theoretic point
Illustration A game, or family of games, that shows how the theory can
illuminate observed phenomena
Preface xvii
Acknowledgments
I owe a huge debt to Ariel Rubinstein. I have learned, and continue to learn, vastly
from him about game theory. His influence on this book will be clear to anyone
familiar with our jointly authored book A course in game theory. Had we not written
that book and our previous book Bargaining and markets, I doubt that I would have
embarked on this project.
I was privileged as a graduate student at Stanford University to learn game
theory from Robert Aumann, Sergiu Hart, Mordecai Kurz, Al Roth, and Robert
Wilson. Discussions over the years with Jean-Pierre Benoît, Haruo Imai, Vijay
Krishna, Michael Peters, and Carolyn Pitchik have improved my understanding
of many game-theoretic topics.
Many people have generously commented on all or parts of drafts of the book.
I am particularly grateful to Peter McCabe for many very thoughtful comments.
I am very grateful also to Gian Luigi Albano, Jeffrey Banks, Nikolaos Benos, Ted
Bergstrom, Tilman Börgers, Randy Calvert, Vu Cao, In-Koo Cho, Rachel Croson,
Eddie Dekel, Marina De Vos, Laurie Duke, Patrick Elias, Mukesh Eswaran, Xinhua
Gu, Costas Halatsis, Joe Harrington, Hiroyuki Kawakatsu, Lewis Kornhauser, Jack
Leach, Tao Li, Simon Link, Bart Lipman, Kin Chung Lo, Massimo Marinacci, Mas-
simo Morelli, Nathan Nunn, Barry O’Neill, Robin G. Osborne, Marco Ottaviani,
Carolyn Pitchik, Marie Rekkas, Bob Rosenthal, Al Roth, Matthew Shum, Branislav
L. Slantchev, Giora Slutzki, Michael Smart, Nick Vriend, Charles A. Wilson, Luís
Zemborain, and several anonymous reviewers.
My editors at Oxford University Press, Kenneth MacLeod and Stephen Mc-
Groarty, offered much encouragement and advice. Their enthusiasm for the project
was a great help in keeping the book on track. The many suggestions of Oxford’s
production editor Brian Kinsey greatly improved the appearance of the book.
The book has its origins in a course I taught at Columbia University in the
early 1980s. My experience in that course, and in courses at McMaster University
and the University of Toronto, brought the book to its current form. The Kyoto
Institute of Economic Research at Kyoto University and the School of Economics
at the Australian National University provided me with splendid environments in
which to work on the book during visits in 1999 and 2001.
I maintain a website for the book. The current URL is
http://www.economics.utoronto.ca/osborne/igt/
M ARTIN J. O SBORNE
martin.osborne@utoronto.ca
http://www.economics.utoronto.ca/osborne/
Department of Economics, University of Toronto
150 St. George Street, Toronto, Canada, M5S 3G7
May 2003
