3.
2 n-player nonzero sum game
We can extend the two player game to the n-player case in similar way. It is defined by
the following components:
N = {1, 2, · · · , n} is the set of players.
Ai is a finite action set of player i ∈ N . A generic element of Ai is denoted by ai .
A = i∈N Ai denotes the set of all actions profiles of the players. A generic element
Q
of A is denoted by a = (a1 , a2 , · · · , an ).
(ri (a))a∈A is the payoff vector of player i where ri (a) is the payoff player i receives
when the players choose actions a1 , a2 , . . . , an simultaneously.
Ti = τi ∈ R|Ai | | ai ∈Ai τi (ai ) = 1, τi (ai ) ≥ 0, ∀ ai ∈ Ai denote the set of all
P
mixed strategies of player i, i ∈ N ; |Ai | is the cardinality of action set Ai .
T
Q
Q = i∈N Ti is the set of of mixed strategy profiles of the players, and T−i =
j∈N ;j6=i Tj is the set of mixed strategy profiles of all the players except player i.
The generic elements of T and T−i are denoted by τ = (τ1 , τ2 , · · · , τn ) and τ−i =
(τ1 , · · · , τi−1 , τi+1 , · · · , τn ) respectively.
When each player i, i ∈ N , chooses strategy τi simultaneously, the payoff of player i is
given by XY
ui (τ ) = τj (aj )ri (a). (32)
a∈A j∈N
For a given mixed strategy profile τ−i of all the players except player i, the set of best
response strategies of player i is given by
BRi (τ−i ) = τ̄i | ui (τ̄i , τ−i ) ≥ ui (τi , τ−i ), ∀ τi ∈ Ti . (33)
A strategy pair is said to be a Nash equilibrium iff for each i ∈ N , the following inequality
holds
ui (τi∗ , τ−i
∗ ∗
) ≥ ui (τi , τ−i ), ∀ τi ∈ Ti . (34)
From (33) and (34), a strategy profile τ ∗ is a Nash equilibrium iff τi∗ ∈ BR(τ−i
∗
) for all
i ∈ N.
3.2.1 Existence of Nash equilibrium
We show that there always exists a mixed strategy Nash equilibrium for a finite strategic
game. We use Kakutani fixed point theorem to prove the result. Let P(T ) be a power
set of T . Define a set valued map
G : T → P(T )
such that Y
G(τ ) = BRi (τ−i ).
i∈N
24
A strategy profile τ is said to be a fixed point of G(·) if τ ∈ G(τ ), i.e., τi ∈ BRi (τ−i )
for all i ∈ N . This implies that a fixed point of G(·) is a Nash equilibrium of the game.
Therefore, to show the existence of a Nash equilibrium it is enough to show that there
exists a fixed point of the set valued map G(·).
Theorem 3.8. There always exists a mixed strategy Nash equilibrium for an n-player
finite strategic game.
Proof. In order to show that G has a fixed point, we show that G satisfies all the following
conditions of Kakutani fixed point theorem:
1. T is a non-empty, convex, and compact subset of a finite dimensional Euclidean
space.
2. G(τ ) is non-empty and convex for all τ ∈ X.
3. G(·) has closed graph: if (τn , τ̄n ) → (τ, τ̄ ) with τ̄n ∈ G(τn ) for all n, then τ̄ ∈ G(τ ).
Condition 1 holds from the definition of T . For fixed τ−i , ui (·, τ−i ) is a continuous function
of τi . For each i ∈ I, BRi (τ−i ), is non-empty because a continuous function ui (·, τ−i ) over
a compact set Ti always attains maxima. Hence, G(τ ) is non-empty for all τ ∈ T . For
each i ∈ I, BRi (τ−i ) is a convex set because ui (·, τ−i ) is a linear function of τi . Hence,
G(τ ) is a convex set for all τ ∈ T . Now, we prove that G(·) is a closed graph. Assume
that G(·) is not a closed graph, i.e., there is a sequence (τ n , τ̄ n ) → (τ, τ̄ ) with τ̄ n ∈ G(τ n )
for all n, but τ̄ ∈
/ G(τ ). In this case, τ̄i ∈ / BRi (τ−i ) for some i ∈ I. Then, there is an > 0
and a τ̃i such that
ui (τ̃i , τ−i ) > ui (τ̄i , τ−i ) + 3. (35)
Since, ui (·) is a continuous function of τ , ui (τ̄in , τ−i n
) → ui (τ̄i , τ−i ). Then, there exists an
integer N1 such that
ui (τ̄in , τ−i
n
) < ui (τ̄i , τ−i ) + , ∀ n ≥ N1 . (36)
From (35) and (36), we have
ui (τ̄in , τ−i
n
) < ui (τ̃i , τ−i ) − 2, ∀ n ≥ N1 . (37)
n
Similarly, ui (τ̃i , τ−i ) → ui (τ̃i , τ−i ). Then, there exists an integer N2 such that
n
ui (τ̃i , τ−i ) < ui (τ̃i , τ−i ) + , ∀ n ≥ N2 . (38)
Let N = max{N1 , N2 }. Then, from (37) and (38), we have
n
ui (τ̃i , τ−i ) > ui (τ̄in , τ−i
n
) + , ∀ n ≥ N.
That is, τ̃i performs better than τ̄in against τ−in
for all n ≥ N which contradicts τ̄in ∈
n
BRi (τ−i ) for all n. Hence, G(·) is a closed graph. That is, the set valued map G(·)
satisfies all the conditions of Kakutani fixed point theorem. Hence, G(·) has a fixed point
τ ∗ . Such τ ∗ is a Nash equilibrium of the game.
25
