![]()
Chapter 1
Normal and Extensive Form Games
1.1Normal Form Games
Most introductions to game theory start with the prisoner’s dilemma.1 Two suspects (I and II) are separately interrogated. The prosecutors have sufficient evidence to convict each of a minor offence, but wish to convict them of a major offence. The potential results of the interrogation are illustrated in Figure 1.1.1. Clearly, no matter what the other suspect does, it is always better to confess than not confess.
This game is often interpreted as a partnership game, in which two partners simultaneously choose between exerting effort and shirking. Effort E produces an output of 6 at a cost of 4, while shirking S yields no output at no cost. Total output is shared equally. The result is given in Figure 1.1.2. With this formulation, no matter what the other partner does (E or S), the partner maximizes his/her payoff by shirking.
The scenarios illustrated in Figures 1.1.1 and 1.1.2 are examples of normal form games.
Definition 1.1.1. An n-player normal (or strategic) form game G is an n-tuple {(S1, U1), . . . , (Sn, Un)}, where for each player i,
•Si is a nonempty set, i’s strategy space, with typical element si, and
Figure 1.1.1:The prisoner’s dilemma, with the numbers describing length of sentence (the minus signs indicate that longer sentences are less desirable). In each cell, the first number is player I’s sentence, while the second is player II’s.
Figure 1.1.2:The prisoner’s dilemma, as a partnership game. In each cell, the first number is the row player’s payoff, while the second number is the column player’s payoff.
The normal form game G is finite if n < ∞ and |Si| < ∞ for all i.
Notation: The set of strategy profiles is
, with a
strategy profile denoted by
s ≔ (
s1, . . . ,
sn) ∈
S. The strategy profile omitting player
i’s strategy is
s−i ≔ (
s1, . . . ,
si−1,
si+1, . . . ,
sn) ∈
S−i ≔ ∏
k≠i Sk. Finally,
, so that
s = (
si,
s−i).
We sometimes write payoffs as a vector-valued function
U :
S →
n, or when
S is finite, as the vector
U ∈
n|S| (recall that a vector
x ∈
k can be viewed as the function
x : {1, . . . ,
k} →
, and conversely, a function from the finite set {1, . . . ,
k} to a set
Y can be viewed as a vector in
Yk).
Example 1.1.1 (Sealed-bid second-price auction). Two bidders simultaneously submit bids (in sealed envelopes) for an object. A bid is a nonnegative number, with
i’s bid denoted by
bi ∈
+. Bidder
i’s value for the object (reservation price, willingess to pay) is denoted by
υi. The object is awarded to the highest bidder, who pays the second highest bid. Ties are resolved
by a fair coin toss. Then,
n = 2,
Si =
+, and (taking expectations)
Example 1.1.2 (Sealed bi...
