Sách A Course in Game Theory (373 pages) - Martin J. Osborne Ariel Rubinstein

A Course in Game Theory (373 pages)
Martin J. Osborne
Ariel Rubinstein

CONTENTS
Preface xi
1
Introduction
1
1.1 Game Theory 1
1.2 Games and Solutions 2
1.3 Game Theory and the Theory of Competitive Equilibrium 3
1.4 Rational Behavior 4
1.5 The Steady State and Deductive Interpretations 5
1.6 Bounded Rationality 6
1.7 Terminology and Notation 6
Notes 8
I
Strategic Games
9
2
Nash Equilibrium
11
2.1 Strategic Games 11
2.2 Nash Equilibrium 14
2.3 Examples 15
2.4 Existence of a Nash Equilibrium 19
2.5 Strictly Competitive Games 21
2.6 Bayesian Games: Strategic Games with Imperfect Information 24
Notes 29
Page vi
3
Mixed, Correlated, and Evolutionary Equilibrium
31
3.1 Mixed Strategy Nash Equilibrium 31
3.2 Interpretations of Mixed Strategy Nash Equilibrium 37
3.3 Correlated Equilibrium 44
3.4 Evolutionary Equilibrium 48
Notes 51
4
Rationalizability and Iterated Elimination of Dominated Actions
53
4.1 Rationalizability 53
4.2 Iterated Elimination of Strictly Dominated Actions 58
4.3 Iterated Elimination of Weakly Dominated Actions 62
Notes 64
5
Knowledge and Equilibrium
67
5.1 A Model of Knowledge 67
5.2 Common Knowledge 73
5.3 Can People Agree to Disagree? 75
5.4 Knowledge and Solution Concepts 76
5.5 The Electronic Mail Game 81
Notes 84
II
Extensive Games with Perfect Information
87
6
Extensive Games with Perfect Information
89
6.1 Extensive Games with Perfect Information 89
6.2 Subgame Perfect Equilibrium 97
6.3 Two Extensions of the Definition of a Game 101
6.4 The Interpretation of a Strategy 103
6.5 Two Notable Finite Horizon Games 105
6.6 Iterated Elimination of Weakly Dominated Strategies 108
Notes 114
7
Bargaining Games
117
7.1 Bargaining and Game Theory 117
7.2 A Bargaining Game of Alternating Offers 118
7.3 Subgame Perfect Equilibrium 121
7.4 Variations and Extensions 127
Notes 131
8
Repeated Games
133
8.1 The Basic Idea 133
8.2 Infinitely Repeated Games vs. Finitely Repeated Games 134
8.3 Infinitely Repeated Games: Definitions 136
8.4 Strategies as Machines 140
8.5 Trigger Strategies: Nash Folk Theorems 143
8.6 Punishing for a Limited Length of Time: A Perfect Folk Theorem for
the Limit of Means Criterion
146
8.7 Punishing the Punisher: A Perfect Folk Theorem for the Overtaking
Criterion
149
8.8 Rewarding Players Who Punish: A Perfect Folk Theorem for the
Discounting Criterion
150
8.9 The Structure of Subgame Perfect Equilibria Under the Discounting
Criterion
153
8.10 Finitely Repeated Games 155
Notes 160
9
Complexity Considerations in Repeated Games
163
9.1 Introduction 163
9.2 Complexity and the Machine Game 164
9.3 The Structure of the Equilibria of a Machine Game 168
9.4 The Case of Lexicographic Preferences 172
Notes 175
10
Implementation Theory
177
10.1 Introduction 177
10.2 The Implementation Problem 178
10.3 Implementation in Dominant Strategies 180
10.4 Nash Implementation 185
10.5 Subgame Perfect Equilibrium Implementation 191
Notes 195
Page viii
III
Extensive Games with Imperfect Information
197
11
Extensive Games with Imperfect Information
199
11.1 Extensive Games with Imperfect Information 199
11.2 Principles for the Equivalence of Extensive Games 204
11.3 Framing Effects and the Equivalence of Extensive Games 209
11.4 Mixed and Behavioral Strategies 212
11.5 Nash Equilibrium 216
Notes 217
12
Sequential Equilibrium
219
12.1 Strategies and Beliefs 219
12.2 Sequential Equilibrium 222
12.3 Games with Observable Actions: Perfect Bayesian Equilibrium 231
12.4 Refinements of Sequential Equilibrium 243
12.5 Trembling Hand Perfect Equilibrium 246
Notes 254
IV
Coalitional Games
255
13
The Core
257
13.1 Coalitional Games with Transferable Payoff 257
13.2 The Core 258
13.3 Nonemptiness of the Core 262
13.4 Markets with Transferable Payoff 263
13.5 Coalitional Games without Transferable Payoff 268
13.6 Exchange Economies 269
Notes 274
14
Stable Sets, the Bargaining Set, and the Shapley Value
277
14.1 Two Approaches 277
14.2 The Stable Sets of yon Neumann and Morgenstern 278
14.3 The Bargaining Set, Kernel, and Nucleolus 281
14.4 The Shapley Value 289
Notes 297
Page ix
15
The Nash Solution
299
15.1 Bargaining Problems 299
15.2 The Nash Solution: Definition and Characterization 301
15.3 An Axiomatic Definition 305
15.4 The Nash Solution and the Bargaining Game of Alternating
Offers
310
15.5 An Exact Implementation of the Nash Solution 311
Notes 312
List of Results 313
References 321
Index 341
Page xi
PREFACE
This book presents some of the main ideas of game theory. It is designed to serve as a textbook for a one-semester graduate course consisting of about 28 meetings each of 90 minutes.
The topics that we cover are those that we personally would include in such a one-semester course. We do not
pretend to provide a complete reference book on game theory and do not necessarily regard the topics that we
exclude as unimportant. Our selection inevitably reflects our own preferences and interests. (Were we to start
writing the book now we would probably add two chapters, one on experimental game theory and one on learning
and evolution.)
We emphasize the foundations of the theory and the interpretation of f the main concepts. Our style is to give
precise definitions and full proofs of results, sacrificing generality and limiting the scope of the material when
necessary to most easily achieve these goals.
We have made a serious effort to give credit for an the concepts, results, examples, and exercises (see the "Notes" at the end of each chapter). We regret any errors and encourage you to draw our attention to them.




1
Introduction
1.1 Game Theory
Game theory is a bag of analytical tools designed to help us understand the phenomena that we observe when
decision-makers interact. The basic assumptions that underlie the theory are that decision-makers pursue welldefined
exogenous objectives (they are rational) and take into account their knowledge or expectations of other
decision-makers' behavior (they reason strategically).
The models of game theory are highly abstract representations of classes of real-life situations. Their abstractness
allows them to be used to study a wide range of phenomena. For example, the theory of Nash equilibrium (Chapter
2) has been used to study oligopolistic and political competition. The theory of mixed strategy equilibrium
(Chapter 3) has been used to explain the distributions of tongue length in bees and tube length in flowers. The
theory of repeated games (Chapter 8) has been used to illuminate social phenomena like threats and promises. The
theory of the core (Chapter 13) reveals a sense in which the outcome of trading under a price system is stable in an
economy that contains many agents.
The boundary between pure and applied game theory is vague; some developments in the pure theory were
motivated by issues that arose in applications. Nevertheless we believe that such a line can be drawn. Though we
hope that this book appeals to those who are interested in applications, we stay almost entirely in the territory of
"pure" theory. The art of applying an abstract model to a real-life situation should be the subject of another tome.
Game theory uses mathematics to express its ideas formally. However, the game theoretical ideas that we discuss
are not inherently mathematPage
2
ical; in principle a book could be written that had essentially the same content as this one and was devoid of
mathematics. A mathematical formulation makes it easy to define concepts precisely, to verify the consistency of
ideas, and to explore the implications of assumptions. Consequently our style is formal: we state definitions and
results precisely, interspersing them with motivations and interpretations of the concepts.
The use of mathematical models creates independent mathematical interest. In this book, however, we treat game
theory not as a branch of mathematics but as a social science whose aim is to understand the behavior of interacting
decision-makers; we do not elaborate on points of mathematical interest. From our point of view the mathematical
results are interesting only if they are confirmed by intuition.
1.2 Games and Solutions
A game is a description of strategic interaction that includes the constraints on the actions that the players can take
and the players' interests, but does not specify the actions that the players do take. A solution is a systematic
description of the outcomes that may emerge in a family of games. Game theory suggests reasonable solutions for
classes of games and examines their properties.
We study four groups of game theoretic models, indicated by the titles of the four parts of the book: strategic
games (Part I), extensive games with and without perfect information (Parts II and III), and coalitional games (Part
IV). We now explain some of the dimensions on which this division is based.
Noncooperative and Cooperative Games
In all game theoretic models the basic entity is a player. A player may be interpreted as an individual or as a group
of individuals making a decision. Once we define the set of players, we may distinguish between two types of
models: those in which the sets of possible actions of individual players are primitives (Parts I, II, and III) and
those in which the sets of possible joint actions of groups of players are primitives (Part IV). Sometimes models of
the first type are referred to as "noncooperative", while those of the second type are referred to as
"cooperative" (though these terms do not express well the differences between the models).
The numbers of pages that we devote to each of these branches of the theory reflect the fact that in recent years
most research has been
Page 3
devoted to noncooperative games; it does not express our evaluation of the relative importance of the two branches.
In particular, we do not share the view of some authors that noncooperative models are more "basic" than
cooperative ones; in our opinion, neither group of models is more "basic" than the other.
Strategic Games and Extensive Games
In Part I we discuss the concept of a strategic game and in Parts II and III the concept of an extensive game. A
strategic game is a model of a situation in which each player chooses his plan of action once and for all, and all
players' decisions are made simultaneously (that is, when choosing a plan of action each player is not informed of
the plan of action chosen by any other player). By contrast, the model of an extensive game specifies the possible
orders of events; each player can consider his plan of action not only at the beginning of the game but also
whenever he has to make a decision.
Games with Perfect and Imperfect Information
The third distinction that we make is between the models in Parts II and III. In the models in Part II the participants
are fully informed about each others' moves, while in the models in Part III they may be imperfectly informed. The
former models have firmer foundations. The latter were developed intensively only in the 1980s; we put leas
emphasis on them not because they are less realistic or important but because they are less mature.
1.3 Game Theory and the Theory of Competitive Equilibrium
To clarify further the nature of game theory, we now contrast it with the theory of competitive equilibrium that is
used in economics. Game theoretic reasoning takes into account the attempts by each decision-maker to obtain,
prior to making his decision, information about the other players' behavior, while competitive reasoning assumes
that each agent is interested only in some environmental parameters (such as prices), even though these parameters
are determined by the actions of all agents.
To illustrate the difference between the theories, consider an environment in which the level of some activity (like
fishing) of each agent depends on the level of pollution, which in turn depends on the levels of
Page 4
the agents' activities. In a competitive analysis of this situation we look for a level of pollution consistent with the
actions that the agents take when each of them regards this level as given. By contrast, in a game theoretic analysis
of the situation we require that each agent's action be optimal given the agent's expectation of the pollution created
by the combination of his action and all the other agents' actions.
1.4 Rational Behavior
The models we study assume that each decision-maker is "rational" in the sense that he is aware of his alternatives,
forms expectations about any unknowns, has clear preferences, and chooses his action deliberately after some
process of optimization. In the absence of uncertainty the following elements constitute a model of rational choice.
ã A set A of actions from which the decision-maker makes a choice.
ã A set C of possible consequences of these actions.
ã A consequence function that associates a consequence with each action.
ãA preference relation (a complete transitive reflexive binary relation) on the set C.
Sometimes the decision-maker's preferences are specified by giving a utility function , which defines a
preference relation by the condition if and only if .
Given any set of actions that are feasible in some particular case, a rational decision-maker chooses an
action a* that is feasible (belongs to B) and optimal in the sense that for all ; alternatively he
solves the problem . An assumption upon which the usefulness of this model of decision-making
depends is that the individual uses the same preference relation when choosing from different sets B.
In the models we study, individuals often have to make decisions under conditions of uncertainty. The players may
be
ã uncertain about the objective parameters of the environment
ã imperfectly informed about events that happen in the game
ã uncertain about actions of the other players that are not deterministic
ã uncertain about the reasoning of the other players.
Page 5
To model decision-making under uncertainty, almost all game theory uses the theories of von Neumann and
Morgenstern (1944) and of Savage (1972). That is, if the consequence function is stochastic and known to the
decision-maker (i.e. for each the consequence g(a) is a lottery (probability distribution) on C) then the
decision-maker is assumed to behave as if he maximizes the expected value of a (von Neumann-Morgenstern
utility) function that attaches a number to each consequence. If the stochastic connection between actions and
consequences is not given, the decision-maker is assumed to behave as if he has in mind a (subjective) probability
distribution that determines the consequence of any action. In this case the decision-maker is assumed to behave as
if he has in mind. a "state space" W, a probability measure over W, a function , and a utility function
; he is assumed to choose an action a that maximizes the expected value of u(g(a,w)) with respect to the
probability measure.
We do not discuss the assumptions that underlie the theory of a rational decision-maker. However, we do point out
that these assumptions are under perpetual attack by experimental psychologists, who constantly point out severe
limits to its application.
1.5 The Steady State and Deductive Interpretations
There are two conflicting interpretations of solutions for strategic and extensive games. The steady state (or, as
Binmore (1987/88) calls it, evolutive) interpretation is closely related to that which is standard in economics. Game
theory, like other sciences, deals with regularities. As Carnap (1966, p. 3) writes, "The observations we make in
everyday life as well as the more systematic observations of science reveal certain repetitions or regularities in the
world The laws of science are nothing more than statements expressing these regularities as precisely as
possible." The steady state interpretation treats a game as a model designed to explain some regularity observed in
a family of similar situations. Each participant "knows" the equilibrium and tests the optimality of his behavior
given this knowledge, which he has acquired from his long experience. The deductive (or, as Binmore calls it,
eductive) interpretation, by contrast, treats a game in isolation, as a "one-shot" event, and attempts to infer the
restrictions that rationality imposes on the outcome; it assumes that each player deduces how the other players will
behave simply from principles of rationality. We try to avoid the confusion between the two interpretations that
frequently arises in game theory.
Page 6
1.6 Bounded Rationality
When we talk in real life about games we often focus on the asymmetry between individuals in their abilities. For
example, some players may have a clearer perception of a situation or have a greater ability to analyze it. These
difference, which are so critical in life, are missing from game theory in its current form.
To illustrate the consequences of this fact, consider the game of chess. In an actual play of chess the players may
differ in their knowledge of the legal moves and in their analytical abilities. In contrast, when chess is modeled
using current game theory it is assumed that the players' knowledge of the rules of the game is perfect and their
ability to analyze it is ideal. Results we prove in Chapters 2 and 6 (Propositions 22.2 and 99.2) imply that chess is a
trivial game for "rational" players: an algorithm exists that can be used to "solve" the game. This algorithm defines
a pair of strategies, one for each player, that leads to an "equilibrium" outcome with the property that a player who
follows his strategy can be sure that the outcome will be at least as good as the equilibrium outcome no matter what
strategy the other player uses. The existence of such strategies (first proved by Zermelo (1913)) suggests that chess
is uninteresting because it has only one possible outcome. Nevertheless, chess remains a very popular and
interesting game. Its equilibrium outcome is yet to be calculated; currently it is impossible to do so using the
algorithm. Even if White, for example, is shown one day to have a winning strategy, it may not be possible for a
human being to implement that strategy. Thus while the abstract model of chess allows us to deduce a significant
fact about the game, at the same time it omits the most important determinant of the outcome of an actual play of
chess: the players' "abilities".
Modeling asymmetries in abilities and in perceptions of a situation by different players is a fascinating challenge
for future research, which models of "bounded rationality" have begun to tackle.
1.7 Terminology and Notation
We presume little familiarity with mathematical results, but throughout use deductive reasoning. Our notation and
mathematical definitions are standard, but to avoid ambiguities we list some of them here.
We denote the set of real numbers by , the set of nonnegative real numbers by , the set of vectors of n real
numbers by , and the set of
Page 7
vectors of n nonnegative real numbers by . For and we use to mean . for i = 1, ., n and
x > y to mean xi > yi for i = 1, .,n. We say that a function is increasing if f (x) > f(y) whenever x > y and is
nondecreasing if whenever x > y. A function is concave if
for all , all , and all . Given a function we denote
by arg the set of maximizers of f; for any we denote by f(Y) the set .
Throughout we use N to denote the set of players. We refer to a collection of values of some variable, one for each
player, as a profile; we denote such a profile by , or, if the qualifier " " is clear, simply (xi). For any
profile and any we let x-i be the list of elements of the profile x for all players except i.
Given a list and an element xi we denote by (x-i, xi) the profile . If Xi is a set for each
then we denote by X-i the set .
A binary relation .gif"> is convex; it is strictly quasi-concave if every such set is strictly convex.
Let X be a set. We denote by |X| the number of members of X. A partition of X is a collection of disjoint subsets of
X whose union is X. Let N be a finite set and let be a set. Then is Pareto efficient if there is no
for which yi > xi for all is strongly Pareto efficient if there is no for which for all
and yi > xi for some .
A probability measure à on a finite (or countable) set X is an additive function that associates a nonnegative real
number with every subset of X (that is, whenever B and C are disjoint) and satisfies à(X) =
1. In some cases we work with probability measures over spaces that are not necessarily finite. If you are
unfamiliar with such measures, little is lost by restricting attention to the finite case; for a definition of more
general measures see, for example, Chung (1974, Ch. 2).
Page 8
Notes
Von Neumann and Morgenstern (1944) is the classic work in game theory. Luce and Raiffa (1957) is an early
textbook; although now out-of-date, it contains superb discussions of the basic concepts in the theory. Schelling
(1960) provides a verbal discussion of some of the main ideas of the theory.
A number of recent books cover much of the material in this book, at approximately the same level: Shubik (1982),
Moulin (1986), Friedman (1990), Kreps (1990a, Part III), Fudenberg and Tirole (1991a), Myerson (1991), van
Damme (1991), and Binmore (1992). Gibbons (1992) is a more elementary introduction to the subject.
Aumann (1985b) contains a discussion of the aims and achievements of game theory, and Aumann (1987b) is an
account of game theory from a historical perspective. Binmore (1987/88) is a critical discussion of game theory
that makes the distinction between the steady state and deductive interpretations. Kreps (1990b) is a reflective
discussion of many issues in game theory.
For an exposition of the theory of rational choice see Kreps (1988).