IE675 Game Theory

Lecture Note Set 1

Wayne F. Bialas1
Friday, March 30, 2001

1 INTRODUCTION
1.1 What is game theory?
Game theory is the study of problems of conflict and cooperation among independent
decision-makers.
Game theory deals with games of strategy rather than games of chance.
The ingredients of a game theory problem include

• players (decision-makers)
• choices (feasible actions)
• payoffs (benefits, prizes, or awards)
• preferences to payoffs (objectives)

We need to know when one choice is better than another for a particular player.

1.2 Classification of game theory problems

Problems in game theory can be classified in a number of ways.

1.2.1 Static vs. dynamic games

In dynamic games, the order of decisions are important.
Question 1.1. Is it ever really possible to implement static decision-making in prac-
tice?
1
Department of Industrial Engineering, University at Buffalo, 342 Bell Hall, Box 602050, Buffalo,
NY 14260-2050 USA; E-mail: bialas@buffalo.edu; Web: http://www.acsu.buffalo.edu/˜bialas.
Copyright c MMI Wayne F. Bialas. All Rights Reserved. Duplication of this work is prohibited
without written permission. This document produced March 30, 2001 at 2:31 pm.

1-1
1.2.2 Cooperative vs. non-cooperative
In a non-cooperative game, each player pursues his/her own interests. In a cooperative
games, players are allowed to form coalitions and combine their decision-making problems.

Non-cooperative Cooperative
Math programming Cooperative
Static Non-cooperative Game
Game Theory Theory
Cooperative
Dynamic Control Theory Dynamic
Games

Note 1.1. This area of study is distinct from multi-criteria decision making.
Flow of information is an important element in game theory problems, but it is sometimes
explicitly missing.

• noisy information
• deception

1.2.3 Related areas

• differential games
• optimal control theory
• mathematical economics

1.2.4 Application areas

• corporate decision making
• defense strategy
• market modelling
• public policy analysis
• environmental systems
• distributed computing
• telecommunications networks

1-2
1.2.5 Theory vs. simulation
The mathematical theory of games provides the fundamental laws and problem structure.
Games can also be simulated to assess complex economic systems.

1.3 Solution concepts

The notion of a “solution” is more tenuous in game theory than in other fields.
Definition 1.1. A solution is a systematic description of the outcomes that may emerge
from the decision problem.

• optimality (for whom??)

• feasibility
• equilibria

1.4 Games in extensive form

1.4.1 Example: Matching Pennies
• Player 1: Choose H or T
• Player 2: Choose H or T (not knowing Player 1’s choice)

• If the coins are alike, Player 2 wins 1 cent from Player 1

• If the coins are different, Player 1 wins 1 cent from Player 2

Written in extensive form, the game appears as follows

1-3
 Information Player 1
Set

S12 Player 2

(-1,1) (1,-1) (1,-1) (-1,1)

In order to deal with the issue of Player 2’s knowledge about the game, we introduce the
concept of an information set. When the game’s progress reaches Player 2’s time to move,
Player 2 is supposed to know Player 1’s choice. The set of nodes, S12 , is an information set
for Player 2.
A player only knows the possible options emanating from an information. A player does
not know which node within the information set is the actual node at which the progress of
play resides.
There are some obvious rules about information sets that we will formally describe later.

1-4
For example, the following cannot occur. . .

7KL FDQQR
KDSSHQ

Player 1

S12 Player 2

Definition 1.2. A player is said to have perfect information if all of his/her information
sets are singletons.

JDP
ZLW  SHUIHF  LQIRUPDWLRQ

Player 1

Player 2

1-5
 Definition 1.3. A strategy for Player i is a function which assigns to each of Player i’s
information sets, one of the branches which follows a representative node from that set.
Example 1.1. A strategy Ψ which has Ψ(S12 ) = H would tell Player 2 to select Heads
when he/she is in information set S12 .

1.5 Games in strategic form

1.5.1 Example: Matching Pennies
Consider the same game as above and the following matrix of payoffs:

Player 2
H T
Player 1 H (-1,1) (1,-1)
T ( 1,-1) (-1,1)

The rows represent the strategies of Player 1. The columns represent the strategies of Player
2.
Distinguish actions from strategies.
The matching pennies game is an example of a non-cooperative game.

1.6 Cooperative games

Cooperative games allow players to form coalitions to share decisions, information and
payoffs.
For example, if we have player set

N = {1, 2, 3, 4, 5, 6}

A possible coalition structure would be

{{1, 2, 3}, {4, 6}, {5}}

Often these games are described in characteristic function form. A characteristic function
is a mapping
v : 2N → R
and v(S) (where S ⊆ N ) is the “worth” of the coalition S.

1-6
1.7 Dynamic games
Dynamic games can be cooperative or non-cooperative in form.
One class of cooperative dynamic games are hierarchical (organizational) games.
Consider a hierarchy of players, for example,

President
Vice-President
.
..
Workers

Each level has control over a subset of all decision variables. Each may have an objective
function that depends on the decision variables of other levels. Suppose that the top level
makes his/her decision first, and then passes that information to the next level. The next
level then makes his/her decision, and the play progresses down through the hierarchy.
The key ingredient in these problems is preemption, i.e., the “friction of space and time.”
Even when everything is linear, such systems can produce stable, inadmissible solutions
(Chew).

stable: No one wants to unilaterally move away from the given solution point.
inadmissible: There are feasible solution points that produce better payoffs for all players
than the given solution point.

1-7
IE675 Game Theory

Lecture Note Set 2

Wayne F. Bialas1
Friday, March 30, 2001

2 TWO-PERSON GAMES
2.1 Two-Person Zero-Sum Games

2.1.1 Basic ideas

Definition 2.1. A game (in extensive form) is said to be zero-sum if and only if,
Pn
at each terminal vertex, the payoff vector (p1 , . . . , pn ) satisfies i=1 pi = 0.
Two-person zero sum games in normal form. Here’s an example. . .
 
−1 −3 −3 −2
 
A= 0 1 −2 −1 
2 −2 0 1
The rows represent the strategies of Player 1. The columns represent the strategies
of Player 2. The entries aij represent the payoff vector (aij , −aij ). That is, if
Player 1 chooses row i and Player 2 chooses column j , then Player 1 wins aij and
Player 2 loses aij . If aij < 0, then Player 1 pays Player 2 |aij |.
Note 2.1. We are using the term strategy rather than action to describe the player’s
options. The reasons for this will become evident in the next chapter when we use
this formulation to analyze games in extensive form.
Note 2.2. Some authors (in particular, those in the field of control theory) prefer
to represent the outcome of a game in terms of losses rather than profits. During
the semester, we will use both conventions.
1
Department of Industrial Engineering, University at Buffalo, 342 Bell Hall, Box 602050, Buffalo,
NY 14260-2050 USA; E-mail: bialas@buffalo.edu; Web: http://www.acsu.buffalo.edu/˜bialas.
Copyright c MMI Wayne F. Bialas. All Rights Reserved. Duplication of this work is prohibited
without written permission. This document produced March 30, 2001 at 2:31 pm.

2-1
How should each player behave? Player 1, for example, might want to place a
bound on his profits. Player 1 could ask “For each of my possible strategies, what
is the least desirable thing that Player 2 could do to minimize my profits?” For
each of Player 1’s strategies i, compute

αi = min aij
j

and then choose that i which produces maxi αi . Suppose this maximum is achieved
for i = i∗ . In other words, Player 1 is guaranteed to get at least

V (A) = min ai∗ j ≥ min aij i = 1, . . . , m

j j

The value V (A) is called the gain-floor for the game A.

In this case V (A) = −2 with i∗ ∈ {2, 3}.
Player 2 could perform a similar analysis and find that j ∗ which yields

V (A) = max aij ∗ ≤ max aij j = 1, . . . , n

i i

The value V (A) is called the loss-ceiling for the game A.

In this case V (A) = 0 with j ∗ = 3.
Now, consider the joint strategies (i∗ , j ∗ ). We immediately get the following:
‚ ƒ
Theorem 2.1. For every (finite) matrix game A = aij
1. The value V (A) and V (A) are unique.
2. There exists at least one security strategy for each player given by (i∗ , j ∗ ).
3. minj ai∗ j = V (A) ≤ V (A) = maxi aij ∗
Proof: (1) and (2) are easy. To prove (3) note that for any k and `,

min akj ≤ ak` ≤ max ai`

j i

and the result follows.

2-2
2.1.2 Discussion

Let’s examine the decision-making philosophy that underlies the choice of (i∗ , j ∗ ).
For instance, Player 1 appears to be acting as if Player 2 is trying to do as much
harm to him as possible. This seems reasonable since this is a zero-sum game.
Whatever, Player 1 wins, Player 2 loses.
As we proceed through this presentation, note that this same reasoning is also used
in the field of statistical decision theory where Player 1 is the statistician, and Player
2 is “nature.” Is it reasonable to assume that “nature” is a malevolent opponent?

2.1.3 Stability

Consider another example

 
−4 0 1
 
A= 0 1 −3 
−1 −2 −1

Player 1 should consider i∗ = 3 (V = −2) and Player 2 should consider j ∗ = 1

(V = 0).
However, Player 2 can continue his analysis as follows
• Player 2 will choose strategy 1
• So Player 1 should choose strategy 2 rather than strategy 3
• But Player 2 would predict that and then prefer strategy 3
and so on.
Question 2.1. When do we have a stable choice of strategies?
The answer to the above question gives rise to some of the really important early
results in game theory and mathematical programming.
We can see that if V (A) = V (A), then both Players will settle on (i∗ , j ∗ ) with

min ai∗ j = V (A) = V (A) = max aij ∗

j i

Theorem 2.2. If V (A) = V (A) then

1. A has a saddle point

2-3
 2. The saddle point corresponds to the security strategies for each player
3. The value for the game is V = V (A) = V (A)
Question 2.2. Suppose V (A) < V (A). What can we do? Can we establish a
“spy-proof” mechanism to implement a strategy?
Question 2.3. Is it ever sensible to use expected loss (or profit) as a perfor-
mance criterion in determining strategies for “one-shot” (non-repeated) decision
problems?

2.1.4 Developing Mixed Strategies

Consider the following matrix game. . .

" #
3 −1
A=
0 1

For Player 1, we have V (A) = 0 and i∗ = 2. For Player 2, we have V (A) = 1 and
j ∗ = 2. This game does not have a saddle point.
Let’s try to create a “spy-proof” strategy. Let Player 1 randomize over his two pure
strategies. That is Player 1 will pick the vector of probabilities x = (x1 , x2 ) where
P
i xi = 1 and xi ≥ 0 for all i. He will then select strategy i with probability xi .

Note 2.3. When we formalize this, we will call the probability vector x, a mixed
strategy.
To determine the “best” choice of x, Player 1 analyzes the problem, as follows. . .

2-4

   

1
3/5
0

-1
x1 = 1/5

x1 = 0 x1 = 1
x2 = 1 x2 = 0

Player 2 might do the same thing using probability vector y = (y1 , y2 ) where
P
i yi = 1 and yi ≥ 0 for all i.

   
3

1
3/5
0

-1
y1 = 2/5

y1 = 0 y1 = 1
y2 = 1 y2 = 0

2-5
If Player 1 adopts mixed strategy (x1 , x2 ) and Player 2 adopts mixed strategy
(y1 , y2 ), we obtain an expected payoff of

V = 3x1 y1 + 0(1 − x1 )y1 − x1 (1 − y1 )

+(1 − x1 )(1 − y1 )
= 5x1 y1 − y1 − 2x1 + 1

Suppose Player 1 uses x∗1 = 51 , then

’ “ ’ “
1 1 3
V =5 y1 − y1 − 2 +1=
5 5 5

which doesn’t depend on y ! Similarly, suppose Player 2 uses y1∗ = 25 , then

’ “ ’ “
2 2 3
V = 5x1 − − 2x1 + 1 =
5 5 5
which doesn’t depend on x!
Each player is solving a constrained optimization problem. For Player 1 the problem
is
max{v}
st: +3x1 + 0x2 ≥ v
−1x1 + 1x2 ≥ v
x1 + x2 = 1
xi ≥ 0 ∀i
which can be illustrated as follows:

2-6

   

1
v
0

-1

x1 = 0 x1 = 1
x2 = 1 x2 = 0

This problem is equivalent to

max min{(3x1 + 0x2 ), (−x1 + x2 )}

x

For Player 2 the problem is

min{v}
st: +3y1 − 1y2 ≤ v
+0y1 + 1y2 ≤ v
y1 + y2 = 1
yj ≥ 0 ∀j
which is equivalent to

min max{(3y1 − y2 ), (0y1 + y2 )}

y

We recognize these as dual linear programming problems.

Question 2.4. We now have a way to compute a “spy-proof” mixed strategy for
each player. Modify these two mathematical programming problems to produce
the pure security strategy for each player.

2-7
In general, the players are solving the following pair of dual linear programming
problems:
max{v}
P
st: a x ≥ v ∀j
Pi ij i
i xi = 1
xi ≥ 0 ∀i
and
min{v}
P
st: a y ≤ v ∀i
Pj ij j
i yi = 1
yi ≥ 0 ∀j

Note 2.4. Consider, once again, the example game

" #
3 −1
A=
0 1

If Player 1 (the maximizer) uses mixed strategy (x1 , (1 − x1 )), and if Player 2 (the
minimizer) uses mixed strategy (y1 , (1 − y1 )) we get

E(x, y) = 5x1 y1 − y1 − 2x1 + 1

and letting x∗ = 51 and y ∗ = 25 we get E(x∗ , y) = E(x, y ∗ ) = 53 for any x and y .

These choices for x∗ and y ∗ make the expected value independent of the opposing
strategy. So, if Player 1 becomes a minimizer (or if Player 2 becomes a maximizer)
the resulting mixed strategies would be the same!
Note 2.5. Consider the game
" #
1 3
A=
4 2

By “factoring” the expression for E(x, y), we can write

E(x, y) = x1 y1 + 3x1 (1 − y1 ) + 4(1 − x1 )y + 2(1 − x1 )(1 − y1 )

= −4x1 y1 + x1 + 2y1 + 2
x1 y1 1 1
= −4(x1 y1 − − + )+2+
4 2 8 2
1 1 5
= −4(x1 − )(y1 − ) +
2 4 2
It’s now easy to see that x∗1 = 21 , y1∗ = 1
4 and v = 25 .

2-8
2.1.5 A more formal statement of the problem
‚ ƒ
Suppose we are given a matrix game A(m×n) ≡ aij . Each row of A is a pure
strategy for Player 1. Each column of A is a pure strategy for Player 2. The value
of aij is the payoff from Player 1 to Player 2 (it may be negative).
For Player 1 let
V (A) = max min aij
i j

For Player 2 let

V (A) = min max aij
j i

{Case 1} (Saddle Point Case where V (A) = V (A) = V )

Player 1 can assure himself of getting at least V from Player 2 by playing his
maximin strategy.

{Case 2} (Mixed Strategy Case where V (A) < V (A))

Player 1 uses probability vector
X
x = (x1 , . . . , xm ) xi = 1 xi ≥ 0
i

Player 2 uses probability vector

X
y = (y1 , . . . , yn ) yj = 1 yj ≥ 0
j

If Player 1 uses x and Player 2 uses strategy j , the expected payoff is

X
E(x, j) = xi aij = xAj
i

where Aj is column j from matrix A.

If Player 2 uses y and Player 1 uses strategy i, the expected payoff is
X
E(i, y) = aij yj = Ai y T
j

where Ai is row i from matrix A.

2-9
 Combined, if Player 1 uses x and Player 2 uses y , the expected payoff is
XX
E(x, y) = xi aij yj = xAy T
i j

The players are solving the following pair of dual linear programming prob-
lems:
max{v}
P
st: a x ≥ v ∀j
Pi ij i
i xi = 1
xi ≥ 0 ∀i
and
min{v}
P
st: a y ≤ v ∀i
Pj ij j
i yi = 1
yi ≥ 0 ∀j

The Minimax Theorem (von Neumann, 1928) states that there exists mixed strate-
gies x∗ and y ∗ for Players 1 and 2 which solve each of the above problems with
equal objective function values.

2.1.6 Proof of the minimax theorem

Note 2.6. (From Başar and Olsder [1]) The theory of finite zero-sum games dates
back to Borel in the early 1920’s whose work on the subject was later translated
into English (Borel, 1953). Borel introduced the notion of a conflicting decision
situation that involves more than one decision maker, and the concepts of pure
and mixed strategies, but he did not really develop a complete theory of zero-sum
games. Borel even conjectured that the minimax theorem was false.
It was von Neumann who first came up with a proof of the minimax theorem, and
laid down the foundations of game theory as we know it today (von Neumann 1928,
1937).
The following proof of the minimax theorem does not use the powerful tools
of duality in linear programming problems. It is provided here for historical
purposes.
‚ ƒ
Theorem 2.3. Minimax Theorem Let A = aij be an m × n matrix of real
numbers. Let Ξr denote the set of all r-dimensional probability vectors, that is,
Pr
Ξr = {x ∈ Rr | i=1 xi = 1 and xi ≥ 0}

2-10
We sometimes call Ξr the probability simplex.
Let x ∈ Ξm and y ∈ Ξn . Define
V (A) = max min xAy T
x y

V (A) = min max xAy T

y x

Then V (A) = V (A).

Proof: (By finite induction on m + n.)
The result is clearly true when A is a 1 × 1 matrix (i.e., m + n = 2).
Assume that the theorem is true for all p × q matrices such that p + q < m + n
(i.e., for any submatrix of an m × n matrix). We will now show the result is true
for any m × n matrix.
First note that xAy T , maxx xAy T and miny xAy T are all continuous functions of
(x, y), x and y , respectively. Any continuous, real-valued function on a compact
set has an extermum. Therefore, there exists x0 and y 0 such that
V (A) = min x0 Ay T
y

V (A) = max xAy 0T

x
It is clear that
(1) V (A) ≤ x0 Ay 0T ≤ V (A)
So we only need to show that V (A) ≥ V (A).
Let’s assume that V (A) < V (A). We will show that this produces a contradiction.
From Equation 1, either V (A) < x0 Ay 0T or V (A) > x0 Ay 0T . We’ll assume
V (A) < x0 Ay 0T (the other half of the proof is similar).
Let A be an (m − 1) × n matrix obtained from A by deleting a row. Let A be an
m × (n − 1) matrix obtained from A by deleting a column. We then have, for all
x ∈ Ξm−1 and y ∈ Ξn−1 ,
V (A) = max min x0 Ay T ≤ V (A)
0 x y

V (A) = min max x0 Ay T ≤ V (A)

0y x
V (A) = max min xAy 0T ≥ V (A)
0x y

V (A) = min max xAy 0T ≥ V (A)

0 y x

2-11
We know that V (A) = V (A) and V (A) = V (A). Thus

V (A) = V (A) ≤ V (A)

V (A) ≤ V (A) ≤ V (A)

and

V (A) = V (A) ≥ V (A) ≥ V (A)

V (A) ≥ V (A)

So, if it is really true that V (A) < V (A) then, for all A and A, we have

V (A) > V (A)

V (A) > V (A)

Now, if is true that V (A) > V (A) we will show that we can construct a vector ∆x
such that
min(x0 + ∆x)Ay T > V (A) = max min xAy T
y x y

for some  > 0. This would be clearly false and would yield our contradiction.
To construct ∆x, assume
(2) V (A) > V (A)
For some k there is a column Ak of A such that

x0 Ak > V (A)

This must be true because if x0 Ak ≤ V (A) for all columns Aj , then x0 Ay 0T ≤

V (A) violating Equation 2.
For the above choice of k , let Ak denote the m×(n− 1) matrix obtained by deleting
the k th column from A. From calculus, there must exist x0 ∈ Ξm such that

V (Ak ) = max min xAy 0T

0x y

= min
0
x Ay 0T
0
y

where y 0 ∈ Ξn but with yk0 = 0 (because we deleted the k th column from A).
Now, let ∆x = x0 − x0 6= 0 to get

V (Ak ) = min
0
(x0 + ∆x)Ay 0T > V (A)
y

2-12
 To summarize, by assuming Equation 2, we now have the following:

V (A) = min x0 Ay T
y

V (Ak ) = min
0
(x0 + ∆x)Ay 0T > V (A)
y

Therefore,
min(x0 + ∆x)Ay 0T > V (A) = min x0 Ay 0T
0 y y

for all 0 <  ≤ 1.

In addition, xAk is continuous, and linear in x, so

x0 Ak > V (A)

implies
(x0 + ∆x)Ak > V (A)
for some small  > 0. Let x? = x0 + ∆x for that small . This produces,
š ’ “ ›
? T ? 0T € ? 
min x Ay = min (1 − yk ) min x Ay + yk x Ak
y 0≤yk ≤1 0 y
š ›
? 0T ?
= min min
0
x Ay , x Ak > V (A)
y

which is a contradiction.

2.1.7 The minimax theorem and duality

The following theorem provides a modern proof of the minimax theorem, using
duality:1
Theorem 2.4. Consider the matrix game A with mixed strategies x and y for
Player 1 and Player 2, respectively. Then
1. minimax statement

max min E(x, y) = min max E(x, y)

x y y x

1
This theorem and proof is from my own notebook from a Game Theory course taught at Cornell
in the summer of 1972. The course was taught by Professors William Lucas and Louis Billera. I
believe, but I cannot be sure, that this particular proof is from Professor Billera.

2-13
 2. saddle point statement (mixed strategies) There exists x∗ and y ∗ such that

E(x, y ∗ ) ≤ E(x∗ , y ∗ ) ≤ E(x∗ , y)

for all x and y .

2a. saddle point statement (pure strategies) Let E(i, y) denote the expected
value for the game if Player 1 uses pure strategy i and Player 2 uses mixed
strategy y . Let E(x, j) denote the expected value for the game if Player 1
uses mixed strategy x and Player 2 uses pure strategy j . There exists x∗ and
y ∗ such that
E(i, y ∗ ) ≤ E(x∗ , y ∗ ) ≤ E(x∗ , j)
for all i and j .
3. LP feasibility statement There exists x∗ , y ∗ , and v 0 = v 00 such that
P P
x∗i ≥ v0 ∀ j a y∗ ≤ v 00 ∀ i
Pi aij ∗
Pj ∗ij j
i xi = 1 j yj = 1
x∗i ≥ 0 ∀i yj∗ ≥ 0 ∀j

4. LP duality statement The objective function values are the same for the
following two linear programming problems:

max{v} min{v}
P
P
x∗i st: a y∗ ≤ v ∀i
st: Pi aij ∗
≥ v ∀j Pj ∗ij j
i xi = 1 i yj = 1
x∗i ≥ 0 ∀i yj∗ ≥ 0 ∀j

Proof: We will sketch the proof for the above results by showing that

(4) ⇒ (3) ⇒ (2) ⇒ (1) ⇒ (3) ⇒ (4)

and
(2) ⇔ (2a)
.

{(4) ⇒ (3)} (3) is just a special case of (4).

2-14
{(3) ⇒ (2)} Let 1n denote a column vector of n ones. Then (3) implies that there
exists x∗ , y ∗ , and v 0 = v 00 such that
x∗ A ≥ v 0 1n
x∗ Ay T ≥ v 0 (1n y T ) = v 0 ∀y

and
Ay ∗T ≤ v 00 1m
xAy ∗T ≤ xv 00 1m = v 00 (x1m ) = v 00 ∀x

Hence,
E(x∗ , y) ≥ v 0 = v 00 ≥ E(x, y ∗ ) ∀ x, y
and
E(x∗ , y ∗ ) = v 0 = v 00 = E(x∗ , y ∗ )

{(2) ⇒ (2a)} (2a) is just a special case of (2) using mixed strategies x with xi = 1
and xk = 0 for k 6= i.
{(2a) ⇒ (2)} For each i, consider all convex combinations of vectors x with xi =
1 and xk = 0 for k 6= i. Since E(i, y ∗ ) ≤ v , we must have E(x∗ , y ∗ ) ≤ v .
{(2) ⇒ (1)}

• {Case ≥}
E(x, y ∗ ) ≤ E(x∗ , y) ∀ x, y
∗ ∗
max E(x, y ) ≤ E(x , y) ∀y
x
max E(x, y ∗ ) ≤ min E(x∗ , y)
x y
min max E(x, y) ≤ max E(x, y ∗ ) ≤ min E(x∗ , y) ≤ max min E(x, y)
y x x y x y

• {Case ≤}
min E(x, y) ≤ E(x, y) ∀ x, y
y
” •
max min E(x, y) ≤ max E(x, y) ∀y
x y x
” • h i
max min E(x, y) ≤ min max E(x, y)
x y y x

2-15
 {(1) ⇒ (3)}
” • h i
max min E(x, y) = min max E(x, y)
x y y x

Let f (x) = miny E(x, y). From calculus, there exists x∗ such that
f (x) attains its maximum value at x∗ . Hence
” •
∗
min E(x , y) = max min E(x, y)
y x y

{(3) ⇒ (4)} This is direct from the duality theorem of LP. (See Chapter 13 of
Dantzig’s text.)

Question 2.5. Can the LP problem in section (4) of Theorem 2.4 have alternate
optimal solutions. If so, how does that affect the choice of (x∗ , y ∗ )?2

2.2 Two-Person General-Sum Games

2.2.1 Basic ideas

Two-person general-sum games (sometimes‚ called ƒ

“bi-matrix games”) can be rep-
‚ ƒ
resented by two (m × n) matrices A = aij and B = bij where aij is the
“payoff” to Player 1 and bij is the “payoff” to Player 2. If A = −B then we get a
two-person zero-sum game, A.
Note 2.7. These are non-cooperative games with no side payments.
Definition 2.2. The (pure) strategy (i∗ , j ∗ ) is a Nash equilibrium solution to the
game (A, B) if

ai∗ ,j ∗ ≥ ai,j ∗ ∀i
bi∗ ,j ∗ ≥ bi∗ ,j ∀j

Note 2.8. If both players are placed on their respective Nash equilibrium strategies
(i∗ , j ∗ ), then each player cannot unilaterally move away from that strategy and
improve his payoff.
2
Thanks to Esra E. Aleisa for this question.

2-16
 Question 2.6. Show that if A = −B (zero-sum case), the above definition of a
Nash solution corresponds to our previous definition of a saddle point.
Note 2.9. Not every game has a Nash solution using pure strategies.
Note 2.10. A Nash solution need not be the best solution, or even a reasonable
solution for a game. It’s merely a stable solution against unilateral moves by a
single player. For example, consider the game
" #
(4, 0) (4, 1)
(A, B) =
(5, 3) (3, 2)

This game has two Nash equilibrium strategies, (4, 1) and (5, 3). Note that both
players prefer (5, 3) when compared with (4, 1).
Question 2.7. What is the solution to the following simple modification of the
above game:3 " #
(4, 0) (4, 1)
(A, B) =
(4, 2) (3, 2)

Example 2.1. (Prisoner’s Dilemma) Two suspects in a crime have been picked up
by police and placed in separate rooms. If both confess (C ), each will be sentenced
to 3 years in prison. If only one confesses, he will be set free and the other (who
didn’t confess (N C )) will be sent to prison for 4 years. If neither confesses, they
will both go to prison for 1 year.
This game can be represented in strategic form, as follows:

C NC
C (-3,-3) (0,-4)
NC (-4,0) (-1,-1)

This game has one Nash equilibrium strategy, (−3, −3). When compared with the
other solutions, note that it represents one of the worst outcomes for both players.

2.2.2 Properties of Nash strategies

3
Thanks to Esra E. Aleisa for this question.

2-17
Definition 2.3. The pure strategy pair (i1 , j1 ) weakly dominates (i2 , j2 ) if and
only if
ai1 ,j1 ≥ ai2 ,j2
bi1 ,j1 ≥ bi2 ,j2
and one of the above inequalities is strict.
Definition 2.4. The pure strategy pair (i1 , j1 ) strongly dominates (i2 , j2 ) if and
only if
ai1 ,j1 > ai2 ,j2
bi1 ,j1 > bi2 ,j2

Definition 2.5. (Weiss [3]) The pure strategy pair (i, j) is inadmissible if there
exists some strategy pair (i0 , j0 ) that weakly dominates (i, j).
Definition 2.6. (Weiss [3]) The pure strategy pair (i, j) is admissible if it is not
inadmissible.
Example 2.2. Consider again the game
" #
(4, 0) (4, 1)
(A, B) =
(5, 3) (3, 2)
With Nash equilibrium strategies, (4, 1) and (5, 3). Only (5, 3) is admissible.
Note 2.11. If there exists multiple admissible Nash equilibria, then side-payments
(with collusion) may yield a “better” solution for all players.
Definition 2.7. Two bi-matrix games (A.B) and (C, D) are strategically equiv-
alent if there exists α1 > 0, α2 > 0 and scalars β1 , β2 such that
aij = α1 cij + β1 ∀ i, j
bij = α2 dij + β2 ∀ i, j

Theorem 2.5. If bi-matrix games (A.B) and (C, D) are strategically equivalent
and (i∗ , j ∗ ) is a Nash strategy for (A, B), then (i∗ , j ∗ ) is also a Nash strategy for
(C, D).
Note 2.12. This was used to modify the original matrices for the Prisoners’
Dilemma problem in Example 2.1.

2-18
2.2.3 Nash equilibria using mixed strategies

Sometimes the bi-matrix game (A, B) does not have a Nash strategy using pure
strategies. As before, we can use mixed strategies for such games.
Definition 2.8. The (mixed) strategy (x∗ , y ∗ ) is a Nash equilibrium solution to
the game (A, B) if
x∗ Ay ∗T ≥ xAy ∗T ∀ x ∈ Ξm
x∗ By ∗T ≥ x∗ By T ∀ y ∈ Ξn

where Ξr is the r-dimensional probability simplex.

Question 2.8. Consider the game
" #
(−2, −4) (0, −3)
(A, B) =
(−3, 0) (1, −1)
Can we find mixed strategies (x∗ , y ∗ ) that provide a Nash solution as defined
above?
Theorem 2.6. Every bi-matrix game has at least one Nash equilibrium solution
in mixed strategies.
Proof: (This is the sketch provided by the text for Proposition 33.1; see Chapter 3
for a complete proofs for N ≥ 2 players.)
Consider the sets Ξn and Ξm consisting of the mixed strategies for Player 1 and
Player 2, respectively. Note that Ξn × Ξm is non-empty, convex and compact.
Since the expected payoff functions xAy T and xBy T are linear in (x, y), the result
follows using Brouwer’s fixed point theorem,

2.2.4 Finding Nash mixed strategies

Consider again the game

" #
(−2, −4) (0, −3)
(A, B) =
(−3, 0) (1, −1)
For Player 1
xAy T = −2x1 y1 − 3(1 − x1 )y1 + (1 − x1 )(1 − y1 )
= 2x1 y1 − x1 − 4y1 + 1

2-19
For Player 2

xBy T = −2x1 y1 − 2x1 + y1 − 1

In order for (x∗ , y ∗ ) to be a Nash equilibrium, we must have for all 0 ≤ x1 ≤ 1

(3) x∗ Ay ∗T ≥ xAy ∗T ∀ x ∈ Ξm
(4) x∗ By ∗T ≥ x∗ By T ∀ y ∈ Ξn

For Player 1 this means that we want (x∗ , y ∗ ) so that for all x1

2x∗1 y1∗ − x∗1 − 4y1∗ + 1 ≥ 2x1 y1∗ − x1 − 4y1∗ + 1

2x1∗ y1∗ − x∗1 ≥ 2x1 y1∗ − x1

Let’s try y1∗ = 21 . We get

’ “ ’ “
1 1
2x∗1 − x∗1 ≥ 2x1 − x1
2 2
0 ≥ 0

Therefore, if y ∗ = ( 21 , 21 ) then any x∗ can be chosen and condition (3) will be

satisfied.
Note that only condition (3) and Player 1’s matrix A was used to get Player 2’s
strategy y ∗ .
For Player 2 the same thing happens if we use x1∗ = 1
2 and condition (4). That is,
for all 0 ≤ y1 ≤ 1

−2x∗1 y1∗ − 2x∗1 + y1∗ − 1 ≥ −2x1 y1∗ − 2x1 + y1∗ − 1

−2x1∗ y1∗ + y1∗ ≥ −2x1 y1∗ + y1
’ “ ’ “
1 ∗ ∗ 1 ∗
−2 y + y1 ≥ − 2 y + y1
2 1 2 1
0 ≥ 0

How can we get the values of (x∗ , y ∗ ) that will work? One suggested approach
from (Başar and Olsder [1]) uses the following:

2-20
Theorem 2.7. Any mixed Nash equilibrium solution (x∗ , y ∗ ) in the interior of
Ξm × Ξn must satisfy
n
X
(5) yj∗ (aij − a1j ) = 0 ∀ i 6= 1
j=1
m
X
(6) xi∗ (bij − bi1 ) = 0 ∀ j 6= 1
i=1

Proof: Recall that

m X
X n
E(x, y) = xAy T = xi yj aij
i=1 j=1
Xn X m
= xi yj aij
j=1 i=1

Pm
Since x1 = 1 − i=2 xi , we have
n
"m   m
! #
X X X
T
xAy = xi yj aij + 1 − xi yj a1j
j=1 i=2 i=2
n
" m
#
X X
= yj a1j + yj xi (aij − a1j )
j=1 i=2
 
n
X m
X n
X
= yj a1j + xi yj (aij − a1j )
j=1 i=2 j=1

If (x∗ , y ∗ ) is an interior maximum (or minimum) then

Xn
∂
xAy T = yj (aij − a1j ) = 0 for i = 2, . . . , m
∂xi j=1

Which provide the Equations 5.

The derivation of Equations 6 is similar.
Note 2.13. In the proof we have the equation
 
n
X m
X n
X
xAy T = yj a1j + xi  yj (aij − a1j )
j=1 i=2 j=1

2-21
 Any Nash solution (x∗ , y ∗ ) in the interior of Ξm × Ξn has
n
X
yj∗ (aij − a1j ) = 0 ∀i=
6 1
j=1

So this choice of y ∗ produces

n
X m
X
T
xAy = yj a1j + xi [0]
j=1 i=2

making this expression independent of x.

Note 2.14. Equations 5 and 6 only provide necessary (not sufficient) conditions,
and only characterize solutions on the interior of the probability simplex (i.e., where
every component of x and y are strictly positive).
For our example, these equations produce

y1∗ (a21 − a11 ) + y2∗ (a22 − a12 ) = 0

x∗1 (b12 − b11 ) + x∗2 (b22 − b21 ) = 0

Since x∗2 = 1 − x1∗ and y2∗ = 1 − y1∗ , we get

y1∗ (−3 − (−2)) + (1 − y1∗ )(1 − 0) = 0

−y1∗ + (1 − y1∗ ) = 0
1
y1∗ =
2

x∗1 (−3 − (−4)) + (1 − x∗1 )(−1 − 0) = 0

x1∗ − (1 − x∗1 ) = 0
1
x1∗ =
2
But, in addition, one must check that x∗1 = 1
2 and y1∗ = 1
2 are actually Nash
solutions.

2.2.5 The Lemke-Howson algorithm

Lemke and Howson [2] developed a quadratic programming technique for finding
mixed Nash strategies for two-person general sum games (A, B) in strategic form.
Their method is based on the following fact, provided in their paper:

2-22
Let ek denote a column vector of k ones, and let x and y be row vectors of dimension
m and n, respectively. Let p and q denote scalars. We will also assume that A and
B are matrices, each with m rows and n columns.
A mixed strategy is defined by a pair (x, y) such that

(7) xem = yen = 1, and x ≥ 0, y ≥ 0

with expected payoffs

(8) xAy T and xBy T .
A Nash equilibrium solution is a pair (x̄, ȳ) satisfying (7) such that for all (x, y)
satisfying (7),
(9) xAȳ T ≤ x̄Aȳ T and x̄By T ≤ x̄B ȳ T .
But this implies that

(10) Aȳ T ≤ x̄Aȳ T em and x̄B ≤ x̄B ȳ T eTn .

Conversely, suppose (10) holds for (x̄, ȳ) satisfying (7). Now choose an arbitrary
(x, y) satisfying (7). Multiply the first expression in (10) on the left by x and
second expression in (10) on the right by y T to get (9). Hence, (7) and (10) are,
together, equivalent to (7) and (9).
This serves as the foundation for the proof of the following theorem:
Theorem 2.8. Any mixed strategy (x∗ , y ∗ ) for bi-matrix game (A, B) is a Nash
equilibrium solution if and only if x∗ , y ∗ , p∗ and q ∗ solve problem (LH):

(LH): maxx,y,p,q {xAy T + xBy T − p − q}

st: Ay T ≤ pem
B T xT ≤ qen
xi ≥ 0 ∀i
yj ≥ 0 ∀j
P m
x i = 1
Pi=1
n
j=1 yj = 1

Proof: (⇒)
Every feasible solution (x, y, p, q) to problem (LH) must satisfy the constraints

Ay T ≤ pem
xB ≤ qeTn .

2-23
Multiply both sides of the first constraint on the left by x and multiply the second
constraint on the right by y T . As a result, we see that a feasible (x, y, p, q) must
satisfy

xAy T ≤ p
xBy T ≤ q.

Hence, for any feasible (x, y, p, q). the objective function must satisfy

xAy T + xBy T − p − q ≤ 0.

Suppose (x∗ , y ∗ ) is any Nash solution for (A, B). Let

p∗ = x∗ Ay ∗T
q ∗ = x∗ By ∗T .

Because of (9) and (10), this implies

Ay ∗T ≤ x∗ Ay ∗T em = p∗ em
x∗ B ≤ x∗ By ∗T eTn = q ∗ eTn .

So this choice of (x∗ , y ∗ , p∗ , q ∗ ) is feasible, and results in the objective function

equal to zero. Hence it’s an optimal solution to problem (LH)
(⇐)
Suppose (x̄, ȳ, p̄, q̄) solves problem (LH). From Theorem 2.6, there is at least one
Nash solution (x∗ , y ∗ ). Using the above argument, (x∗ , y ∗ ) must be an optimal
solution to (LH) with an objective function value of zero. Since (x̄, ȳ, p̄, q̄) is an
optimal solution to (LH), we must then have

(11) x̄Aȳ T + x̄B ȳ T − p̄ − q̄ = 0

with (x̄, ȳ, p̄, q̄) satisfying the constraints

(12) Aȳ T ≤ p̄em

(13) x̄B ≤ q̄eTn .

Now multiply (12) on the left by x̄ and multiply (13) on the right by ȳ T to get

(14) x̄Aȳ T ≤ p̄
(15) x̄B ȳ T ≤ q̄.

2-24
 Then (11), (14), and (15) together imply

x̄Aȳ T = p̄
x̄B ȳ T = q̄.

So (12), and (13) can now be rewritten as

(16) Aȳ T ≤ x̄Aȳ T em

(17) x̄B ≤ x̄B ȳ T en .

Choose an arbitrary (x, y) ∈ Ξm × Ξn and, this time, multiply (16) on the left by
x and multiply (17) on the right by y T to get

(18) xAȳ T ≤ x̄Aȳ T

(19) x̄By T ≤ x̄B ȳ T

for all (x, y) ∈ Ξm × Ξn . Hence (x̄, ȳ) is a Nash equilibrium solution.

2.3 BIBLIOGRAPHY

[1] T. Başar and G. Olsder, Dynamic noncooperative game theory, Academic Press
(1982).
[2] C. E. Lemke and J. T. Howson, Jr., Equilibrium points of bimatrix games, SIAM
Journal, Volume 12, Issue 2 (Jun., 1964), pp 413–423.
[3] L. Weiss, Statistical decision theory, McGraw-Hill (1961).

2-25
IE675 Game Theory

Lecture Note Set 3

Wayne F. Bialas1
Monday, April 16, 2001

3 N -PERSON GAMES
3.1 N -Person Games in Strategic Form

3.1.1 Basic ideas

We can extend many of the results of the previous chapter for games with N > 2
players.
Let Mi = {1, . . . , mi } denote the set of mi pure strategies available to Player i.
Let ni ∈ Mi be the strategy actually selected by Player i, and let ani 1 ,n2 ,...,nN be the
payoff to Player i if

Player 1 chooses strategy n1

Player 2 chooses strategy n2
..
.
Player N chooses strategy nN

Definition 3.1. The strategies (n∗1 , . . . , n∗N ) with n∗i ∈ Mi for all i ∈ N form a
Nash equilibrium solution if

an1 ∗ ,n∗ ,...,n∗ ≥ a1n1 ,n∗ ,...,n∗ ∀ ni ∈ M 1

1 2 N 2 N

1
Department of Industrial Engineering, University at Buffalo, 342 Bell Hall, Box 602050, Buffalo,
NY 14260-2050 USA; E-mail: bialas@buffalo.edu; Web: http://www.acsu.buffalo.edu/˜bialas.
Copyright c MMI Wayne F. Bialas. All Rights Reserved. Duplication of this work is prohibited
without written permission. This document produced April 16, 2001 at 1:47 pm.

3-1
 a2n∗ ,n∗ ,...,n∗ ≥ a2n∗ ,n2 ,...,n∗ ∀ n 2 ∈ M2
1 2 N 1 N
..
.
aN
n∗ ,n∗ ,...,n∗ ≥ aN
n∗ ,n∗ ,...,nN ∀ nN ∈ M N
1 2 N 1 2

Definition 3.2. Two N -person games with payoff functions ani 1 ,n2 ,...,nN and
bin1 ,n2 ,...,nN are strategically equivalent if there exists αi > 0 and scalars βi for
i = 1, . . . , n such that

ain1 ,n2 ,...,nN = αi bin1 ,n2 ,...,nN + βi ∀i∈N

3.1.2 Nash solutions with mixed strategies

Definition 3.3. The mixed strategies (y ∗1 , . . . , y ∗N ) with y ∗i ∈ ΞMi for all i ∈ N
form a Nash equilibrium solution if
X X X X
··· yn∗11 yn∗22 · · · yn∗N a1
N n1 ,...,nN
≥ ··· yn1 1 yn∗22 · · · yn∗N a1
N n1 ,...,nN
∀ y 1 ∈ ΞM1
n1 nN n1 nN
X X X X
··· yn∗11 yn∗22 · · · yn∗N a2
N n1 ,...,nN
≥ ··· yn∗11 yn2 2 · · · yn∗N a2
N n1 ,...,nN
∀ y 2 ∈ ΞM2
n1 nN n1 nN
..
.
X X X X
··· yn∗11 yn∗22 · · · yn∗N aN
N n1 ,...,nN
≥ ··· yn∗11 yn∗22 · · · ynNN aN
n1 ,...,nN ∀ y N ∈ ΞMN
n1 nN n1 nN

Note 3.1. Consider the function

X X
ψni i (y 1 , . . . , y n ) = ··· yn1 1 yn2 2 · · · ynNN ain1 ,...,nN
n1 nN
X XX X
− ··· ··· yn1 1 · · · yni−1 y i+1 · · · ynNN ain1 ,...,nN
i−1 ni+1
n1 ni−1 ni+1 nN

This represents the difference between the following two quantities:

1. the expected payoff to Player i if all players adopt mixed strategies (y 1 , . . . , y N ):
X X
··· yn1 1 yn2 2 · · · ynNN ain1 ,...,nN
n1 nN

3-2
 2. the expected payoff to Player i if all players except Player i adopt mixed
strategies (y 1 , . . . , y N ) and Player i uses pure strategy ni :
X X X X
··· ··· yn1 1 · · · yni−1 y i+1 · · · ynNN ani 1 ,...,nN
i−1 ni+1
n1 ni−1 ni+1 nN

Remember that the mixed strategies include the pure strategies. For example,
(0, 1, 0, . . . , 0) is a mixed strategy that implements pure strategy 2.
For example, in a two-player game, for each n1 ∈ M1 we have
h i
ψn1 1 (y 1 , y 2 ) = y11 y12 a111 + y11 y22 a112 + y21 y12 a121 + y21 y22 a22
1
h i
− y12 a1n1 1 + y22 an1 1 2

The first term

y11 y12 a111 + y11 y22 a112 + y21 y12 a121 + y21 y22 a122
is the expected value if Player 1 uses mixed strategy y1 . The second term

y12 an1 1 1 + y22 an1 1 2

is the expected value if Player 1 uses pure strategy n1 . Player 2 uses mixed strategy
y2 in both cases.
The next theorem (Theorem 3.1) will guarantee that every game has at least one
Nash equilibrium in mixed strategies. Its proof depends on things that can go
wrong when ψni i (y 1 , . . . , y n ) < 0. So we will define

cni i (y 1 , . . . , y n ) = min{ψni i (y 1 , . . . , y n ), 0}

The proof of Theorem 3.1 then uses the expression

yni i + cni i
ȳni i = P
1 + j∈Mi cij

Note that the denominator is the sum (taken over ni ) of the terms in the numerator.
If all of the cij vanish, we get
ȳni i = yni i .

Theorem 3.1. Every N -person finite game in normal (strategic) form has a Nash
equilibrium solution using mixed strategies.

3-3
Proof: Define ψni i and cni i , as above. Consider the expression

yni i + cini
(1) ȳni i = P
1 + j∈Mi cij

We will try to find solutions yni i to Equation 1 such that

ȳni i = yni i ∀ ni ∈ Mi and ∀ i = 1, . . . , N

The Brouwer fixed point theorem1 guarantees that at least one such solution exists.
We will show that every solution to Equation 1 is a Nash equilibrium solution and
that every Nash equilibrium solution is a solution to Equation 1.
To show that every Nash equilibrium solution is a solution to Equation 1, note that
if (y ∗1 , . . . , y ∗N ) is a Nash solution then, from the definition of a Nash solution,

ψni i (y 1∗ , . . . , y n∗ ) ≥ 0

which implies
cini (y 1∗ , . . . , y n∗ ) = 0
and this holds for all ni ∈ Mi and all i = 1, . . . , N . Hence, (y 1∗ , . . . , y n∗ ) solves
Equation 1.

Remark: Will show that every solution to Equation 1 is a Nash equi-

librium solution by contradiction. That is, we will assume that a mixed
strategy (y 1 , . . . , y N ) is a solution to Equation 1 but is not a Nash so-
lution. This will lead us to conclude that (y 1 , . . . , y N ) is not a solution
to Equation 1, a contradiction.

Assume (y 1 , . . . , y N ) is a solution to Equation 1 but is not a Nash solution. Then

there exists a i ∈ {1, . . . , N } (say i = 1) with ỹ 1 ∈ ΞM1 such that
X X
··· yn1 1 yn2 2 · · · ynNN ani 1 ,...,nN
n1 nN
X X
< ··· ỹn1 1 yn2 2 · · · ynNN ain1 ,...,nN
n1 nN

1
The Brouwer fixed point theorem states that if S is a compact and convex subset of Rn and if
f : S → S is a continuous function onto S, then there exists at least one x ∈ S such that f (x) = x.

3-4
Rewriting the right hand side,
X X
··· yn1 1 yn2 2 · · · ynNN ain1 ,...,nN
n1 nN
" #
X X X
< ỹn1 1 ··· yn2 2 · · · ynNN ain1 ,...,nN
n1 n2 nN

Now the expression

" #
X X
··· yn2 2 · · · ynNN ain1 ,...,nN
n2 nN

is a function of n1 . Suppose this quantity is maximized when n1 = ñ1 . We then

get,
X X
··· yn1 1 yn2 2 · · · ynNN ani 1 ,...,nN
n1 nN
" #
X X X
< ỹn1 1 ··· yn2 2 · · · ynNN aiñ1 ,...,nN
n1 n2 nN

which yields
X X
(2) ··· yn1 1 yn2 2 · · · ynNN ain1 ,...,nN
n1 nN
X X
(3) < ··· yn2 2 · · · ynNN aiñ1 ,...,nN
n2 nN

Remark: After this point we don’t really use ỹ again. It was just a
device to obtain ñ1 which will produce our contradiction. Remember,
throughout the rest of the proof, the values of (y 1 , . . . , y N ) claim be a
fixed point for Equation 1. If (y 1 , . . . , y N ) is, in fact, not Nash (as was
assumed), then we have just found a player (who we are calling Player
1) who has a pure strategy ñ1 that can beat strategy y 1 when Players
2, . . . , N use mixed strategies (y 2 , . . . , y N ).
Using ñ1 , Player 1 obtains

ψñ1 1 (y 1 , . . . , y n ) < 0

which means that

c1ñ1 (y 1 , . . . , y n ) < 0

3-5
which implies that X
cij < 0
j∈M1

since one of the indices in M1 is ñ1 and the rest of the cij cannot be positive.
Remark: Now the values (y 1 , . . . , y N ) are in trouble. We have deter-
mined that their claim of being “non-Nash” produces a denominator
in Equation 1 that is less than 1. All we need to do is find some pure
strategy (say n̂1 ) for Player 1 with cin̂i (y 1 , . . . , y n ) = 0. If we can,
(y 1 , . . . , y N ) will fail to be a fixed-point for Equation 1, and it will be
y 1 that causes the failure. Let’s see what happens. . .
Recall expression 2:
X X
··· yn1 1 yn2 2 · · · ynNN ain1 ,...,nN
n1 nN

rewritten as " #
X X X
yn1 1 ··· yn2 2 · · · ynNN ani 1 ,...,nN
n1 n2 nN

and consider the term

" #
X X
(4) ··· yn2 2 · · · ynNN ain1 ,...,nN
n2 nN

as a function of n1 There must be some n1 = n̂1 that minimizes expression 4, with

" #
X X X X
··· yn1 1 yn2 2 · · · ynNN ani 1 ,...,nN ≥ ··· yn2 2 · · · ynNN ain̂1 ,n2 ...,nN
n1 nN n2 nN

For that particular strategy we have

ψn̂1 1 (y 1 , . . . , y n ) ≥ 0

which means that

c1n̂1 (y 1 , . . . , y n ) = 0
Therefore, for Player 1, we get

yn̂1 1 + 0
ȳn̂1 1 = > yn̂1 1
1 + [something < 0]

3-6
 Hence, y 1 (which claimed to be a component of the non-Nash solution (y 1 , . . . , y N ))
fails to solve Equation 1. A contradiction.
The following theorem is an extension of a result for N = 2 given in Chapter 2. It
provides necessary conditions for any interior Nash solution for N -person games.
Theorem 3.2. Any mixed Nash equilibrium solution (y ∗1 , . . . , y ∗N ) in the interior
of ΞM1 × · · · × ΞMN must satisfy
XX X
··· yn∗22 yn∗33 · · · yn∗N
N
1
(a1n1 ,n2 ,n3 ...,nN − a1,n 2 ,n3 ...,nN
) = 0 ∀ n1 ∈ M1 − {1}
n2 n3 nN
XX X
··· yn∗11 yn∗33 · · · yn∗N
N
(a2n1 ,n2 ,n3 ...,nN − an2 1 ,1,n3 ...,nN ) = 0 ∀ n2 ∈ M2 − {1}
n1 n3 nN
..
.
XX X
··· yn∗11 yn∗22 · · · yn∗N
N
(aN N
n1 ,n2 ,n3 ...,nN − an1 ,n2 ,n3 ...,1 ) = 0 ∀ nN ∈ MN − {1}
n1 n2 nN −1

Proof: Left to the reader.

Question 3.1. Consider the 3-player game with the following values for

(a1n1 ,n2 ,n3 , a2n1 ,n2 ,n3 , an3 1 ,n2 ,n3 ) :

For n3 = 1 For n3 = 2
n2 = 1 n2 = 2 n2 = 1 n2 = 2
n1 = 1 (1, −1, 0) (0, 1, 0) n1 = 1 (1, 0, 1) (0, 0, 0)
n1 = 2 (2, 0, 0) (0, 0, 1) n1 = 2 (0, 3, 0) (−1, 2, 0)
2 = 3. Use the above method to find an interior Nash solution.
For example a212

3.2 N -Person Games in Extensive Form

3.2.1 An introductory example

We will use an example to illustrate some of the issues associates with games in
extensive form.

3-7
Consider a game with two players described by the following tree diagram:

information set η11

Player 1

L M R

η12 η22 Player 2

action L R L R L R

payoffs (0,1) (2,-1) (-3,-2) (0,-3) (-2,-1) (1,0)

Player 1 goes first and chooses an action among {Left, Middle, Right}. Player 2
then follows by choosing an action among {Left, Right}.
The payoff vectors for each possible combination of actions are shown at each
terminating node of the tree. For example, if Player 1 chooses action u1 = L and
Player 2 chooses action u2 = R then the payoff is (2, −1). So, Player 1 gains 2
while Player 1 loses 1.
Player 2 does not have complete information about the progress of the game. His
nodes are partitioned among two information sets {η21 , η22 }. When Player 2 chooses
his action, he only knows which information set he is in, not which node.
Player 1 could analyze the game as follows:
• If Player 1 chooses u1 = L then Player 2 would respond with u2 = L
resulting in a payoff of (0, 1).
• If Player 1 chooses u1 ∈ {M, R} then the players are really playing the

3-8
 following subgame:

η11
Player 1

L M R

η12 η 22 Player 2

L R L R L R

(0,1) (2,-1) (-3,-2) (0,-3) (-2,-1) (1,0)

which can be expressed in normal form as

L R
M (-3,-2) (0,-3)
R (-2,-1) (1,0)

in which (R, R) is a Nash equilibrium strategy in pure strategies.

So it seems reasonable for the players to use the following strategies:
• For Player 1
– If Player 1 is in information set η11 choose R.
• For Player 2
– If Player 2 is in information set η12 choose L.
– If Player 2 is in information set η22 choose R.

3-9
These strategies can be displayed in our tree diagram as follows:

A pair of pure strategies

for Players 1 and 2
η11
Player 1

L M R

η12 η22 Player 2

L R L R L R

(0,1) (2,-1) (-3,-2) (0,-3) (-2,-1) (1,0)

For games in strategic form, we denote the set of pure strategies for Player i by
Mi = {1, . . . , mi } and let ni ∈ Mi denote the strategy actually selected by Player
i. We will now consider a strategy γ i as a function whose domain is the set of
information sets of Player i and whose range is the collection of possible actions
for Player i. For the strategy shown above

γ 1 (η11 ) = R
(
2 2 L if η 2 = η12
γ (η ) =
R if η 2 = η22
The players’ task is to choose the best strategy from those available. Using the
notation from Section 3.1.1, the set Mi = {1, . . . , mi } now represents the indices
i }, for Player i.
of the possible strategies, {γ1i , . . . , γm i

Notice that if either player attempts to change his strategy unilaterally, he will not
improve his payoff. The above strategy is, in fact, a Nash equilibrium strategy as
we will formally define in the next section.

3-10
There is another Nash equilibrium strategy for this game, namely

An alternate strategy pair

for Players 1 and 2
η11
Player 1

L M R

η12 η22 Player 2

L R L R L R

(0,1) (2,-1) (-3,-2) (0,-3) (-2,-1) (1,0)

γ 1 (η11 ) = L
(
2 2 L if η 2 = η12
γ (η ) =
L if η 2 = η22
There is another Nash equilibrium strategy for this game, namely the strategy pair

3-11
 (γ11 , γ12 ).

An alternate strategy pair

for Players 1 and 2
η11
Player 1

L M R

η12 η22 Player 2

L R L R L R

(0,1) (2,-1) (-3,-2) (0,-3) (-2,-1) (1,0)

But this strategy did not arise from the recursive procedure described in Sec-
tion 3.2.1. But (γ11 , γ12 ) is, indeed, a Nash equilibrium. Neither player can improve
his payoff by a unilateral change in strategy. Oddly, there is no reason for Player
1 to implement this strategy. If Player 1 chooses to go Left, he can only receive
0. But if Player 1 goes Right, Player 2 will go Right, not Left, and Player 1 will
receive a payoff of 1. This example shows that games in extensive form can have
Nash equilibria that will never be considered for implementation,

3.2.2 Basic ideas

Definition 3.4. An N -player game in extensive form is a directed graph with

1. a specific vertex indicating the starting point of the game.
2. N cost functions each assigning a real number to each terminating node of
the graph. The ith cost function represents the gain to Player i if that node
is reached.
3. a partition of the nodes among the N players.
4. a sub-partition of the nodes assigned to Player i into information sets {ηki }.
The number of branches emanating from each node of a given information

3-12
 set is the same, and no node follows another node in the same information
set.
We will use the following notation:
η i information sets for Player i.
ui actual actions for Player i emanating from information sets.
γ i (·) a function whose domain is the set of all information sets {η i }
and whose range is the set of all possible actions {ui }.
The set of γ i (·) is the collection of possible (pure) strategies that Player i could
use. In the parlance of economic decision theory, the γ i are decision rules. In game
theory, we call them (pure) strategies.
For the game illustrated in Section 3.2.1, we can write down all possible strategy
pairs (γ 1 , γ 2 ). The text calls these profiles.
Player 1 has 3 possible pure strategies:

γ 1 (η11 ) = L
γ 1 (η11 ) = M
γ 1 (η11 ) = R

Player 2 has 8 possible pure strategies which can be listed in tabular form, as
follows:
γ12 γ22 γ32 γ42
2
η1 : L R L R
η22 : L L R R

Each strategy pair (γ 1 , γ 2 ), when implemented, results in payoffs to both players

which we will denote by (J 1 (γ 1 , γ 2 ), J 2 (γ 1 , γ 2 )). These payoffs produce a game
in strategic (normal) form where the rows and columns correspond to the possible
pure strategies of Player 1 and Player 2, respectively.

γ12 γ22 γ32 γ42

γ11 (0,1) (2,-1) (0,1) (2,-1)
γ21 (-3,-2) (-3,-2) (0,-3) (0,-3)
γ31 (-2,-1) (-2,-1) (1,0) (1,0)

3-13
 Using Definition 3.1, we have two Nash equilibria, namely

(γ11 , γ12 ) with J(γ11 , γ12 ) = (0, 1)

(γ31 , γ32 ) with J(γ31 , γ32 ) = (1, 0)

This formulation allows us to

• focus on identifying “good” decision rules even for complicated strategies
• analyze games with different information structures
• analyze multistage games with players taking more than one “turn”

3.2.3 The structure of extensive games

The general definition of games in extensive form can produce a variety of different
types of games. This section will discuss some of the approaches to classifying
such games. These classification schemes are based on
1. the topology of the directed graph
2. the information structure of the games
3. the sequencing of the players
This section borrows heavily from Başar and Olsder [1]. We will categorize multi-
stage games, that is, games where the players take multiple turns. This classification
scheme extends to differential games that are played in continuous time. In this
section, however, we will use it to classify multi-stage games in extensive form.
Define the following terms:
ηki information for Player i at stage k .
xk state of the game at stage k . This completely describes the current
status of the game at any point in time.
yki = hik (xk ) is the state measurement equation, where
hik (·) is the state measurement function
yki is the observation of Player i at state k .
uik decision of Player i at stage k .

3-14
The purpose of the function hik is to recognize that the players may not perfect
information regarding the current state of the game. The information available to
Player i at stage k is then

ηki = {y11 , . . . , yk1 ; y12 , . . . , yk2 ; · · · ; y1N , . . . , ykN }

Based on these ideas, games can be classified as

open loop

ηki = {x1 } ∀k∈K

closed loop, perfect state

ηki = {x1 , . . . , xk } ∀k∈K

closed loop, imperfect state

ηki = {y1i , . . . , yki } ∀k∈K

memoryless, perfect state

ηki = {x1 , xk } ∀k∈K

feedback, perfect state

ηki = {xk } ∀k∈K

feedback, imperfect state

ηki = {yki } ∀k∈K

Example 3.1. Princess and the Monster. This game is played in complete
darkness. A princess and a monster know their starting positions in a cave. The
game ends when they bump into each other. Princess is trying to maximize the time
to the final encounter. The monster is trying to minimize the time. (Open Loop)
Example 3.2. Lady in the Lake. This game is played using a circular lake. The
lady is swimming with maximum speed v` . A man (who can’t swim) runs along
the shore of the lake at a maximum speed of vm . The lady wins if she reaches shore
and the man is not there. (Feedback)

3-15
3.3 Structure in extensive form games

I am grateful to Pengfei Yi who provided significant portions of Section 3.3.

The solution of an arbitrary extensive form game may require enumeration. But
under some conditions, the structure of some games will permit a recursive solution
procedure. Many of these results can be found in Başar and Olsder [1].
Definition 3.5. Player i is said to be a predecessor of Player j if Player i is
closer to the initial vertex of the game’s tree than Player j .
Definition 3.6. An extensive form game is nested if each player has access to the
information of his predecessors.
Definition 3.7. (Başar and Olsder [1]) A nested extensive form game is ladder-
nested if the only difference between the information available to any player (say
Player i) and his immediate predecessor (Player (i − 1)) involves only the actions
of Player (i − 1), and only at those nodes corresponding to the branches emanating
from singleton information sets of Player (i − 1).
Note 3.2. Every 2-player nested game is ladder-nested
The following three figures illustrate the distinguishing characteristics among non-
nested, nested, and ladder-nested games.

Not nested
Player 1

Player 2

Player 3

3-16
 Nested
Player 1

Player 2

Player 3

Ladder-nested
Player 1

Player 2

Player 3

The important feature of ladder-nested games is that the tree can be decomposed
in to sub-trees using the singleton information sets as the starting vertices of the
sub-trees. Each sub-tree can then be analyzed as game in strategic form among
those players involved in the sub-tree.

3-17
As an example, consider the following ladder-nested game:

An example
η11
Player 1

L R

Player 2 η12 η22

η13 η23
Player 3

(0,-1,-3) (-1,0,-2) (1,-2,-0) (0,1,-1) (-1,-1,-1) (0,0,-3) (1,-3,0) (0,-2,-2)

This game can be decomposed into two bimatrix games involving Player 2 and
Player 3. Which of these two games are actually played by Player 2 and Player 3
depends on the action (L or R) of Player 1.
If Player 1 chooses u1 = L then Player 2 and Player 3 play the game
Player 3
L R
Player 2 L (−1, −3) (0, −2)
R (−2, 0) (1, −1)
Suppose Player 2 uses a mixed strategy of choosing L with probability 0.5 and R
with probability 0.5. Suppose Player 3 also uses a mixed strategy of choosing L
with probability 0.5 and R with probability 0.5. Then these mixed strategies are a
Nash equilibrium solution for this sub-game with an expected payoff to all three
players of (0, −0.5, −1.5).
If Player 1 chooses u1 = R then Player 2 and Player 3 play the game
Player 3
L R
Player 2 L (−1, −1) (0, −3)
R (−3, 0) (0, −2)

3-18
This subgame has a Nash equilibrium in pure strategies with Player 2 and Player 3
both choosing L. The payoff to all three players in this case is of (−1, −1, −1).
To summarize the solution for all three players we will introduce the concept of a
behavioral strategy:
Definition 3.8. A behavioral strategy (or locally randomized strategy) assigns
for each information set a probability vector to the alternatives emanating from the
information set.
When using a behavioral strategy, a player simply randomizes over the alternatives
from each information set. When using a mixed strategy, a player randomizes his
selection from the possible pure strategies for the entire game.
The following behavioral strategy produces a Nash equilibrium for all three players:

γ 1 (η11 ) = L
(
L with probability 0.5
γ 2 (η12 ) =
R with probability 0.5
(
2 L with probability 1
γ (η22 ) =
R with probability 0
(
L with probability 0.5
γ 3 (η13 ) =
R with probability 0.5
(
3 L with probability 1
γ (η23 ) =
R with probability 0

with an expected payoff of (0, −0.5, −1.5).

Note 3.3. When using a behavioral strategy, a player, at each information set,
must specify a probability distribution over the alternatives for that information set.
It is assumed that the choices of alternatives at different information sets are made
independently. Thus it might be reasonable to call such strategies “uncorrelated”
strategies.
Note 3.4. For an arbitrary game, not all mixed strategies can be represented by
using behavioral strategies. Behavioral strategies are easy to find and represent. We
would like to know when we can use behavioral strategies instead of enumerating
all pure strategies and randomizing among those pure strategies.
Theorem 3.3. Every single-stage, ladder-nested N -person game has at least one
Nash equilibrium using behavioral strategies.

3-19
3.3.1 An example by Kuhn

One can show that every behavioral strategy can be represented as a mixed strat-
egy. But an important question arises when considering mixed strategies vis-à-vis
behavioral strategies: Can a mixed strategy always be represented by a behavioral
strategy?
The following example from Kuhn [2] shows a remarkable result involving behav-
ioral strategies. It shows what can happen if the players do not have a property
called perfect recall. Moreover, the property of perfect recall alone is a necessary
and sufficient condition to obtain a one-to-one mapping between behavioral and
mixed strategies for any game.
In a game with perfect recall, each player remembers everything he knew at
previous moves and all of his choices at these moves.
A zero-sum game involves two players and a deck of cards. A card is dealt to each
player. If the cards are not different, two more cards are dealt until one player has
a higher card than the other.
The holder of the high card receives $1 from his opponent. The player with the
high card can choose to either stop the game or continue.
If the game continues, Player 1 (who forgets whether he has the high or low card)
can choose to leave the cards as they are or trade with his opponent. Another $1 is
then won by the (possibly different) holder of the high card.

3-20
The game can be represented with the following diagram:

Chance

1 1
2 2

Player 1 η11 η12 Player 2

S C C S

Player 1

η12
(1,-1) (-1,1)

T K K T

(0,0) (2,-2) (-2,2) (0,0)

where
S Stop the game
C Continue the game
T Trade cards
K Keep cards

At information set η11 , Player 1 makes the critical decision that causes him to
eventually lose perfect recall at η21 . Moreover, it is Player 1’s own action that
causes this loss of information (as opposed to Player 2 causing the loss). This is
the reason why behavioral strategies fail for Player 1 in this problem.
Define the following pure strategies for Player 1:
( (
S if η 1 = η11 S if η 1 = η11
γ11 (η 1 ) = γ21 (η 1 ) =
T if η 1 = η21 K if η 1 = η21
( (
C if η 1 = η11 C if η 1 = η11
γ31 (η 1 ) = γ41 (η 1 ) =
T if η 1 = η21 K if η 1 = η21

and for Player 2:

γ12 (η12 ) = S γ22 (η12 ) = C

3-21
This results in the following strategic (normal) form game:

γ12 γ22
γ11 (1/2, −1/2) (0, 0)
γ21 (−1/2, 1/2) (0, 0)
γ31 (0, 0) (−1/2, 1/2)
γ41 (0, 0) (1/2, −1/2)

Question 3.2. Show that the mixed strategy for Player 1:

( 21 , 0, 0, 12 )

and the mixed strategy for Player 2:

( 21 , 12 )

result in a Nash equilibrium with expected payoff ( 41 , − 14 ).

Question 3.3. Suppose that Player 1 uses a behavioral strategy (x, y) defined
as follows: Let x ∈ [0, 1] be the probability Player 1 chooses S when he is in
information set η11 , and let y ∈ [0, 1] be the probability Player 1 chooses T when he
is in information set η21 .
Also suppose that Player 2 uses a behavioral strategy (z) where z ∈ [0, 1] is the
probability Player 2 chooses S when he is in information set η12 .
Let E i ((x, y), z) denote the expected payoff to Player i = 1, 2 when using behav-
ioral strategies (x, y) and (z). Show that,

E 1 ((x, y), z) = (x − z)(y − 21 )

and E 1 ((x, y), z) = −E 2 ((x, y), z) for any x, y and z .

Furthermore, consider
max min(x − z)(y − 21 )
x,y z

and show that the every equilibrium solution in behavioral strategies must have
y = 12 where
E 1 ((x, 21 ), z) = −E 2 ((x, 12 ), z) = 0.

Therefore, using only behavioral strategies, the expected payoff will be (0, 0). If
Player 1 is restricted to using only behavioral strategies, he can guarantee, at most,

3-22
an expected gain of 0. But if he randomizes over all of his pure strategies and stays
with that strategy throughout the game, Player 1 can get an expected payoff of 14 .
Any behavioral strategy can be expressed as a mixed strategy. But, without perfect
recall, not all mixed strategies can be implemented using behavioral strategies.
Theorem 3.4. (Kuhn [2]) Perfect recall is a necessary and sufficient condition
for all mixed strategies to be induced by behavioral strategies.
A formal proof of this theorem is in [2]. Here is a brief sketch: We would like to
know under what circumstances there is a 1-1 correspondence between behavioral
and mixed strategies. Suppose a mixed strategy consists of the following mixture
of three pure strategies:
1
choose γa with probability 2
1
choose γb with probability 3
1
choose γc with probability 6

Suppose that strategies γb and γc lead the game to information set η . Suppose that
strategy γa does not go to η . If a player is told he is in information η , he can use
perfect recall to backtrack completely through the game to learn whether strategy
γb or γc was used. Suppose γb (η) = ub and γc (η) = uc . Then if the player is in η ,
he can implement the mixed strategy with the following behavioral strategy:
2
choose ub with probability 3
1
choose uc with probability 3

A game may not have perfect recall, but some strategies could take the game
along paths that, as sub-trees, have the property of perfect recall. Kuhn [2] and
Thompson [4] employ the concept of signaling information sets. In essence, a
signaling information set is that point in the game where a decision by a player
could cause him to lose the property of perfect recall.

3-23
In the following three games, the signaling information sets are marked with (*):

 Signaling Set
Chance

1/2 1/2

Â
Player 1 Player 2

Player 1

 Signaling Set
 Player 1

Player 2

Player 1

3-24
 Â Signaling Set
Player 1

 Â
Player 2 Player 2

Player 2

3.4 Stackelberg solutions

3.4.1 Basic ideas

This early idea in game theory is due to Stackelberg [3]. Its features include:
• hierarchical ordering of the players
• strategy decisions are made and announced sequentially
• one player has the ability to enforce his strategy on others
This approach introduce is notion of a rational reaction of one player to another’s
choice of strategy.
Example 3.3. Consider the bimatrix game

γ12 γ22 γ32

γ11 (0, 1) (−2, −1) (− 32 , − 23 )
γ21 (−1, −2) (−1, 0) (−3, −1)
γ21 (1, 0) (−2, −1) (−2, 12 )

Note that (γ21 , γ22 ) is a Nash solution with value (−1, 0).

3-25
Suppose that Player 1 must “lead” by announcing his strategy, first. Is this an
advantage or disadvantage? Note that,

If Player 1 chooses γ11 Player 2 will respond with γ12

If Player 1 chooses γ21 Player 2 will respond with γ22
If Player 1 chooses γ31 Player 2 will respond with γ32

The best choice for Player 1 is γ11 which will yield a value of (0, 1). For this
game, the Stackelberg solution is an improvement over the Nash solution for both
players.
If we let
γ11 = L γ12 = L
γ21 = M γ22 = M
γ31 = R γ32 = R
we can implement the Stackelberg strategy by playing the following game in
extensive form:

Stackelberg

Player 1

L R
M

Player 2

L M R L M R

L M R
(0,1) (-2,-1) (-3/2,- 2/3) (1,0) (-2,-1) (-2, 1/2)

(-1-2) (-1,0) (-3,-1)

3-26
The Nash solution can be obtained by playing the following game:

Nash

Player 1

L R
M

Player 2

L M R L M R

L M R
(0,1) (-2,-1) (-3/2,- 2/3) (1,0) (-2,-1) (-2, 1/2)

(-1-2) (-1,0) (-3,-1)

There may not be a unique response to the leader’s strategy. Consider the following
example:
γ12 γ22 γ32
γ11 (0, 0) (−1, 0) (−3, −1)
1
γ2 (−2, 1) (−2, 0) (1, 1)
In this case
If Player 1 chooses γ11 Player 2 will respond with γ12 or γ22
If Player 1 chooses γ21 Player 2 will respond with γ12 or γ32

One solution approach uses a minimax philosophy. That is, Player 1 should secure
his profits against the alternative rational reactions of Player 2. If Player 1 chooses
γ11 the least he will obtain is −1, and he chooses γ21 the least he will obtain is −2.
So his (minimax) Stackelberg strategy is γ11 .
Question 3.4. In this situation, one might consider mixed Stackelberg strategies.
How could such strategies be defined, when would they be useful, and how would
they be implemented?

3-27
 Note 3.5. When the follower’s response is not unique, a natural solution approach
would be to side-payments. In other words, Player 1 could provide an incentive
to Player 2 to choose an action in Player 1’s best interest. Let  > 0 be a small
side-payment. Then the players would be playing the Stackelberg game

γ12 γ22 γ32

γ11 (−, ) (−1, 0) (−3, −1)
γ21 (−2, 1) (−2, 0) (1 − , 1 + )

3.4.2 The formalities

Let Γ1 and Γ2 denote the sets of pure strategies for Player 1 and Player 2, respec-
tively. Let J i (γ 1 , γ 2 ) denote the payoff to Player i if Player 1 chooses strategy
γ 1 ∈ Γ1 and Player 2 chooses strategy γ 2 ∈ Γ2 . Let

R2 (γ 1 ) ≡ {ξ ∈ Γ2 | J 2 (γ 1 , ξ) ≥ J 2 (γ 1 , γ 2 ) ∀ γ 2 ∈ Γ2 }

Note that R2 (γ 1 ) ⊆ Γ2 and we call R2 (γ 1 ) the rational reaction of Player 2 to

Player 1’s choice of γ 1 . A Stackelberg strategy can be formally defined as the γ̂ 1
that solves

min J 1 (γ̂ 1 , γ 2 ) = max min J 1 (γ 1 , γ 2 ) = J 1∗

γ 2 ∈R2 (γ̂ 1 ) γ 1 ∈Γ1 γ 2 ∈R2 (γ 1 )

Note 3.6. If R2 (γ 1 ) is a singleton for all γ 1 ∈ Γ1 then there exists a mapping

ψ 2 : Γ1 → Γ2

such that R2 (γ 1 ) = {γ 2 } implies γ 2 = ψ 2 (γ 1 ). In this case, the definition of a

Stackelberg solution can be simplified to the γ̂ 1 that solves

J 1 (γ̂ 1 , ψ 2 (γ 1 )) = max J 1 (γ 1 , ψ 2 (γ 1 ))
γ 1 ∈Γ1

It is easy to prove the following:

Theorem 3.5. Every two-person finite game has a Stackelberg solution for the
leader.
Note 3.7. From the follower’s point of view, his choice of strategy in a Stackelberg
game is always optimal (i.e., the best he can do).

3-28
 Question 3.5. Let J 1∗ (defined as above) denote the Stackelberg value for the
1 denote any Nash equilibrium solution value for the
leader Player 1, and let JN
1?
same player. What is the relationship (bigger, smaller, etc.) between J 1∗ and JN
What additional conditions (if any) do you need to place on the game to guarantee
that relationship?

3.5 BIBLIOGRAPHY

[1] T. Başar and G. Olsder, Dynamic noncooperative game theory, Academic Press
(1982).
[2] H.W. Kuhn, Extensive games and the problem of information, Annals of Math-
ematics Studies, 28, 1953.
[3] H. von Stackelberg, Marktform und gleichgewicht, Springer, Vienna, 1934.
[4] G. L. Thompson Signaling strategies om n-person games, Annals of Mathe-
matics Studies, 28, 1953.

3-29
IE675 Game Theory

Lecture Note Set 4

Wayne F. Bialas1
Friday, March 30, 2001

4 UTILITY THEORY
4.1 Introduction

This section is really independent of the field of game theory, and it introduces
concepts that pervade a variety of academic fields. It addresses the issue of quan-
tifying the seemingly nonquantifiable. These include attributes such as quality of
life and aesthetics. Much of this discussion has been borrowed from Keeney and
Raiffa [1]. Other important references include Luce and Raiffa [2], Savage [4], and
von Neumann and Morgenstern [5].
The basic problem of assessing value can be posed as follows: A decision maker
must choose among several alternatives, say W1 , W2 , . . . , Wn , where each will
result in a consequence discernible in terms of a single attribute, say X . The
decision maker does not know with certainty which consequence will result from
each of the variety of alternatives. We would like to be able to quantify (in some
way) our preferences for each alternative.
The literature on utility theory is extensive, both theoretical and experimental. It
has been the subject of significant criticism and refinement. We will only present
the fundamental ideas here.

4.2 The basic theory

Definition 4.1. Given any two outcomes A and B we write A Ÿ B if A is

preferable to B . We will write A ' B if A 6Ÿ B and B 6Ÿ A.
1
Department of Industrial Engineering, University at Buffalo, 342 Bell Hall, Box 602050, Buffalo,
NY 14260-2050 USA; E-mail: bialas@buffalo.edu; Web: http://www.acsu.buffalo.edu/˜bialas.
Copyright c MMI Wayne F. Bialas. All Rights Reserved. Duplication of this work is prohibited
without written permission. This document produced March 30, 2001 at 2:31 pm.

4-1
4.2.1 Axioms

The relations Ÿ and ' must satisfy the following axioms:

1. Given any two outcomes A and B , exactly one of the following must hold:
(a) A Ÿ B
(b) B Ÿ A
(c) A ' B
2. A ' A for all A
3. A ' B implies B ' A
4. A ' B and B ' C implies A ' C
5. A Ÿ B and B Ÿ C implies A Ÿ C
6. A Ÿ B and B ' C implies A Ÿ C
7. A ' B and B Ÿ C implies A Ÿ C

4.2.2 What results from the axioms

The axioms provide that ' is an equivalence relation and Ÿ produces a weak
partial ordering of the outcomes.
Now assume that
A1 ≺ A2 ≺ · · · ≺ An
Suppose that the decision maker is indifferent to the following two possibilities:

Certainty option: Receive Ai with probability 1

(
Receive An with probability πi
Risky option:
Receive A1 with probability (1 − πi )

If the decision maker is consistent, then πn = 1 and π1 = 0, and furthermore

π1 < π2 < · · · < πn

Hence, the π ’s provide a numerical ranking for the A’s.

4-2
Suppose that the decision maker is asked express his preference for probability
distributions over the Ai . That is, consider mixtures, p0 and p00 , of the Ai where
Pn
p0i ≥ 0 0
i=1 pi = 1
Pn
p00i ≥ 0 00
i=1 pi = 1

Using the π ’s, we can consider the question of which is better, p0 or p00 , by computing
the following “scores”:
n
X
π̄ 0 = p0i πi
i=1
n
X
π̄ 00 = p00i πi
i=1

We claim that the choice of p0 versus p00 should be based on the relative magnitudes
of π̄ 0 and π̄ 00 .
Note 4.1. Suppose we have two outcomes A and B with the probability of getting
each equal to p and (1 − p), respectively. Denote the lottery between A and B by

Ap ⊕ B(1 − p)

Note that this is not expected value, since A and B are not real numbers.
Suppose we choose p0 . This implies that we obtain Ai with probability p0i and this
is indifferent to obtaining
An πi ⊕ A1 (1 − πi )
with probability pi0 . Now, sum over all i and consider the quantities
n
X n
X
An πi p0i ⊕ A1 (1 − πi )p0i
i=1 i=1
n
  n
!
X X
' An πi pi0 ⊕ A1 1 − πi pi0
i=1 i=1
' An π̄ 0 ⊕ A1 (1 − π̄ 0 )

So if π̄ 0 > π̄ 00 then

An π̄ 0 ⊕ A1 (1 − π̄ 0 ) Ÿ An π̄ 00 ⊕ A1 (1 − π̄ 00 )

4-3
This leads directly to the following. . .
Theorem 4.1. If A Ÿ C Ÿ B and

pA ⊕ (1 − p)B ' C

then 0 < p < 1 and p is unique.

Proof: See Owen [3].
Theorem 4.2. There exists a real-valued function u(·) such that
1. (Monotonicity) u(A) > u(B) if and only if A Ÿ B .
2. (Consistency) u(pA ⊕ (1 − p)B) = pu(A) + (1 − p)u(B)
3. the function u(·) is unique up to a linear transformation. In other
words, if u and v are utility functions for the same outcomes then
v(A) = αu(A) + β for some α and β .
Proof: See Owen [3].
Consider a lottery (L) which yields outcomes {Ai }ni=1 with probabilities {pi }ni=1 .
Then let
à = A1 p1 ⊕ A2 p2 ⊕ · · · ⊕ An pn
Because of the properties of utility functions, we have
n
X
E[(u(Ã)] = pi u(Ai )
i=1

Consider  ‘
u−1 E[(u(Ã)]
This is an outcome that represents lottery (L)
Suppose we have two utility functions u1 and u2 with the property that
 ‘  ‘
u1−1 E[(u1 (Ã)] ' u2−1 E[(u2 (Ã)] ∀ Ã

Then u1 and u2 will imply the same preference rankings for any outcomes. If this
is true, we write u1 ∼ u2 . Note that some texts (such as [1]) say that u1 and u2 are
strategically equivalent. We won’t use that definition, here, because this term has
been used for another property of strategic games.

4-4
4.3 Certainty equivalents

Definition 4.2. A certainty equivalent of lottery (L) is an outcome  such that

the decision maker is indifferent between (L) and the certain outcome Â.
In other words, if  is a certainty equivalent of (L)

u(Â) = E[u(Ã)]
 ‘
 ' u−1 E[u(Ã)]

You will also see the terms cash equivalent and lottery selling price in the literature.
Example 4.1. Suppose outcomes are measured in terms of real numbers, say
A = x. For any a and b > 0

u(x) = a + bx ∼ x

Suppose the decision maker has a lottery described by the probability density f (x)
then Z
E[x̃] = xf (x) dx

Note that
u(x̂) = E[u(x̃)] = E[a + bx̃] = a + bE[x̃]
Taking u−1 of both sides shows that x̂ = E[x̃].
Hence, if the utility function is linear, the certainty equivalent for any lottery is the
expected consequence of that lottery.
Question 4.1. Suppose u(x) = a − be−cx ∼ −e−cx where b > 0. Suppose the
decision maker is considering a 50-50 lottery yielding either x1 or x2 . So
x1 + x2
E[x̃] =
2
Find the solution to u(x̂) = E[u(x̃)] to obtaining the certainty equivalent for this
lottery. In other words, solve
−(e−cx1 + e−cx2 )
−e−cx̂ =
2

Question 4.2. This is a continuation of Question 4.1. If u(x) = −e−cx and x̂ is

the certainty equivalent for the lottery x̃, show that x̂+x0 is the certainty equivalent
for the lottery x g
+ x0 .

4-5
4.4 BIBLIOGRAPHY

[1] R.L. Keeney and H. Raiffa, Decisions with multiple objective, Wiley (1976).
[2] R.D. Luce and H. Raiffa, Games and decisions, Wiley (1957).
[3] G. Owen, Games theory, Academic Press (1982).
[4] L.J. Savage, The foundations of statistics, Dover (1972).
[5] J. von Neumann and O. Morgenstern, Theory of games and economic behavior,
Princeton Univ. Press (1947).

4-6
IE675 Game Theory

Lecture Note Set 5

Wayne F. Bialas12
Friday, March 30, 2001

5 STATIC COOPERATIVE GAMES

5.1 Some introductory examples

Consider a game with three players 1, 2 and 3. Let N = {1, 2, 3} Suppose that the
players can freely form coalitions. In this case, the possible coalition structures
would be
{{1}, {2}, {3}} {{1, 2, 3}}
{{1, 2}, {3}} {{1, 3}, {2}} {{2, 3}, {1}}
Once the players form their coalition(s), they inform a referee who pays each
coalition an amount depending on its membership. To do this, the referee uses the
function v : 2N → R. Coalition S receives v(S). This is a game in characteristic
function form and v is called the characteristic function.
For simple games, we often specify the characteristic function without using brack-
ets and commas. For example,

v(12) ≡ v({1, 2}) = 100

The function v may actually be based on another game or an underlying decision-

making problem.
1
Department of Industrial Engineering, University at Buffalo, 342 Bell Hall, Box 602050, Buffalo,
NY 14260-2050 USA; E-mail: bialas@buffalo.edu; Web: http://www.acsu.buffalo.edu/˜bialas.
Copyright c MMI Wayne F. Bialas. All Rights Reserved. Duplication of this work is prohibited
without written permission. This document produced March 30, 2001 at 2:26 pm.
2
Much of the material for this section has been cultivated from the lecture notes of Louis J. Billera
and William F. Lucas. The errors and omissions are mine.

5-1
 An important issue is the division of the game’s proceeds among the players. We call
the vector (x1 , x2 , . . . , xN ) of these payoffs an imputation. In many situations, the
outcome of the game can be expressed solely in terms of the resulting imputation.
Example 5.1. Here is a three-person, constant sum game:

v(123) = 100
v(12) = v(13) = v(23) = 100
v(1) = v(2) = v(3) = 0

How much will be given to each player? Consider solutions such as

(x1 , x2 , x3 ) = ( 100 100 100

3 , 3 , 3 )
(x1 , x2 , x3 ) = (50, 50, 0)

Example 5.2. This game is similar to Example 5.1.

v(123) = 100
v(12) = v(13) = 100
v(23) = v(1) = v(2) = v(3) = 0

Player 1 has veto power but if Player 2 and Player 3 form a coalition, they can force
Player 1 to get nothing from the game. Consider this imputation as a solution:

(x1 , x2 , x3 ) = ( 200 50 50
3 , 3 , 3 )

5.2 Cooperative games with transferable utility

Cooperative TU (transferable utility) games have the following ingredients:

1. a characteristic function v(S) that gives a value to each subset S ⊂ N of
players
2. payoff vectors called imputation of the form (x1 , x2 , . . . , xn ) which repre-
sents a realizable distribution of wealth

5-2
 3. a preference relation over the set of imputations
4. solution concepts
Global: stable sets
solutions outside of the stable set can be blocked by some
coalition, and nothing in the stable set can be blocked by
another member of the stable set.
Local: bargaining sets
any objection to an element of a bargaining set has a counter-
objection.
Single point: Shapley value
Definition 5.1. A TU game in characteristic function form is a pair (N, v)
where N = {1, . . . , n} is the set of players and v : 2N → R is the characteristic
function.
Note 5.1. We often assume either that the game is
superadditive: v(S ∪ T ) ≥ v(S) + v(T ) for all S, T ⊆ N , such that S ∩ T = Ø
or that the game is
cohesive: v(N ) ≥ v(S) for all S ⊆ N
We define the set of imputations as
Pn
A(v) = {x | i=1 xi = v(N ) and xi ≥ v({i}) ∀ i ∈ N } ⊂ RN

If S ⊆ N , S = 6 Ø and x, y ∈ A(v) then we say that x dominates y via S ,

(x domS y ) if and only if
1. xi > yi for all i ∈ S
P
2. i∈S xi ≤ v(S)
If x dominates y via S , we write x domS y .
If x domS y for some S ⊆ N then we say that x dominates y and write x dom y .
For x ∈ A(v), we define the dominion of x via S as

DomS x ≡ {y ∈ A(v) | x domS y}

5-3
For any B ⊆ A(v) we define
[
DomS B ≡ DomS y
y∈B

and [
Dom B ≡ DomT B
T ⊆N

We say that K ⊂ A(v) is a stable set if

1. K ∩ Dom K = Ø
2. K ∪ Dom K = A(v)
In other words, K = A(v) − Dom K
The core is defined as
P
C ≡ {x ∈ A(v) | i∈S xi ≥ v(S) ∀ S ⊂ N }

Note 5.2. If the game is cohesive, the core is the set of undominated imputations.
Theorem 5.1. The core of a cooperative TU game (N, v) has the following
properties:
1. The core C is an intersection of half spaces.
2. If stable sets Kα exist, then C ⊂ ∩α Kα
3. (∩α Kα ) ∩ Dom C = Ø
Note 5.3. For some games (e.g., constant sum games) the core is empty.
As an example consider the following constant sum game with N = 3:

v(123) = 1
v(12) = v(13) = v(23) = 1
v(1) = v(2) = v(3) = 0

The set of imputations is

A(v) = {x = (x1 , x2 , x3 ) | x1 + x2 + x3 = 1 and xi ≥ 0 for i = 1, 2, 3}

5-4
This set can be illustrated as a subset in R3 as follows:

The set of
x2
imputations
(0,1,0)

x1
(1,0,0)

(0,0,1)

x3

or alternatively, using barycentric coordinates

The set of imputations

using barycentric coordinates
x2 = 1

x = (x1 ,x2 ,x3 )

x3
0
=

=0
x1

x3 = 1 x2 = 0 x1 = 1

5-5
For an interior point x we get

Dom{1,2} x = A(v) ∩ {y | y1 < x1 and y2 < x2 }

The set of
x2
imputations
Dom{1.2}x
(0,1,0)

x1
(1,0,0)

(0,0,1)

x3

x2

Dom{1.2}x

x3 x1

5-6
And for all two-player coalitions we obtain

x2

Dom{1.3}x

x
Dom{1.2}x

x3 x1
Dom{2.3}x

Question 5.1. Prove that

(1) DomN A(v) = Ø

(2) Dom{i} A(v) = Ø ∀i
(3) C = Ø

Note that (1) and (2) are general statements, while (3) is true for this particular
game.
Now consider the set

K = {( 21 , 21 , 0), ( 12 , 0, 21 ), (0, 12 , 12 )}

5-7
and note that the sets Dom{1,2} ( 12 , 21 , 0), Dom{1,3} ( 21 , 0, 21 ), and Dom{2,3} (0, 21 , 12 )
can be illustrated as follows:

x2

(1/2, 1/2,0)

x3 x1

Dom{1.2} (1/2,1/2,0)

x2

Dom{1.3} (1/2,0, 1/2)

x3 x1
(1/2,0,1/2)

5-8
 x2

(0,1/2,1/2)

x3 x1
Dom{2.3} (0,1/2,1/2)

We will let you verify that

1. K ∩ Dom K = Ø
2. K ∪ Dom K = A(v)
so that K is a stable set.
Question 5.2. There are more stable sets (an uncountable collection). Find them,
and show that, for this example,

∩α Kα = Ø
∪α Kα = A(v)

Now, let’s look at the veto game:

v(123) = 1
v(12) = v(13) = 1
v(23) = v(1) = v(2) = v(3) = 0

5-9
This game has a core at (1, 0, 0) as shown in the following diagram:

x2

Dom{1,3}x

x
Dom{1.2}x

x3 x1

Core 3-
(1,0,0)

Question 5.3. Verify that any continuous curve from C to the surface x2 + x3 = 1
with a Lipshitz condition of 30◦ or less is a stable set.

A stable set
x2

x3 x1

Core 3- (1,0,0)

5-10
 Note that

∩α Kα = C
∪α Kα = A(v)

5.3 Nomenclature

Much of this section is from Willick [13].

5.3.1 Coalition structures

A coalition structure is any partition of the player set into coalitions Let N =
{1, 2, . . . , n} denote the set of n players.
Definition 5.2. A coalition structure, P , is a partition of N into non-empty
sets such that P = {R1 , R2 , . . . , RM } where Ri ∩ Rj = Ø for all i6=j and
∪Mi=1 Ri = N .

5.3.2 Partition function form

Let P0 ≡ {{1}, {2}, . . . , {n}} denote the singleton coalition structure. The coali-
tion containing all players N is called the grand coalition. The coalition structure
PN ≡ {N } is called the grand coalition structure.
In partition function form games, the value of a coalition, S , can depend on the
coalition arrangement of players in N − S (See Lucas and Thrall [11]).
Definition 5.3. The game (N, v) is a n-person game in partition function form
if v(S, P) is a real valued function which assigns a number to each coalition S ∈ P
for every coalition structure P .

5.3.3 Superadditivity

A game is superadditive if v(S ∪ T ) ≥ v(S) + v(T ) for all S, T ⊆ N such that

S ∩ T = Ø.
Most non-superadditive games can be mapped into superadditive games. The
following reason is often given: Suppose there exist disjoint coalitions S and T
such that
v(S ∪ T ) < v(S) + v(T )

5-11
Then S and T could secretly form the coalition S ∪ T and collect the value
v(S) + v(T ). The coalition S ∪ T would then divide the amount among its total
membership.
Definition 5.4. The game v is said to be the superadditive cover of the game u
if for all P ⊆ N , X
v(P ) = max ∗
u(R)
PP ∗
R∈PP

where PP∗ be a partition of P .

Note 5.4. PP∗ is a coalition structure restricted to members of P
Note 5.5. A problem with using a superadditive cover is that it requires the
ingredient of secrecy. Yet all of the players are assumed to have perfect information.
It also requires a dynamic implementation process. The players need to first decide
on their secret alliance, then collect the payoffs as S and T individually, and finally
divide the proceeds as S ∪ T . But characteristic function form games are assumed
to be static.
Example 5.3. Consider this three-person game:

u(123) = 1
u(12) = u(13) = u(23) = 1
u(2) = u(3) = 0
u(1) = 5

Note that (N, u) is not superadditive. The superadditive cover of (N, u) is

v(123) = 6
v(12) = 5
v(13) = 5
v(23) = 1
v(2) = v(3) = 0
v(1) = 5

We can often relax the requirement of superadditivty and assume only that the
grand coalition obtains a value at least as great as the sum of the values of any
partition of the grand coalition. Such games are called cohesive.

5-12
 Definition 5.5. A characteristic function game is said to be cohesive if
X
v(N ) = max v(P ).
P
P ∈P

There are important examples of cohesive games. For instance, we will see later
that some models of hierarchical organizations produce cohesive games that are
not superadditive.

5.3.4 Essential games

Definition 5.6. A game is essential if

X
v({i}) < v(N )
i∈N

A game is inessential if X
v({i}) ≥ v(N )
i∈N

P P
Note 5.6. If i∈N v(i) > v(N ) then A(v) = Ø. If i∈N v(i) = v(N ) then
A(v) = {(v(1), v(2), . . . , v(n))}

5.3.5 Constant sum games

Definition 5.7. A game is a constant sum game if

v(S) + v(N − S) = v(N ) ∀S ⊂ N

5.3.6 Strategic equivalence

Definition 5.8. Two games (N, v1 ) and (N, v2 ) are strategically equivalent if
and only if there exist c > 0 and scalars a1 , . . . , an such that
X
v1 (S) = cv2 (S) + ai ∀M ⊆ N
i∈S

Properties of strategic equivalence:

5-13
 1. It’s a linear transformation
2. It’s an equivalence relation
• reflexive
• symmetric
• transitive
Hence it partitions the set of games into equivalence classes.
3. It’s an isomorphism with respect to dom on A(v2 ) → A(v1 ). So, strategic
equivalence preserves important solution concepts.

5.3.7 Normalization

Definition 5.9. A game (N, v) is in (0, 1) normal form if

v(N ) = 1
v({i}) = 0 ∀i ∈ N

The set A(v) for a game in (0, 1) normal form is a “probability simplex.”
Suppose a game is in (0, 1) normal form and superadditive, then 0 ≤ v(S) ≤ 1 for
all S ⊆ N .
An essential game (N, u) can be converted to (0, 1) normal form by using
P
u(S) − i∈S u({i})
v(S) = P
u(N ) − i∈N u({i})

Note that the denominator must be positive for any essential game (N, u).
Note 5.7. For N = 3 a game in (0, 1) normal form can be completely defined by
specifying (v(12), v(13), v(23)).
Question 5.4. Show that C 6= Ø for any three-person (0, 1) normal form game
with
v(12) + v(13) + v(23) < 2

5-14
Here’s an example:2

v(12) + v(13) + v(23) < 2

x2
Dom{1,3}C
x1+x2=v(12)

x2+x3=v(23)

Core C
Dom{1,2}C

x3 x1

Dom{2,3}C
x1+x3=v(13)

Show that stable sets are of the following form:

v(12) + v(13) + v(23) < 2

x2

Stable set

x3 x1

2
My thanks to Ling Wang for her suggestions on this section.

5-15
 Produce similar diagrams for the case v(12) + v(13) + v(23) > 2.
Is C = Ø for v(12) + v(13) + v(23) = 2?

5.4 Garbage game

There are N players. Each player produces one bag of garbage and dumps it in
another’s yard. The payoff for any player is

−1 × (the number of bags in his yard)

We get

v(N ) = −n
v(M ) = |M | − n for |M | < n

We have C = Ø when n > 2. To show this, note that x ∈ C implies

X
xi ≥ v(N − {j}) = −1 ∀j ∈ N
i∈N −{j}

Summing over all j ∈ N ,

X
(n − 1) xi ≥ −n
i∈N
(n − 1)v(N ) ≥ −n
(n − 1)(−n) ≥ −n
n ≤ 2

5.5 Pollution game

There are n factories around a lake.

Input water is free, but if the lake is dirty, a factory may need to pay to clean the
water. If k factories pollute the lake, the cost to a factory to clean the incoming
water is kc.
Output water is dirty, but a factory might pay to treat the effluent at a cost of b.
Assume 0 < c < b < nc.

5-16
 If a coalition M forms, all of it’s members could agree to pollute with a payoff of
|M |(−nc). Or, all of it’s members could agree to clean the water with a payoff of
|M |(−(n − |M |)c) − |M |b. Hence,

v(M ) = max {{|M |(−nc)}, {|M |(−(n − |M |)c) − |M |b}} for M ⊂ N

n o
2
v(N ) = max {−n c}, {−nb}

Question 5.5. Show that C =

6 Ø and x = (−b, . . . , −b) ∈ C .

5.6 Balanced sets and the core

The presentation in this section is based on Owen [9]

The core C can be defined as the set of all (x1 , . . . , xn ) ∈ A(V ) ⊂ Rn such that
X
xi ≡ x(N ) = v(N ) and
i∈N
X
xi ≡ x(S) ≥ v(S) ∀ S ∈ 2N
i∈S

If we further define an additive set function x(·) as any function such that

x : 2N → R
X
x(S) = x({i})
i∈S

we get the following, equivalent, definition of a core:

Definition 5.10. The core C of a game (N, v) is the set of additive a : 2N → R
such that

a(N ) = v(N )
a≥v

The second condition means that a(S) ≥ v(S) for all S ⊂ N .

We would like to characterize those characteristic functions v for which the core is
nonempty.

5-17
Note that C =
6 Ø if and only if the linear programming problem
P
min z = ni=1 xi
(4) P
st: i∈S xi ≥ v(S) ∀S ⊂N

has a minimum z ∗ ≤ v(N ).

Consider the dual to the above linear programming problem (4)
X
max yS v(S) = q
S⊂N
X
(5) st: yS = 1 ∀i∈N
S3i
yS ≥ 0 ∀S ⊂N

Both the linear program (4) and its dual (5) are always feasible. So

min z = max q

by the duality theorem. Hence, the core is nonempty if and only if

max q ≤ v(N )

This leads to the following:

Theorem 5.2. A necessary and sufficient condition for the game (N, v) to have
C=
6 Ø is that for every nonnegative vector (yS )S⊂N satisfying
X
yS = 1 ∀i
S3i

we have X
yS v(S) ≤ v(N )
S⊂N

To make this more useful, we introduce the concept of a balanced collection of

coalitions.
Definition 5.11. B ⊂ 2N is balanced if there exists yS ∈ R with yS > 0 for all
S ∈ B such that X
yS = 1 ∀ i ∈ N
S3i

5-18
y is called the balancing vector (or weight vector) for B . The individual yS ’s are
called balancing coefficients.
Example 5.4. Suppose N = {1, 2, 3}
B = {{1}, {2}, {3}} is a balanced collection with y{1} = 1, y{2} = 1, and
y{3} = 1.
B = {{1, 2}, {3}} is a balanced collection with y{1,2} = 1 and y{3} = 1.
B = {{1, 2}, {1, 3}, {2, 3}} is a balanced collection with y{1,2} = 21 , y{1,3} = 12 ,
and y{2,3} = 21 .
Theorem 5.3. The union of balanced collections is balanced.
Lemma 5.1. Let B1 and B2 be balanced collections such that B1 ⊂ B2 but
B1 6= B2 . Then there exists a balanced collection B3 6= B2 such that B3 ∪B1 = B2 .
The above lemma leads us to define the following:
Definition 5.12. A minimal balanced collection is a balanced collection for
which no proper subcollection is balanced.
Theorem 5.4. Any balanced collection can be written as the union of minimal
balanced collections.
Theorem 5.5. Any balanced collection has a unique balancing vector if and only
if it is a minimal balanced collection.
Theorem 5.6. Each extreme point of the polyhedron for the dual linear program-
ming problem (5) is the balancing vector of a minimal balanced collection.
Corollary 5.1. A minimal balanced collection has at most n sets.
The result is the following theorem:
Theorem 5.7. (Shapley-Bondareva) The core is nonempty if and only if for every
minimal balanced collection B with balancing coefficients (yS )S∈B we have
X
v(N ) ≥ yS v(S)
s∈B

Example 5.5. Let N = {1, 2, 3}. Besides the partitions, such as {{1, 2}, {3}},
there is only one other minimal balanced collection, namely,

B = {{1, 2}, {1, 3}, {2, 3}}

5-19
 with  ‘
1 1 1
y= 2, 2, 2

Therefore a three-person game (N, v) has a nonempty core if and only if

1
2 v({1, 2}) + 12 v({1, 3}) + 12 v({2, 3}) ≤ v(N )
v({1, 2}) + v({1, 3}) + v({2, 3}) ≤ 2v(N )

Question 5.6. Use the above result and reconsider Question 5.4 on page 5-14.
Question 5.7. Suppose we are given v(S) for all S 6= N . What is the smallest
value of v(N ) such that C 6= Ø?

5.7 The Shapley value

Much of this section is from Yang [14].

Definition 5.13. A carrier for a game (N, v) is a coalition T ⊆ N such that
v(S) ≤ v(S ∩ T ) for any S ⊆ N .
This definition is slightly different from the one given by Shapley [10]. Shapley
uses v(S) = v(S ∩ T ) instead of v(S) ≤ v(S ∩ T ). However, when the game
(N, v) is superadditive, the definitions are equivalent.
A carrier is a group of players with the ability to benefit the coalitions they join. A
coalition can remove any of its members who do not belong to the carrier and get
the same, or greater value.
Let Π(N ) denote the set of all permutations on N , that is, the set of all one-to-one
mappings from N onto itself.
Definition 5.14. (Owen [9]) Let (N, v) be an n-person game, and let π ∈ Π(N ).
Then, the game (N, πv) is defined as the game (N, u), such that

u({π(i1 ), π(i2 ), . . . , π(i|S| )}) = v(S)

for any coalition S = {i1 , i2 , . . . , i|S| }.

Definition 5.15. (Friedman [3]) Let (N, v) be an n-person game. The marginal
value, cS (v), for coalition S ⊆ N is given by

c{i} (v) ≡ v({i})

5-20
 for all i ∈ N , and X
cS (v) ≡ v(S) − cL (v)
L⊂S

for all S ⊆ N with |S| ≥ 2.

The marginal value of S can also be computed by using the formula
X
cS (v) = (−1)|S|−1 v(L).
L⊆S

5.7.1 The Shapley axioms

Let φ(v) = (φ1 (v), φ2 (v), . . . , φn (v)) be an n-dimensional vector satisfying the
following three axioms:
Axiom S 1. (Symmetry) For each π ∈ Π(N ), φπ(i) (πv) = φi (v).
Axiom S 2. (Rationing) For each carrier C of (N, v)
X
φi (v) = v(C).
i∈C

Axiom S 3. (Law of Aggregation) For any two games (N, v) and (N, w)

φ(v + w) = φ(v) + φ(w).

Theorem 5.8. (Shapley [10]) For any superadditive game (N, v) there is a
unique vector of values φ(v) = (φ1 (v), . . . , φn (v)) satisfying the above three
axioms. Moreover, for each player i this value is given by
X 1
(6) φi (v) = cS (v)
S⊆N
|S|
S3i

Note 5.8. The Shapley value can be equivalently written [9] as

X ’ (|T | − 1)!(n − |T |)! “
(7) φi (v) = [v(T ) − v(T − {i})]
T ⊆N
n!
T 3i

5-21
 This formula can be interpreted as follows: Suppose n players arrive one after the
other into a room that will eventually contain the grand coalition. Consider all
possible sequencing arrangements of the n players. Suppose that any sequence can
1
occur with probability n! . If Player i arrives and finds coalition T − {i} already
in the room, his contribution to the coalition is v(T ) − v(T − {i}). The Shapley
value is the expected value of the contribution of Player i.

5.8 A generalization of the Shapley value

Suppose we introduce the concept of taxation (or resource redistribution) and relax
just one of the axioms. Yang [14], has shown that the Shapley value and the
egalitarian value
v(N )
φ0i (v) = ∀i ∈ N
n
are then the extremes of an entire family of values for all cohesive (not necessarily
superadditive) games.
Axiom Y 1. (Symmetry) For each π ∈ Π(N ), ψπ(i) (πv) = ψi (v).
Axiom Y 2. (Rationing) For each carrier C of (N, v)
X |C|
ψi (v) = g(C)v(C) with n ≤ g(C) ≤ 1.
i∈C

Axiom Y 3. (Law of Aggregation) For any two games (N, v) and (N, w)

ψ(v + w) = ψ(v) + ψ(w).

Note that Yang only modifies the second axiom. The function g(C) is called the
rationing function. Ithcan bei any real-valued function defined on attributes of the
carrier C with range |C|n , 1 . If the game (N, v) is superadditive, then g(C) = 1
yields Shapley’s original axioms.
A particular choice of the rationing function g(C) produces a convex combination
between the egalitarian value and the Shapley value. Let N =‚ {1, .ƒ. . , n} and let
c ≡ |C| for C ⊆ N . Given the value of the parameter r ∈ n1 , 1 consider the
real-valued function
(n − c)r + (c − 1)
g(C) ≡ g(c, r) = .
n−1

5-22
The function g(C) specifies the distribution of revenue among the players of a
game.
Note that this function can be rewritten as
’ “
n−c
g(c, r) = 1 − (1 − r) .
n−1
For games with a large number of players,

lim g(c, r) = r ∈ (0, 1]

n→∞

so that (1 − r) can be regarded as a “tax rate” on carriers.

Using this form of the rationing function results in the following:3
Theorem 5.9. Let (N, ‚
v)ƒbe a cohesive n-person cooperative transferable utility
game. For each r ∈ n1 , 1 , there exists a unique value, ψi,r (v), for each Player i
satisfying the three axioms. Moreover, this unique value is given by
v(N )
(8) ψi,r (v) = (1 − p)φi (v) + p ∀i ∈ N
n
n − nr
where p = ∈ (0, 1).
n−1
Note that the rationing function can be written4 in terms of p ∈ (0, 1) as
c
g(c, p) = p + (1 − p)
n

Example 5.6. Consider a two-person game with

v({1}) = 1, v({2}) = 0, v({1, 2}) = 2

Player 2 can contribute 1 to a coalition with Player 1. But, Player 1 can get 1 on
his own, leaving Player 2 with nothing.
The family of values is ’ “
1 3
ψr (v) = + r, − r
2 2
 ‘
1 3 1
for 2 ≤ r ≤ 1. The Shapley value (with r = 1) is 2, 2 .
3
We are indebted to an anonymous reviewer for the simplified version of this theorem.
4
Once again, our thanks to the same anonymous reviewer for this observation.

5-23
Example 5.7. Consider a modification of the above game in Example (5.6) with

v({1}) = 1, v({2}) = 0, v({1, 2}) = 1

In this case, Player 2 is a dummy player.

The family of values is
ψr (v) = (r, 1 − r)
1
for 2 ≤ r ≤ 1. The Shapley value (with r = 1) is (1, 0).
Example 5.8. This solution approach can be applied to a problem suggested by
Nowak and Radzik [8]. Consider a three-person game where

v({1}) = v({2}) = 0, v({3}) = 1,

v({1, 2}) = 3.5, v({1, 3}) = v({2, 3}) = 0,
v({1, 2, 3}) = 5.

The Shapley value for this game is

 ‘
25 25 10
φ(v) = 12 , 12 , 12 .

Note that the Shapley value will not necessarily satisfy the condition of individual
rationality
φi (v) ≥ v({i})
when the characteristic function v is not superadditive. That is the case here since
φ3 (v) < v({3}).
The solidarity value (Nowak and Radzik [8]) ξ(v) of this game is
 ‘
16 16 13
ξ(v) = 9, 9, 9

and is in the core of (N, v).

‚1 ƒ
For every r ∈ n, 1 , the general form of the family of values is
’ “
35 + 15r 35 + 15r 50 − 30r
ψr (v) = , , .
24 24 24

5-24
The diagram in the following figure shows the relationship between the family of
values and the core.

(0,0,5)

B
CORE

A
(5,0,0) (0,5,0)

Note that, in the diagram,

 ‘
25 25 10
A = 12 , 12 , 12 (the Shapley value)
 ‘
5 5 5
B = 3, 3, 3 .

Neither of these extreme values of the family of values is in the core for this game.
7
However, those solutions for 15 ≤ r ≤ 13 15 are elements of the core.

Example 5.9. Nowak and Radzik [8] offer the following example related to
social welfare and income redistribution: Players 1, 2, and 3 are brothers living
together. Players 1 and 2 can make a profit of one unit, that is, v({1, 2}) = 1.
Player 3 is a disabled person and can contribute nothing to any coalition. Therefore,
v({1, 2, 3}) = 1. Also, v({1, 3}) = v({2, 3}) = 0 and v({i}) = 0 for every Player
i.
Shapley value of this game is
 ‘
1 1
φ(v) = 2, 2, 0

and for the family of values, we get

’ “
1+r 1+r 1−r
ψr (v) = , ,
4 4 2
‚ ƒ
for r ∈ 13 , 1 . Every r yields a solution satisfying individual rationality, but, in
this case, ψr (v) belongs to the core only when it equals the Shapley value (r = 1).

5-25
 For this particular game, the solidarity value is a member of the family when
r = 95 . Nowak and Radzik propose this single value as a “better” solution for the
game (N, v) than its Shapley value. They suggest that it could be used to include
subjective social or psychological aspects in a cooperative game.
Question 5.8. Suppose game (N, v) has core C 6= Ø. Let

1
F ≡ {ψr (v) | ≤ r ≤ 1}
n
denote the set of Yang’s values when using rationing function g(c, r). Under what
conditions will C ∩ F 6= Ø?

5.9 BIBLIOGRAPHY

[1] Robert J. Aumann, The core of a cooperative game without side payments,
Transactions of the American Mathematical Society, Vol. 98, No. 3. (Mar.,
1961), pp. 539-552. (JSTOR)
[2] Louis J. Billera, Some theorems on the core of an n-person game without
side-payments, SIAM Journal on Applied Mathematics, Vol. 18, No. 3. (May.,
1970), pp. 567-579. (JSTOR)
[3] Friedman J.W., Oligopoly and the theory of games. North-Holland Publishing
Co., New York (1977).
[4] Friedman J.W., Game theory with applications to economics. Oxford Univer-
sity Press , New York (1986).
[5] Iñarra E and Usategui J.M. The Shapley value and average convex games.
International Journal of Game Theory, Vol. 22. (1993) pp. 13–29.
[6] Maschler M., The power of a coalition. Management Science, Vol. 10, (1963),
pp. 8–29.
[7] Monderer D., Samet D. and Shapley L.S., Weighted values and the core.
International Journal of Game Theory, Vol. 21 (1992) 27–39
[8] Nowak A.S. and Radzik T., A solidarity value for n-person transferable utility
games. International Journal of Game Theory, Vol. 23, (1994). pp. 43–48.
[9] Owen G., Game theory. Academic Press Inc. San Diego (1982)
[10] Shapley L.S., A value for n-person games. Annals of Mathematics Studies,
Vol. 28, (1951). 307–317

5-26
[11] W. F. Lucas and R. M. Thrall, n-person Games in Partition Form, Naval
Research Logistics Quarterly, Vol. 10 (1963), pp. 281–298.
[12] J. von Neumann and O. Morgenstern, Theory of games and economic behavior,
Princeton Univ. Press (1947).
[13] W. Willick, A power index for cooperative games with applications to hier-
archical organizations, Ph.D. Thesis, SUNY at Buffalo (1995).
[14] C. H. Yang, A family of values for n-person cooperative transferable utility
games, M.S. Thesis, University at Buffalo (1997).

5-27
IE675 Game Theory

Lecture Note Set 6

Wayne F. Bialas1
Tuesday, April 3, 2001

6 DYNAMIC COOPERATIVE GAMES

6.1 Some introductory examples

Consider the following hierarchical game:

G\QDPL
FRRSHUDWLY  JDPH

Federal Government

State Government

Local Government

In this particular example,

1
Department of Industrial Engineering, University at Buffalo, 342 Bell Hall, Box 602050, Buffalo,
NY 14260-2050 USA; E-mail: bialas@buffalo.edu; Web: http://www.acsu.buffalo.edu/˜bialas.
Copyright c MMI Wayne F. Bialas. All Rights Reserved. Duplication of this work is prohibited
without written permission. This document produced April 3, 2001 at 1:34 pm.

6-1
 1. The system has interacting players within a hierarchical structure
2. Each player executes his polices after, and with full knowledge of, the deci-
sions of predecessors.
3. Players might form coalitions in order to improve their payoff.
What do we mean by (3)?
For examples (without coalitions) see Cassidy, et al. [12] and Charnes, et al. [13].
Without coalitions:

Payoff to Federal government = gF (F, S, L)

Payoff to State government = gS (F, S, L)
Payoff to Local government = gL (F, S, L)

A coalition structure of {{F, S}, {L}} would result in the players maximizing the
following objective functions:

Payoff to Federal government = gF (F, S, L) + gS (F, S, L)

Payoff to State government = gF (F, S, L) + gS (F, S, L)
Payoff to Local government = gL (F, S, L)

The order of the play remains the same. Only the objectives change.

6-2
Here is a two-player game of the same type, but written in extensive form:

$ H[DPSO
ZLW WZ  SOD\HUV

Player F

f p
Player S

a b a b

(3,2) (2,1) (7,0) (2,1)

where
f Full funding
p Partial funding

a Project a
b Project b

The Stackelberg solution to this game is (f, a) with a payoff of (3, 1). However, if
the players cooperated, and utility was transferable, they could get 7 with strategy
(p, a).
The key element causing this effect is preemption. A dynamic, cooperative model
is needed.
Chew [14] showed that even linear models can exhibit this behavior and he devel-
oped a dynamic cooperative game model.

6-3
 OHYH
/  SUREOHP
x2

c1

S1
c2
x̂2

x1

x1 = ψ ( xˆ2 )

5DWLRQD UHDFWLRQV
x2

c1

S1
c2

S2 = Ψc1 x ( S1 ) x*
x1

6-4
 Solution properties
x2 c1 + c2
c1
c2

S1

x*
x1

6.1.1 Issues

See Bialas and Karwan [4] for details.

1. alternate optimal solutions
2. nonconvex feasible region
Note 6.1. The cause of inadmissible solutions is not the fault of the optimizers,
but, rather, the sequential and preemptive nature of the decision process (i.e., the
“friction of space and time”).

6.2 Multilevel mathematical programming

The non-cooperative model in this section will serve as the foundation for our
cooperative dynamic model. See also Bialas and Karwan [6].
Note 6.2. Some history: Sequential optimization problems arise frequently in
many fields, including economics, operations research, statistics and control theory.
The origin of this class of problems is difficult to trace since it is woven into the
fabric of many scientific disciplines.
For the field of operations research, this topic arose as an extension to linear
programming (see, for example, Bracken and McGill [8] Cassidy, et al. [12],

6-5
Charnes, et al. [13])
In particular, Bracken, et al. [8, 7, 9] define a two-level problem where the con-
straints contain an optimization problem. However, the feasible region of the lower
level planner does not depend on the decision variables to the upper-level planner.
Removing this restriction, Candler and Norton [10] named this class of problems
“multilevel programming.” A number of researchers mathematically characterized
the geometry of this problem and developed solution algorithms (see, for example,
[1, 4, 5, 15]).
For a more complete bibliography, see Vicente and Calamai [18].
Let the decision variable space (Euclidean n-space), Rn 3 x = (x1 , x2 , . . . , xn ),
be partitioned among r levels,

Rnk 3 xk = (xk1 , xk2 , . . . , xn

k
k
) for k = 1, . . . , r,
P
where rk=1 nk = n. Denote the maximization of a function f (x) over Rn by
varying only xk ∈ Rnk given fixed xk+1 , xk+2 , . . . , xr in Rnk+1 × Rnk+2 ×· · ·× Rnr
by
(1) max{f (x) : (xk | xk+1 , xk+2 , . . . , xr )}.

Note 6.3. The value of expression (1) is a function of x1 , x2 , . . . , xk−1 .

Let the full set of system constraints for all levels be denoted by S . Then the
problem at the lowest level of the hierarchy, level one, is given by
(
1 max {f1 (x) : (x1 | x2 , . . . , xr )}
(P )
st: x ∈ S 1 = S

Note 6.4. The problem for the level-one decision maker P 1 is simply a (traditional)
mathematical programming problem dependent on the given values of x2 , . . . , xr .
That is, P 1 is a parametric programming problem.
The feasible region, S = S 1 , is defined as the level-one feasible region. The
solutions to P 1 in Rn1 for each fixed x2 , x3 , . . . , xr form a set,

S 2 = {x̂ ∈ S 1 : f1 (x̂) = max{f1 (x) : (x1 | x̂2 , x̂3 , . . . , x̂r )}},

called the level-two feasible region over which f2 (x) is then maximized by varying
x2 for fixed x3 , x4 , . . . , xr .

6-6
 Thus the problem at level two is given by
(
2 max {f2 (x) : (x2 | x3 , x4 , . . . , xr )}
(P )
st: x ∈ S 2

In general, the level-k feasible region is defined as

S k = {x̂ ∈ S k−1 | fk−1 (x̂) = max{fk−1 (x) : (xk−1 | x̂k , . . . , x̂r )}},

Note that x̂k−1 is a function of x̂k , . . . , x̂r . Furthermore, the problem at each level
can be written as
(
k max {fk (x) : (xk | xk+1 , . . . , xr )}
(P )
st: x ∈ S k

which is a function of xk+1 , . . . , xr , and

(P r ) : maxr fr (x)
x∈S

defines the entire problem. This establishes a collection of nested mathematical

programming problems {P 1 , . . . , P r }.
Question 6.1. P k depends on given xk+1 , . . . , xr , and only xk is varied. But
f k (x) is defined over all x1 , . . . , xr . Where are the variables x1 , . . . , xk−1 in
problem P k ?
Note that the objective at level k , fk (x), is defined over the decision space of all
levels. Thus, the level-k planner may have his objective function determined, in
part, by variables controlled at other levels. However, by controlling xk , after
decisions from levels k + 1 to r have been made, level k may influence the policies
at level k − 1 and hence all lower levels to improve his own objective function.

6.2.1 A more general definition

See also Bialas and Karwan [5].

Let the vector x ∈ RN be partitioned as (xa , xb ). Then we can define the following
set function over the collection of closed and bounded regions S ⊂ RN :

Ψf (S) = {x̂ ∈ S : f (x̂) = max{f (x) | (xa | x̂b )}}

6-7
 as the set of rational reactions of f over S . This set is also sometimes called
the inducible region. If for a fixed x̂b there exists a unique x̂a which maximizes
f (xa , x̂b ) over all (xa , x̂b ) ∈ S , then there induced a mapping
x̂a = ψf (x̂b )
which provides the rational reaction for each x̂b , and we can then write
Ψf (S) = S ∩ {(xa , xb ) : xa = ψf (xb )}
So if S = S 1 is the level-one feasible region, the level-two feasible region is
S 2 = Ψf1 (S 1 )
and the level-k feasible region is
S k = Ψfk−1 (S k−1 )

Note 6.5. Even if S 1 is convex, S k = Ψfk−1 (S k−1 ) for k ≥ 2 are typically

non-convex sets.

6.2.2 The two-level linear resource control problem

The two-level linear resource control problem is the multilevel programming prob-
lem of the form
max c2 x
st: x ∈ S 2
where
S 2 = {x̂ ∈ S 1 : c1 x̂ = max{c1 x : (x1 | x̂2 )}}
and
S 1 = S = {x : A1 x1 + A2 x2 ≤ b, x ≥ 0}
Here, level 2 controls x2 which, in turn, varies the resource space of level one by
restricting A1 x1 ≤ b − A2 x2 .
The nested optimization problem can be written as:


 max {c2 x = c21 x1 + c22 x2 : (x2 )}




 where x1 solves


(P 2 )  max {c1 x = c11 x1 + c12 x2 : (x1 | x2 )}

 

 1

 (P ) st: A1 x1 + A2 x2 ≤ b

 
 x≥0

6-8
 Question 6.2. Suppose someone gives you a proposed solution x∗ to problem
P 2 . Develop an “easy” way to test that x∗ is, in fact, the solution to P 2 .
Question 6.3. What is the solution to P 2 if c1 = c2 . What happens if c1 is
substituted with αc1 + (1 − α)c2 for some 0 ≤ α ≤ 1?

6.2.3 The two-level linear price control problem

The two-level linear price control problem is another special case of the general
multilevel programming problem. In this problem, level two controls the cost
coefficients of level one:


 max {c2 x = c21 x1 + c22 x2 : (x2 )}

 2 2 2

 st: A x ≤ b



 1
where x solves
(P 2 ) 

  2 t 1 1 2


  max {(x ) x : (x | x )}

 (P 1 ) st: A1 x1 ≤ b1

 
  x1 ≥ 0

In this problem, level two controls the cost coefficients of level one.

6.3 Properties of S 2

Theorem 6.1. Suppose S 1 = {x : Ax = b, x ≥ 0} is bounded. Let

S 2 = {x̂ = (x̂1 , x̂2 ) ∈ S 1 : c1 x̂1 = max{c1 x1 : (x1 | x̂2 )}}

then the following hold:

(i) S 2 ⊆ S 1
P
(ii) Let {yt }`t=1 be any ` points of S 1 , such that x = t λt=1
` y ∈ S2
t
P
with λt ≥ 0 and t λt = 1. Then λt > 0 implies yt ∈ S 2 .
Proof: See Bialas and Karwan [4].
Note 6.6. The following results are due to Wen [19] (Chapter 2).
• a set S 2 with the above property is called a shaving of S 1
• shavings of shavings are shavings.
• shavings can be decomposed into convex sets that are shavings

6-9
 • a convex set is always a shaving of itself.
• a relationship between shavings and the Kuhn-Tucker conditions for linear
programming problems.
Definition 6.1. Let S ⊆ Rn . A set σ(S) ⊆ S is a shaving of S if and only if for
P`
any y1 , y2 , . . . , y` ∈ S , and λ1 ≥ 0, λ2 ≥ 0, . . . , λ` ≥ 0 such that t=1 λt = 1
P`
and t=1 λt yt = x ∈ σ(S), the statement {λi > 0} implies yi ∈ σ(S).
The following figures illustrate the notion of a shaving.

Figure A Figure B
σ(S) is a shaving τ(T) is not a shaving

σ(S) y1
τ(T)

y1
S
x x T

y2 y2

The red region, σ(S), in Figure A is a shaving of the set S . However in Figure B,
the point λ1 y1 + λ2 y2 = x ∈ τ (T ) with λ1 + λ2 = 1, λ1 > 0, λ2 > 0. But y1 and
y2 do not belong to τ (T ). Hence τ (T ) is not a shaving.
Theorem 6.2. Suppose T = σ(S) is a shaving of S and τ (T ) is a shaving of
T . Let τ ◦ σ denote the composition of the functions τ and σ . Then τ ◦ σ(S) is a
shaving of S .
P`
Proof: Let y1 , y2 , . . . , y` ∈ S , and λ1 ≥ 0, λ2 ≥ 0, . . . , λ` ≥ 0 such that t=1 λt =
P
1 and `t=1 λt yt = x ∈ σ(S) = T .
Suppose λi > 0. Since σ(S) is a shaving of S then yi ∈ σ(S) = T . Since τ (T )
is a shaving of T , yi ∈ T , and λi > 0 then yi ∈ τ (T ). Therefore yi ∈ τ (σ(S)) so
τ ◦ σ(S) is a shaving of S .
It is easy to prove the following theorem:
Theorem 6.3. If S is a convex set, the σ(S) = S is a shaving of S .
Theorem 6.4. Let S ⊆ RN . Let σ(S) be a shaving of S . If x is an extreme point
of σ(S), then x is an extreme point of S .

6-10
 Proof: See Bialas and Karwan [4].
Corollary 6.1. An optimal solution to the two-level linear resource control
problem (if one exists) occurs at an extreme point of the constraint set of all
variables (S 1 ).
Proof: See Bialas and Karwan [4].
These results were generalized to n-levels by Wen [19]. Using Theorems 6.2 and
6.4, if fk is linear and S 1 is a bounded convex polyhedron then the extreme points
of
S k = Ψk−1 Ψk−2 · · · Ψ2 Ψ1 (S 1 )
are extreme points of S 1 . This justifies the use of extreme point search procedures
to finding the solution to the n-level linear resource control problem.

6.4 Cooperative Stackelberg games

This section is based on Chew [14], Bialas and Chew [3], and Bialas [2].

6.4.1 An Illustration

Consider a game with three players, named 1, 2 and 3, each of whom controls an
unlimited quantity of a commodity, with a different commodity for each player.
Their task is to fill a container of unit capacity with amounts of their respective
commodities, never exceeding the capacity of the container. The task of filling will
be performed in a sequential fashion, with player 3 (the player at the “top” of the
hierarchy) taking his turn first. A player cannot remove a commodity placed in the
container by a previous player.
At the end of the sequence, a referee pays each player one dollar (or fraction,
thereof) for each unit of his respective commodity which has been placed in the
container. It is easy to see that, since player 3 has preemptive control over the
container, he will fill it completely with his commodity, and collect one dollar.
Suppose, however, that the rules are slightly changed so that, in addition, player 3
could collect five dollars for each unit of player one’s commodity which is placed
in the container. Since player 2 does not receive any benefit from player one’s
commodity, player 2 would fill the container with his own commodity on his turn,
if given the opportunity. This is the rational reaction of player 2. For this reason,
player 3 has no choice but to fill the container with his commodity and collect only
one dollar.

6-11
6.4.2 Coalition Formation

In the previous example, there are six dollars available to the three players. Divided
equally, each of the three players could improve their payoffs. However, because
of the sequential and independent nature of the decisions, such a solution cannot
be attained.
The solution to the above problem is, thus, not Pareto optimal (see Chew [14]).
However, as suggested by the example, the formation of a coalition among subsets
of the players could provide a means to achieve Pareto optimality. The members
of each coalition act for the benefit of the coalition as a whole. The question
immediately raised are:
• which coalitions will tend to form,
• are the coalitions enforceable, and
• what will be the resulting distribution of wealth to each of the players?
The game in partition function form (see Lucas and Thrall [16] and Shenoy [17])
provides a framework for answering these questions in this Stackelberg setting.
Definition 6.2. An abstract game is a pair (X, dom) where X is a set whose
members are called outcomes and dom is a binary relation on X called domina-
tion.
Let G = {1, 2, . . . , n} denote the set of n players. Let P = {R1 , R2 , . . . , RM }
denote a coalition structure or partition of G into nonempty coalitions, where
Ri ∩ Rj = Ø for all i 6= j and ∪i=1M R = G.
i

Let P0 ≡ {{1}, {2}, . . . , {n}} denote the coalition structure where no coalitions
have formed and let PG ≡ {G} denote the grand coalition.
Consider P = {R1 , R2 , . . . , RM }, an arbitrary coalition structure. Assume that
utility is additive and transferable. As a result of the coalition formation, the
objective function of each player in coalition Rj becomes,
X
fR0 j (x) = fi (x).
i∈Rj

Although the sequence of the players’ decisions has not changed, their objective
functions have. Let R(i) denote the unique coalition Rj ∈ P such that player
0
i ∈ Rj . Instead of maximizing fi (x), player i will now be maximizing fR(i) (x).
Let x̂(P) denote the solution to the resulting n-level optimization problem.

6-12
 Definition 6.3. Suppose that S 1 is compact and x̂(P) is unique. The value of (or
payoff to) coalition Rj ∈ P , denoted by v(Rj , P), is given by
X
v(Rj , P) ≡ fi (x̂(P)).
i∈Rj

Note 6.7. The function v need not be superadditive. Hence, one must be careful
when applying some of the traditional game theory results which require superad-
ditivity to this class of problems.
Definition 6.4. A solution configuration is a pair (r, P), where r is an n-
dimensional vector (called an imputation) whose elements ri (i = 1, . . . , n) rep-
resent the payoff to each player i under coalition structure P .
Definition 6.5. A solution configuration (r, P) is a feasible solution configura-
P
tion if and only if i∈R ri ≤ v(R, P) for all R ∈ P .
Let Θ denote the set of all solution configurations which are feasible for the
hierarchical decision-making problem under consideration. We can then define the
binary relation dom, as follows:
Definition 6.6. Let (r, Pr ), (s, Ps ) ∈ Θ. Then (r, Pr ) dominates (s, Ps ) denoted
by (r, Pr )dom(s, Ps ), if and only if there exists an nonempty R ∈ P , such that

(2) ri > si for all i∈R and

X
(3) ri ≤ v(R, Pr ).
i∈R

Condition (2) implies that each decision maker in R prefers coalition structure Pr
to coalition structure Ps . Condition (3) ensures that R is a feasible coalition in Pr .
That is, R must not demand more for the imputation r than its value v(R, Pr ).
Definition 6.7. The core, C , of an abstract game is the set of undominated,
feasible solution configurations.
When the core is nonempty, each of its elements represents an enforceable solution
configuration within the hierarchy.

6.4.3 Results

6-13
 We have now defined a model of the formation of coalitions among players in a
Stackelberg game. Perfect information is assumed among the players, and coali-
tions are allowed to form freely. No matter which coalitions form, the order of the
players’ actions remains the same. Each coalition earns the combined proceeds that
each individual coalition member would have received in the original Stackelberg
game. Therefore, a player’s rational decision may now be altered because he is
acting for the joint benefit of the members of his coalition.
Using the above model, several results can be obtained regarding the formation
of coalitions among the players. First, the distribution of wealth to any feasible
coalition cannot exceed the value of the grand coalition. This is provided by the
following lemma:
Lemma 6.1. If solution configuration (z, P) ∈ Θ then
n
X n
X
zi ≤ fi (x̂(PG )) = v(G, PG ) ≡ V ∗ .
i=1 i=1

Pn
Theorem 6.5. If (z, P) ∈ C 6= Ø then i=1 zi = V ∗.
It is also possible to construct a simple sufficient condition for the core to be empty.
This is provided in Theorem 6.6.
Theorem 6.6. The abstract game (Θ, dom) has C = Ø if there exists coalition
structures P1 , P2 , . . . , Pm and coalitions Rj ∈ Pj (j = 1, . . . , m) with Rj ∩ Rk =
Ø for all j =
6 k such that
m
X
(4) v(Rj , Pj ) > V ∗ .
j=1

Finally, we can easily show that, in any 2-person game of this type, the core is
always nonempty.
Theorem 6.7. If n = 2 then C =
6 Ø.

6.4.4 Examples and Computations

We will expand on the illustration given in Section 6.4.1. Let cij represent the re-
ward to player i if the commodity controlled by player j is placed in the container.
Let C represent the matrix [cij ] and let x be an n-dimensional vector with xj repre-
Pn
senting the amount of commodity j placed in the container. Note that j=1 xj ≤ 1

6-14
and xj ≥ 0 for j = 1, . . . , n. For the illustration provided in Section 6.4.1,
 
1 0 0
 
C =  0 1 0 .
5 0 1

Note that CxT is a vector whose components represent the earnings to each player.
Chew [14] provides a simple procedure to solve this game. The algorithm requires
c11 > 0.
Step 0: Initialize i=1 and j=1. Go to Step 1.
Step 1: If i = n, stop. The solution is x̂j = 1 and x̂k = 0 for k 6= j . If i 6= n,
then go to Step 2.
Step 2: Set i = i + 1. If cii > cij , then set j = i. Go to Step 1.
If no ties occur in Step 2 (i.e., cii 6= cij ) then it can be shown that the above
algorithm solves the problem (see Chew [14]).
Example 6.1. Consider the three player game of this form with
 
10 4 0
 
C = CP0 =  0 1 1 .
1 4 3

With coalition structure P0 = {{1}, {2}, {3}}, the solution is (x1 , x2 , x3 ) =

(0, 1, 0) and the coalition values are v({1}, P0 ) = 4, v({2}, P0 ) = 1 and v({3}, P0 ) =
4.
Consider coalition structure P = {{1, 2}, {3}}, The payoff matrix becomes
 
10 5 1
 
CP =  10 5 1 
1 4 3

and a solution of (0, 0, 1). The values of the coalitions in this case are v({1, 2}, P) =
1 and v({3}, P) = 3.
Note that coalition structure P is not superadditive since

v({1}, P0 ) + v({2}, P0 ) > v({1, 2}, P).

6-15
When Players 1 and 2 do not cooperate, Player 2 fills the container with a benefit
of 4 to Player 3. Suppose the bottom two players form coalition {1, 2}. Then if
Player 2 is given an empty container, the coalition will have Player 1 fill it with his
commodity, earning 10 for the coalition. So, if Player 3 does not fill the container,
the formation of coalition {1, 2} reduces Player 3’s benefit from 4 to 1. As a result,
Player 3 fills the container himself, and earns 3. The coalition {1, 2} only earns 1
(not 10).
Remember that Chew’s model assumes that all players have full knowledge of
the coalition structure that has formed. Obvious natural extensions of this simple
model would incorporate secret coalitions and delayed coalition formation (i.e.,
changes in the coalition structure while the container is being passed).
Example 6.2. Consider the three player game of this form with
 
4 1 4
 
C = CP0 =  1 0 3 .
2 5 1

With coalition structure P0 = {{1}, {2}, {3}}, the solution is (x1 , x2 , x3 ) =

(1, 0, 0) and the coalition values are v({1}, P0 ) = 4, v({2}, P0 ) = 1 and v({3}, P0 ) =
2.
Under the formation of coalition structure P = {{1}, {2, 3}}, the resources of
players 2 and 3 are combined. This yields a payoff matrix of
 
4 1 4
 
CP =  3 5 4 
3 5 4

and a solution of (0, 1, 0). The values of the coalitions in this case are v({1}, P) = 1
and v({2, 3}, P) = 5.
Finally, if all of the players join to form the grand coalition, PG , the payoff matrix
becomes  
7 6 8
 
CP G =  7 6 8 
7 6 8
with a solution of (0, 0, 1) and v({1, 2, 3}, PG ) = 8. Note that

v({1}, P0 ) + v({2, 3}, P) > v({1, 2, 3}, PG ).

From Theorem 6.6, we know that the core for this game is empty.

6-16
6.5 BIBLIOGRAPHY

[1] J. F. Bard and J. E. Falk, “An explicit solution to the multi-level programming
problem,” Computers and Operations Research,, Vol. 9, No. 1 (1982), pp. 77–
100.
[2] W. F. Bialas, Cooperative n-person Stackelberg games. working paper, SUNY
at Buffalo (1998).
[3] W. F. Bialas and M. N. Chew, A linear model of coalition formation in
n-person Stackelberg games. Proceedings of the 21st IEEE Conference on
Decision and Control (1982), pp. 669–672.
[4] W. F. Bialas and M. H. Karwan, Mathematical methods for multilevel plan-
ning. Research Report 79-2, SUNY at Buffalo (February 1979).
[5] W.F. Bialas and M.H. Karwan, On two-level optimization. IEEE Transactions
on Automatic Control;, Vol. AC-27, No. 1 (February 1982), pp. 211–214.
[6] W.F. Bialas and M.H. Karwan, Two-level linear programming. Management
Science, Vol. 30, No. 8 (1984), pp. 1004–1020.
[7] J. Bracken and J. Falk and J. McGill. Equivalence of two mathematical pro-
grams with optimization problems in the constraints. Operations Research,
Vol. 22 (1974), pp. 1102–1104.
[8] J. Bracken and J. McGill. Mathematical programs with optimization problems
in the constraints. Operations Research, Vol. 21 (1973), pp. 37–44.
[9] J. Bracken and J. McGill. Defense applications of mathematical programs
with optimization problems in the constraints. Operations Research, Vol. 22
(1974), pp. 1086–1096.
[10] Candler, W. and R. Norton, Multilevel Programming, unpublished research
memorandum, DRC, World Bank, Washington, D.C., August 1976.
[11] Candler, W. and R. Townsley, A Linear Two-Level Programming Problem.
Computers and Operations Research, Vol. 9, No. 1 (1982), pp. 59–76.
[12] R. Cassidy, M. Kirby and W. Raike. Efficient distribution of resources through
three levels of government. Management Science, Vol. 17 (1971) pp. 462–473.
[13] A. Charnes, R. W. Clower and K. O. Kortanek. Effective control through
coherent decentralization with preemptive goals. Econometrica, Vol. 35, No.
2 (1967), pp. 294–319.

6-17
[14] M. N. Chew. A game theoretic approach to coalition formation in multilevel
decision making organizations. M.S. Thesis, SUNY at Buffalo (1981).
[15] J. Fortuny and B. McCarl, “A representation and economic interpretation
of a two-level programming problem,” Journal of the Operations Research
Society, Vol. 32, No. 9 (1981), pp. 738–792.
[16] W. F. Lucas and R. M. Thrall, n-person Games in partition form. Naval
Research Logistics Quarterly, Vol. 10, (1963) pp. 281–298.
[17] P. Shenoy, On coalition formation: a game theoretic approach. Intl. Jour. of
Game Theory, (May 1978).
[18] L. N. Vicente and P. H. Calamai, Bilevel and multilevel programming: a bib-
liography review. Technical Report, University of Waterloo (1997) Available
at: ftp://dial.uwaterloo.ca/pub/phcalamai/bilevel-review/bilevel-review.ps.
[19] U. P. Wen. Mathematical methods for multilevel programming, Ph.D. Thesis,
SUNY at Buffalo (September 1981).

6-18
IE675 Game Theory Spring 2001
Homework 1 DUE February 1, 2001

1. Obtain the optimal mixed strategies for the following matrix games:
 
0 4  
 4  3 0
2
1 5
1 3

2. Show that, if we treat an m × n matrix game as a point in mn-

dimensional euclidean space, the value of the game is a continuous
function of the game. (See below)

3. Revise the dual linear programming problems for determining optimal

mixed-strategies so that they can find the optimal pure strategy. Show
that your formulation works with an example.

Notes:
For question (2), recall the following from real analysis. . .

Definition 1.1 A metric space is a set E, together with a rule which asso-
ciates with each pair x, y ∈ E a real number d(x, y) such that

a. d(x, y) ≥ 0 for all x, y ∈ E

b. d(x, y) = 0 if and only if x = y

c. d(x, y) = d(y, x) for all x, y ∈ E

d. d(x, z) ≤ d(x, y) + d(y, z) for all x, y, z ∈ E

Definition 1.2 Let E and E 0 be metric spaces, with distances denoted d

and d0 , respectively, let f : E → E 0 , and let x0 ∈ E. Then f is said to be
continuous at x0 if, given any real number  > 0, there exists a real number
δ > 0 such that if x ∈ E and d(x, x0) < δ, then d0 (f (x), f (x0)) < .

Definition 1.3 If E and E 0 are metric spaces and f : E → E 0 is a function,

then f is said to be continuous on E, or, more briefly, continuous, if f is
continuous at all points of E.
IE675 Game Theory Spring 2001
Homework 2 DUE February 8, 2001

1. Obtain the optimal mixed strategies for the following matrix games:
   
1 3 −1 2 −1 −3 1 −2
 −3 −2 2 1   3 2 −2 −1 
0 2 −2 1 0 −2 2 −1

2. Let A be a matrix game and let V = x0 Ay0T denote the expected value
of the game when using the mixed saddle-point strategies x0 and y0 .
Consider a revised game where Player 1 must announce his choice of
row first, and then (knowing Player 1’s choice) Player 2 announces his
choice of column. Let VS denote the (expected) value of the game un-
der these rules. What can one say (if anything) about the relationship
between V and VS ?
Hint: We say that VS is the value from a Stackelberg strategy.
IE675 Game Theory Spring 2001
Homework 3 DUE February 15, 2001

1. Theorem 2.8 in the lecture notes states that the Lemke-Howson

quadratic programming problem can be used to find Nash equilib-
rium solutions for a general-sum strategic form game. Although it’s
the correct approach, the proof in the lecture notes is, to say the least,
rather sloppy.
Using the proof of Theorem 2.8 provided in the lecture notes as a
starting point, develop an improved version of the proof. Try to make
your proof clear and concise.