# On Perfect Nash Equilibria of Polymatrix Games

Authors: Slim Belhaiza
Journal: Game Theory
 (2014)

---

## Abstract

When confronted with multiple Nash equilibria, decision makers have to refine their choices. Among all known Nash equilibrium refinements, theperfectness concept is probably the most famous one. It is known that weakly dominated strategies of two-player games cannot be part of a perfect equilibrium. In general, this undominance property however does not extend to n-player games (E. E. C. van Damme, 1983). In this paper we show that polymatrix games, which form a particular class of n-player games, verify the undominance property. Consequently, we prove that every perfect equilibrium of a polymatrix game is undominated and that every undominated equilibrium of a polymatrix game is perfect. This result is used to set a new characterization of perfect Nash equilibria for polymatrix games. We also prove that the set of perfect Nash equilibria of a polymatrix game is a finite union of convex polytopes. In addition, we introduce a linear programming formulation to identify perfect equilibria for polymatrix games. These results are illustrated on two small game applications. Computational experiments on randomly generated polymatrix games with different size and density are provided.


---

## Body

## 1. Introduction

Interest for game theoretic applications has been growing in engineering, management and political sciences. Apolymatrix game is a confrontation of n players (
n
≥
2
) in a normal and noncooperative context. Polymatrix games form a particular class of n-player games. A polymatrix game G
[
(
A
i
j
)
i
≠
j
] with n players is such that player i’s payoff relative to player j’s decisions is independent from the remaining players’ choices. Considering N
=
{
1
,
…
,
n
} as the set of all players, each player i
∈
N controls a finite set of pure strategies S
i
=
{
s
i
1
,
…
,
s
i
m
i
} with |
S
i
|
=
m
i. We define m
=
∑
i
∈
N
‍
m
i.


### 1.1. Literature Review

The Nash equilibrium concept [1] has often been presented as the most desirable solution for games. Authors like Avis and Fukuda [2] and Audet et al. [3, 4] presented computational methods to enumerate all Nash extreme points for two-player games. Some other authors like Daskalakis et al. [5] and Hazan and Krauthgamer [6] have recently studied the Nash equilibrium computation complexity problem, also for two-player games. Etessami and Yannakakis [7] studied the complexity of computing approximated Nash equilibria for three or more players finite games. Some pioneering results on polymatrix games are to be mentioned. Thecomplementary pivoting method was used by Yanovskaya [8] to compute polymatrix game equilibria. Howson [9], Eaves [10], and Howson and Rosenthal [11] also adopted the same approach. Quintas [12] showed that the set of Nash equilibrium points in a polymatrix game is a finite union of convex polytopes. Miller and Zucker [13] showed how to reduce the polymatrix game equilibria problem to a copositive-plus linear complementarity problem (LCP) solvable with a single application of Lemke’s algorithm [14]. Wilson [15] extended the Lemke and Howson algorithm [16] for finding a Nash equilibrium of a two-player game to n-player games. Govindan and Wilson [17] used sequences of polymatrix games to approximate and compute Nash equilibrium for n-player games. We addressed the problem of enumeration of all polymatrix game Nash extreme equilibria in Audet et al. [4]. Papadimitriou and Roughgarden [18] showed that computing a correlated equilibrium of a polymatrix game can be done in polynomial time.


### 1.2. Motivation

Decision makers, confronted to multiple Nash equilibria, have to refine their choices using other rational concepts in addition to the concept of Nash equilibrium. Game theorists introduced many refinement concepts. Among all known Nash equilibrium refinements, theperfectness concept is probably the most studied one. This concept was first introduced by Selten [19] for finite strategic form games. It is based on the idea that a reasonable equilibrium should be stable against slight perturbations in the equilibrium strategies. Hence, the perfect refinement defines stability conditions with respect to slight imperfections of rationality sometimes called “trembling-hand perfection.” Selten [19] and Myerson [20] showed that there is at least one perfect equilibrium for any strategic form game. Selten’s proof of perfect equilibrium existence is indirect and relies on the existence of Nash equilibrium in every perturbed game. Topolyan [21] used a generalization of Kakutani’s fixed point existence theorem to prove the existence of perfect equilibria in finite normal form games and extensive games with perfect recall. Her constructive proof generates a correspondence whose fixed points are precisely the perfect equilibria of a given finite game. For bimatrix games, Borm et al. [22] described amaximal Selten subset as a set of interchangeable perfect equilibria. Each maximal Selten subset is a subset of a maximal Nash subset and each extreme point of a maximal Selten subset corresponds to an extreme perfect equilibrium. Laslier and van der Straeten [23] used the concept of “trembling-hand perfection” to analyze an electoral competition problem under imperfect information. Watanabe and Yamato [24] used the same concept to study a choice of auction in seller cheating. Miltersen and Sørensen [25] proposed a computational method to find quasiperfect Nash equilibria for two-player games. While the perfectness verification problem is known to be easy with two players [26], to our knowledge, no results are reported on the perfect refinement of Nash equilibria for polymatrix games.In this paper, we intend to set an automatic procedure to verify the perfectness of polymatrix games Nash equilibria. Section2 recalls the definition of a polymatrix game Nash Equilibrium. Section 3 sets a new characterization for polymatrix games perfect equilibria and proposes a linear programming approach to conclude the perfectness of a Nash equilibrium point. Section 4 states a geometric property on the set of perfect equilibria. Section 5 presents computational results obtained over sets of randomly generated polymatrix games with different size and density.


## 1.1. Literature Review

The Nash equilibrium concept [1] has often been presented as the most desirable solution for games. Authors like Avis and Fukuda [2] and Audet et al. [3, 4] presented computational methods to enumerate all Nash extreme points for two-player games. Some other authors like Daskalakis et al. [5] and Hazan and Krauthgamer [6] have recently studied the Nash equilibrium computation complexity problem, also for two-player games. Etessami and Yannakakis [7] studied the complexity of computing approximated Nash equilibria for three or more players finite games. Some pioneering results on polymatrix games are to be mentioned. Thecomplementary pivoting method was used by Yanovskaya [8] to compute polymatrix game equilibria. Howson [9], Eaves [10], and Howson and Rosenthal [11] also adopted the same approach. Quintas [12] showed that the set of Nash equilibrium points in a polymatrix game is a finite union of convex polytopes. Miller and Zucker [13] showed how to reduce the polymatrix game equilibria problem to a copositive-plus linear complementarity problem (LCP) solvable with a single application of Lemke’s algorithm [14]. Wilson [15] extended the Lemke and Howson algorithm [16] for finding a Nash equilibrium of a two-player game to n-player games. Govindan and Wilson [17] used sequences of polymatrix games to approximate and compute Nash equilibrium for n-player games. We addressed the problem of enumeration of all polymatrix game Nash extreme equilibria in Audet et al. [4]. Papadimitriou and Roughgarden [18] showed that computing a correlated equilibrium of a polymatrix game can be done in polynomial time.


## 1.2. Motivation

Decision makers, confronted to multiple Nash equilibria, have to refine their choices using other rational concepts in addition to the concept of Nash equilibrium. Game theorists introduced many refinement concepts. Among all known Nash equilibrium refinements, theperfectness concept is probably the most studied one. This concept was first introduced by Selten [19] for finite strategic form games. It is based on the idea that a reasonable equilibrium should be stable against slight perturbations in the equilibrium strategies. Hence, the perfect refinement defines stability conditions with respect to slight imperfections of rationality sometimes called “trembling-hand perfection.” Selten [19] and Myerson [20] showed that there is at least one perfect equilibrium for any strategic form game. Selten’s proof of perfect equilibrium existence is indirect and relies on the existence of Nash equilibrium in every perturbed game. Topolyan [21] used a generalization of Kakutani’s fixed point existence theorem to prove the existence of perfect equilibria in finite normal form games and extensive games with perfect recall. Her constructive proof generates a correspondence whose fixed points are precisely the perfect equilibria of a given finite game. For bimatrix games, Borm et al. [22] described amaximal Selten subset as a set of interchangeable perfect equilibria. Each maximal Selten subset is a subset of a maximal Nash subset and each extreme point of a maximal Selten subset corresponds to an extreme perfect equilibrium. Laslier and van der Straeten [23] used the concept of “trembling-hand perfection” to analyze an electoral competition problem under imperfect information. Watanabe and Yamato [24] used the same concept to study a choice of auction in seller cheating. Miltersen and Sørensen [25] proposed a computational method to find quasiperfect Nash equilibria for two-player games. While the perfectness verification problem is known to be easy with two players [26], to our knowledge, no results are reported on the perfect refinement of Nash equilibria for polymatrix games.In this paper, we intend to set an automatic procedure to verify the perfectness of polymatrix games Nash equilibria. Section2 recalls the definition of a polymatrix game Nash Equilibrium. Section 3 sets a new characterization for polymatrix games perfect equilibria and proposes a linear programming approach to conclude the perfectness of a Nash equilibrium point. Section 4 states a geometric property on the set of perfect equilibria. Section 5 presents computational results obtained over sets of randomly generated polymatrix games with different size and density.


## 2. Polymatrix Games Nash Equilibria

Let us defineA
i
.
=
[
A
i
1
⋯
A
i
j
⋯
A
i
n
] as the payoff matrix of player i against all other players. A partial payoff a
i
j
(
s
i
k
,
s
j
l
) is assigned to player i, if player i plays his strategy s
i
k and player j plays his strategy s
j
l. Player i’s partial payoff matrix relative to player j’s strategic decisions is a m
i
×
m
j matrix A
i
j
=
(
a
i
j
k
l
). The total payoff for player i corresponding to any pure strategic choice (
s
1
k
,
…
,
s
n
l
) of the n players is
(1)
A
i
(
s
1
k
,
…
,
s
n
l
)
=
∑
j
≠
i
‍
a
i
j
(
s
i
k
,
s
j
l
)
.Each playeri selects a probability vector X
i over his set of pure strategies and tries to maximize his own total payoff. Themixed strategy vector X
i is such that X
i
=
(
x
i
1
,
…
,
x
i
m
i
), where for all k
∈
{
1
,
…
,
m
i
}, x
i
k is the relative probability with which player i plays his strategy s
i
k
∈
S
i. Player i’s mixed strategies belong to the set:
(2)
S
~
i
=
{
X
i
:
e
i
T
X
i
=
1
,
X
i
≥
0
}
,
where e
i
T is a row vector with all m
i entries equal to 1. At the end of the game, the total payoff of player i can be expressed as follows:
(3)
α
i
(
X
)
=
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
X
j
=
∑
j
≠
i
‍
∑
k
=
1
m
i
‍
∑
l
=
1
m
j
‍
a
i
j
k
l
x
i
k
x
j
l
.Like anyn-player strategic form game, a polymatrix game has at least oneNash equilibrium [1]. We can define a Nash equilibrium to be a n-tuple X
^
=
(
X
^
1
,
…
,
X
^
n
) of mixed strategies such that for any other n-tuple X
=
(
X
^
1
,
…
,
X
^
i
-
1
,
X
i
,
X
^
i
+
1
,
…
,
X
^
n
) the following inequality is satisfied:
(4)
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
,
for
i
∈
N
;
that is, player i’s payoff relative to all other players is simultaneously maximized.We denote by NE the set of Nash equilibria. This set is the union of a finite number of polytopes calledmaximal Nash subsets [12]. We define an extreme equilibrium to be any vertex of the maximal Nash subsets. Hence, the set of extreme equilibria is the set of vertices of the maximal Nash subsets. A subset T
⊂
NE is called a Nash subset if and only if every pair of elements in T is interchangeable; that is,
(5)
If
(
X
^
1
,
…
,
X
^
i
,
…
,
X
^
n
)
∈
T
,
(
Y
^
1
,
…
,
Y
^
i
,
…
,
Y
^
n
)
∈
T
,
then
,
(
X
^
1
,
…
,
Y
^
i
,
…
,
X
^
n
)
∈
T
,
(
Y
^
1
,
…
,
X
^
i
,
…
,
Y
^
n
)
∈
T
,
∀
i
∈
N
.A Nash subsetT is called maximal if it is not properly contained in another Nash subset [22]. Enumeration of all maximal Nash subsets can be achieved using an algorithm for the enumeration of all maximal cliques of a graph [26].


## 3. Polymatrix Games Nash Perfect Equilibria

LetX
^
=
(
X
^
1
,
…
,
X
^
n
) be a Nash equilibrium of a polymatrix game G
[
(
A
i
j
)
i
≠
j
] with n players, and let
(6)
M
i
=
M
i
[
A
i
.
,
(
X
^
1
,
…
,
X
^
i
-
1
,
X
^
i
+
1
,
…
,
X
^
n
)
]
=
M
i
[
A
i
.
,
X
^
-
i
]
be the set of pure best replies of player i against X
^
-
i
=
(
X
^
1
,
…
,
X
^
i
-
1
,
X
^
i
+
1
,
…
,
X
^
n
):
(7)
M
i
=
{
arg
max
⁡
h
∈
{
1
,
…
,
m
i
}
(
e
i
h
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
}
,
where e
i
h is a column vector with all entries equal to zero, except the h
t
h entry which equals one. Let us also define C
M
i
=
conv
(
M
i
), where conv
(
M
i
) is the convex envelope of M
i.


### 3.1. Polymatrix Game Perfect Equilibrium Definition

Using Selten’s definition of perfect equilibrium for a strategic form game (see [20, Chapter 5]), we define a perfect equilibrium for a polymatrix game as follows.Definition 1.
LetX
^
=
(
X
^
1
,
…
,
X
^
n
) be a Nash equilibrium of a polymatrix game G
[
(
A
i
j
)
i
≠
j
] with n players. The equilibrium X
^ isperfect if there exists a sequence {
X
r
}
r
∈
N
=
{
(
X
1
r
,
…
,
X
n
r
)
}
r
∈
N of completely mixed strategies n-tuples converging to X
^
=
(
X
^
1
,
…
,
X
^
n
), such that, for all r
∈
N and i
∈
N,
(8)
X
^
i
∈
C
M
i
[
A
i
.
,
X
-
i
r
]
.In other words, a perfect Nash equilibriumX
^ is the limit point of a sequence {
X
r
}
r
∈
N of completely mixed strategy combinations such that, for every player i
∈
N, X
^
i is a best response against every X
-
i
r in every element in this sequence. An equivalent definition which uses ϵ-perfect equilibria can also be stated (see [27, Chapter 2]).Definition 2.
LetX
^
=
(
X
^
1
,
…
,
X
^
n
) be a Nash equilibrium of a polymatrix game G
[
(
A
i
j
)
i
≠
j
] with n players. Given any strictly positive number ϵ
r, with r
∈
N, the equilibrium X
^ isperfect if there exists a sequence of ϵ-perfect equilibria {
X
ϵ
r
}
r
∈
N
=
{
(
X
1
ϵ
r
,
…
,
X
n
ϵ
r
)
}
r
∈
N in completely mixed strategies converging to X
^
=
(
X
^
1
,
…
,
X
^
n
) as ϵ
r goes to zero, such that, for all r
∈
N and i
∈
N,
(9)
if
s
i
k
∉
M
i
,
then
x
i
ϵ
r
,
k
<
ϵ
r
.This second characterization describes a perfect Nash equilibriumX
^ as the limit point of a sequence {
X
ϵ
r
}
r
∈
N of ϵ-perfect equilibria of the polymatrix game. Every strategy in an ϵ-perfect equilibrium is played with a strictly positive probability. As shown by van Damme in his corollary 2.2.6 in [27], the convergence of the sequences of ϵ-perfect equilibria to the perfect equilibrium X
^ certifies that X
^ is undominated. In other words, in every perfect equilibrium, for any given player i, any strategy s
i
k
∉
M
i is assigned a zero probability.


### 3.2.  New Definition for Polymatrix Game Perfect Equilibria

In the following, we reformulate the conditions on polymatrix games perfect equilibria to show that every player’s mixed strategic choice is a best response to any combination of the other players pure strategic choices. In other words, we show that every perfect equilibrium of a polymatrix game is undominated and every undominated equilibrium of a polymatrix game is perfect. While this result is known to always be satisfied for bimatrix games, the second part of it is not true in general for games with more than two players. Nevertheless, it appears from the next development that the particular structure of polymatrix games payoffs allows us to extend the perfectness undominance property to polymatrix games. To reach this result, we first show thatX
^ is a Nash equilibrium of a polymatrix game if and only if X
^
i
∈
C
M
i.Proposition 3.
Then-tuple X
^
=
(
X
^
1
,
…
,
X
^
n
) is a Nash equilibrium of the polymatrix game G
[
(
A
i
j
)
i
≠
j
] with n players if and only if X
^
i
∈
C
M
i for each player i
∈
N.Proof.
In the first part of the proof, we show that ifX
^
=
(
X
^
1
,
…
,
X
^
n
) is a Nash equilibrium, then X
^
i
∈
C
M
i for each player i
∈
N. In the second part, we show that if X
^
i
∈
C
M
i for each player i
∈
N, then X
^
=
(
X
^
1
,
…
,
X
^
n
) is a Nash equilibrium.
Part I(X
^
=
(
X
^
1
,
…
,
X
^
n
) is a Nash equilibrium). Since X
^ is a Nash equilibrium, for each player i and for each X
i
∈
S
~
i, we have
(10)
X
^
i
T
∑
j
≠
i
‍
A
i
j
X
^
j
≥
X
i
T
∑
j
≠
i
‍
A
i
j
X
^
j
.
Let X
^
i
=
∑
h
=
1
m
i
‍
α
i
h
e
i
h, with α
i
h
≥
0 and ∑
h
=
1
m
i
‍
α
i
h
=
1. Assume that X
^
i
∉
C
M
i. Then, there exist at least one h
=
k (s
i
k
∈
S
i), such that α
i
k
>
0 and s
i
k
∉
M
i. Thus, we can write X
^
i
=
α
i
k
e
i
k
+
∑
h
=
1
,
h
≠
k
m
i
‍
α
i
h
e
i
h. Moreover, there exists at least one strategy s
i
l
∈
S
i, such that s
i
l
∈
M
i. Since s
i
k
∉
M
i, we have
(11)
(
e
i
l
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
>
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
.
Therefore,α
i
k
(
e
i
l
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
>
α
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
X
^
j.
Hence,(12)
α
i
k
(
e
i
l
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
+
∑
h
=
1
,
h
≠
k
m
i
‍
α
i
h
(
e
i
h
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
>
α
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
+
∑
h
=
1
,
h
≠
k
m
i
‍
α
i
h
(
e
i
h
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
,
which yields
(13)
(
α
i
k
(
e
i
l
)
T
+
∑
h
=
1
,
h
≠
k
m
i
‍
α
i
h
(
e
i
h
)
T
)
︸
=
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
>
(
α
i
k
(
e
i
k
)
T
+
∑
h
=
1
,
h
≠
k
m
i
‍
α
i
h
(
e
i
h
)
T
)
︸
=
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
.
Since α
i
k
+
∑
h
=
1
,
h
≠
k
m
i
‍
α
i
h
=
∑
h
=
1
m
i
‍
α
i
h
=
1, X
i
∈
S
~
i. Thus, the mixed strategy vector X
i
∈
S
~
i is a strictly better response than X
^
i, which contradicts the fact that X
^ is a Nash equilibrium. Therefore, if X
^
=
(
X
^
1
,
…
,
X
^
n
) is a Nash equilibrium, then X
^
i
∈
C
M
i for each player i
∈
N.
Part II(X
^
i
∈
C
M
i for each player i
∈
N). Since X
^
i
∈
C
M
i for each player i
∈
N, X
^
i
=
∑
h
=
1
m
i
‍
α
i
h
e
i
h, with α
i
h
>
0 only if s
i
h
∈
M
i, and ∑
h
=
1
m
i
‍
α
i
h
=
1. We now refer to h by l if α
i
h
>
0. Then, for each pair (
l
,
k
) such that l
≠
k (s
i
k
∈
S
i), s
i
l
∈
M
i and α
i
l
>
0, we have
(14)
(
e
i
l
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
≥
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
.
Thus,
(15)
α
i
l
(
e
i
l
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
≥
α
i
l
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
.
If we sum all thel
∈
M
i, we obtain
(16)
∑
h
=
1
,
h
=
l
m
i
‍
α
i
l
(
e
i
l
)
T
︸
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
≥
∑
h
=
1
,
h
=
l
m
i
‍
α
i
l
(
e
i
k
)
T
︸
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
.
Since∑
h
=
1
,
h
=
l
m
i
‍
α
i
l
=
1, X
i
∈
S
~
i. Hence, for each player i, X
^
i is a better response than any mixed strategy vector X
i
∈
S
~
i. We deduce that if X
^
i
∈
C
M
i for each player i
∈
N, then X
^ is a Nash equilibrium.
We conclude that an-tuple X
^
=
(
X
^
1
,
…
,
X
^
n
) is a Nash equilibrium of the polymatrix game G
[
(
A
i
j
)
i
≠
j
] with n players if and only if X
^
i
∈
C
M
i, for each player i
∈
N.As shown in [4], a strategy s
i
k of a given player i is weakly dominated if, for every pure strategic combination of the other players choices, there exists X
i
-
k, a convex combination of the pure strategies of player i, such that the total payoff for i, if he plays this weakly dominated strategy, is always less or equal to his payoff if he plays the convex combination of his pure strategies X
i
-
k. In the following development, we show that in every perfect equilibrium, for any given player i, any weakly dominated strategy s
i
k that provides a total payoff strictly less than the total payoff provided by one of the dominant convex combinations X
i
-
k of his pure strategies, for some pure strategic combination of the other players choices, should be assigned a zero probability. To do so, let us define P
i
=
{
1
,
…
,
∏
j
≠
i
‍
m
j
} to be the set of indices of all pure strategy reply combinations by all players j
≠
i.Proposition 4.
LetX
^
=
(
X
^
1
,
…
,
X
^
n
) be a Nash equilibrium of a polymatrix game. For any player i, let s
i
k
∈
S
i be any weakly dominated pure strategy. Also let X
i
-
k be a convex combination of the pure strategies of player i that weakly dominates s
i
k. If for some combination g
∈
P
i the dominant convex combination X
i
-
k is such that
(17)
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
g
<
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
g
,
and if the probability x
^
i
k assigned by player i to s
i
k is strictly positive, then X
^ is not perfect.Proof.
For any playeri, if s
i
k
∈
S
i is weakly dominated, there exists a convex combination X
i
-
k of all the other pure strategies of player i, such that X
i
-
k
=
∑
h
=
1
,
h
≠
k
m
i
‍
ω
i
h
e
i
h, ∑
h
=
i
,
h
≠
k
m
i
‍
ω
i
h
=
1, and the following inequality is satisfied:
(18)
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
f
≤
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
f
,
∀
f
∈
P
i
.
If for some combinationg
∈
P
i, we have (
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
g
<
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
g, then we can write
(19)
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
f
=
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
f
,
∀
f
≠
g
∈
P
i
.
By Definition1, if X
^ is a perfect equilibrium, then X
^
i
∈
C
M
i
[
A
i
.
,
X
-
i
r
]. Since, for each player j
≠
i, X
j
r is completely mixed, each pure strategy of j in a combination f or g
∈
P
i is assigned a strictly positive probability ω
j
f
>
0 and ω
j
g
>
0, such that X
j
r
=
∑
f
∈
P
i
,
f
≠
g
‍
ω
j
f
e
j
f
+
∑
g
∈
P
i
‍
ω
j
g
e
j
g.
Thus, we have(20)
ω
j
g
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
g
<
ω
j
g
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
g
,
for
some
g
∈
P
i
,
and ω
j
f
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
f
=
ω
j
f
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
f
,
∀
f
≠
g
∈
P
i, which is equivalent to
(21)
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
ω
j
g
e
j
g
<
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
ω
j
g
e
j
g
,
for
some
g
∈
P
i
,
and (
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
ω
j
f
e
j
f
=
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
ω
j
f
e
j
f
,
∀
f
≠
g
∈
P
i.
If the weakly dominated strategys
i
k is assigned a strictly positive probability ω
i
k, then
(22)
ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
g
e
j
g
)
<
ω
i
k
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
g
e
j
g
)
,
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
for
some
g
∈
P
i
,
and ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
f
e
j
f
)
=
ω
i
k
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
f
e
j
f
)
,
∀
f
≠
g
∈
P
i.
Therefore, if we sum, respectively, on allg and f
∈
P
i, we obtain
(23)
∑
g
∈
P
i
‍
ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
g
e
j
g
)
<
∑
g
∈
P
i
‍
ω
i
k
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
g
e
j
g
)
,
and ∑
f
∈
P
i
,
f
≠
g
‍
ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
f
e
j
f
)
=
∑
f
∈
P
i
,
f
≠
g
‍
ω
i
k
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
f
e
j
f
), which is equivalent to
(24)
ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
∑
g
∈
P
i
‍
(
ω
j
g
e
j
g
)
<
ω
i
k
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
∑
g
∈
P
i
‍
(
ω
j
g
e
j
g
)
,
ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
∑
f
∈
P
i
,
f
≠
g
‍
(
ω
j
f
e
j
f
)
=
ω
i
k
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
∑
f
∈
P
i
,
f
≠
g
‍
(
ω
j
f
e
j
f
)
.
Since X
j
r
=
(
∑
f
∈
P
i
,
f
≠
g
‍
(
ω
j
f
e
j
f
)
+
∑
g
∈
P
i
‍
(
ω
j
g
e
j
g
)
), adding side by side inequality (24) yields
(25)
ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
X
j
r
<
ω
i
k
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
X
j
r
.
Also, we know that the mixed strategy vectorX
^
i can be expressed using the weakly dominated strategy s
i
k and all other pure strategies. Hence, we can write
(26)
X
^
i
=
ω
i
k
e
i
k
+
∑
h
=
1
,
h
≠
k
m
i
‍
ω
i
h
e
i
h
,
such that ω
i
k
+
∑
h
=
1
,
h
≠
k
m
i
‍
ω
i
h
=
1. Thus, if we add the term
(27)
∑
h
=
1
,
h
≠
k
m
i
‍
ω
i
h
(
e
i
h
)
T
∑
j
≠
i
‍
A
i
j
(
∑
f
∈
P
i
,
f
≠
g
‍
(
ω
j
f
e
j
f
)
+
∑
g
∈
P
i
‍
(
ω
j
g
e
j
g
)
)
,
to both sides of inequality (25), we obtain
(28)
(
ω
i
k
(
e
i
k
)
T
+
∑
h
=
1
,
h
≠
k
m
i
‍
ω
i
h
(
e
i
h
)
T
)
︸
=
X
^
i
∑
j
≠
i
‍
A
i
j
X
j
r
<
(
ω
i
k
(
X
i
-
k
)
T
+
∑
h
=
1
,
h
≠
k
m
i
‍
ω
i
h
(
e
i
h
)
T
)
︸
=
X
i
∑
j
≠
i
‍
A
i
j
X
j
r
.
Thus,X
^
i
∉
C
M
i
[
A
i
.
,
X
-
i
r
], which contradicts the fact that X
^ is perfect. Therefore, if X
^ is a perfect Nash equilibrium, then for any given player i, any weakly dominated strategy s
i
k that provides a total payoff strictly less than the total payoff provided by a dominant convex combination X
i
-
k, for some pure strategic combination of the other players choices, should be assigned a zero probability.We now show that every perfect equilibrium of a polymatrix game is undominated and every undominated equilibrium of a polymatrix game is perfect. Theorem5 sets an alternate definition of perfect equilibrium for polymatrix games.Theorem 5.
LetX
^
=
(
X
^
1
,
…
,
X
^
n
) be a Nash equilibrium of a polymatrix game, and let e
j
h be any pure strategy reply vector by any player j
≠
i. The Nash equilibrium X
^ is perfect if and only if for each player i and any vector X
i
∈
S
~
i, the vector X
^
i
∈
S
~
i satisfies
(29)
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
.Proof.
In the first part of the proof, we show that ifX
^
=
(
X
^
1
,
…
,
X
^
n
) is a perfect Nash equilibrium, then (
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h for each player i
∈
N. In the second part, we show that if (
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h for each player i
∈
N, then X
^
=
(
X
^
1
,
…
,
X
^
n
) is a perfect Nash equilibrium.
Part I(the Nash equilibrium X
^ is perfect). Firstly, we write X
^
i
=
∑
k
=
1
m
i
‍
ω
i
k
e
i
k, with ∑
k
=
1
m
i
‍
ω
i
k
=
1 and ω
i
k
≥
0. Since X
^
=
(
X
^
1
,
…
,
X
^
n
) is a perfect Nash equilibrium of a polymatrix game, Proposition 4 implies that, for each player i
∈
N, X
^
i is such that any pure strategy s
i
k is assigned a nonzero probability ω
i
k
>
0 only if for any pure strategy reply vector e
j
h, by any player j
≠
i, we have
(30)
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
e
i
l
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
∀
s
i
l
≠
s
i
k
∈
S
i
,
∀
i
∈
N
.
Thus, we can write(31)
ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
ω
i
k
(
e
i
l
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
∀
s
i
l
≠
s
i
k
∈
S
i
,
∀
i
∈
N
.
Therefore, we obtain(32)
∑
k
=
1
m
i
‍
ω
i
k
(
e
i
k
)
T
︸
=
X
^
i
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
∑
k
=
1
m
i
‍
ω
i
k
(
e
i
l
)
T
︸
=
X
i
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
kkkkkkkkkkkkk
i
k
∀
s
i
l
≠
s
i
k
∈
S
i
,
∀
i
∈
N
.
Since∑
k
=
1
m
i
ω
i
k
=
1, ∑
k
=
1
m
i
‍
ω
i
k
(
e
i
l
)
T
=
X
i
T
∈
S
~
i. Hence
(33)
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
i
∈
N
.
We deduce that ifX
^ is a perfect Nash equilibrium, then X
^
i is a best response to any combination of the other players pure strategic choices.
Part II((
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h for each player i
∈
N). Many authors show how to construct a sequence of completely mixed strategies converging to a given Nash equilibrium under some refinement conditions [20, 26]. In the absence of any particular refinement condition, we can assume that it is easy to construct a sequence {
X
r
}
r
∈
N
=
{
(
X
1
r
,
…
,
X
n
r
)
}
r
∈
N of completely mixed strategies n-tuples converging to X
^
=
(
X
^
1
,
…
,
X
^
n
).
LetX
j
r
=
∑
h
=
1
m
j
‍
ω
j
r
h
e
j
h. Then, each real parameter ω
j
r
h is strictly positive (ω
j
r
h
>
0) and ∑
h
=
1
m
j
‍
ω
j
h
=
1. Since (
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h for all i
∈
N, for each positive real parameter ω
j
r
h, we can write
(34)
ω
j
r
h
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
ω
j
r
h
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
i
∈
N
.
Thus, if we sum all the h
∈
m
j, we obtain
(35)
∑
h
=
1
m
j
‍
ω
j
r
h
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
∑
h
=
1
m
j
‍
ω
j
r
h
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
i
∈
N
.
Hence,
(36)
(
X
^
i
)
T
∑
j
≠
i
‍
∑
h
=
1
m
j
‍
ω
j
r
h
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
∑
h
=
1
m
j
‍
ω
j
r
h
A
i
j
e
j
h
,
i
∈
N
.
Therefore,
(37)
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
∑
h
=
1
m
j
‍
ω
j
r
h
e
j
h
︸
=
X
j
r
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
∑
h
=
1
m
j
‍
ω
j
r
h
e
j
h
︸
=
X
j
r
,
i
∈
N
.
Since∑
h
=
1
m
j
ω
j
h
=
1, we obtain
(38)
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
X
j
r
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
X
j
r
,
i
∈
N
,
which shows that X
^
i is a best response to every X
j
r in the sequence
(39)
X
^
i
∈
C
M
i
[
A
i
.
,
X
-
i
r
]
.
Hence,X
^ satisfies the conditions of Definition 1; that is, X
^ is a perfect Nash equilibrium.
We finally conclude that the Nash equilibriumX
^ is perfect if and only if for any pure strategy reply vector e
j
h by any player j
≠
i, for each player i and any vector X
i
∈
S
~
i, the vector X
^
i
∈
S
~
i satisfies
(40)
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
.
This shows thatX
^ is a perfect Nash equilibrium if and only if it is a best response to any combination of the other players pure strategic choices.While this perfectness undominance property is generally not right forn-player normal form games, Theorem 5 showed how the additive structure of polymatrix games payoffs allows this property to be extended to this particular class of n-player games. Hence, if there exists a vector of mixed strategies X such that
(41)
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≠
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
then the equilibrium X
^
=
(
X
^
1
,
…
,
X
^
n
) is not perfect. An immediate corollary can be stated.Corollary 6.
LetX
^
=
(
X
^
1
,
…
,
X
^
n
) be a Nash equilibrium of a polymatrix game. For any player i, if there is a vector X
i
∈
S
~
i such that
(42)
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
∀
h
∈
P
i
,
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
g
≠
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
g
,
f
o
r
s
o
m
e
g
∈
P
i
,
then X
^ is not perfect.This characterization of equilibrium strategies can be used to verify if a Nash equilibriumX
^
=
(
X
^
1
,
…
,
X
^
n
) is perfect or not.Proposition 7.
The equilibriumX
^
=
(
X
^
1
,
…
,
X
^
n
) is perfect if and only if all optimal objective functions values of the following linear programs are equal to zero, for all i
∈
N:
(43)
maximize
(
X
i
,
ϵ
i
)
∈
R
m
i
×
R
|
P
i
|
∑
h
∈
P
i
‍
ϵ
i
h
subject
to
i
e
m
i
t
X
i
=
1
,
kkkkkkkkk
kkk
i
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
kkkkkkkkk
kkk
i
≥
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
+
ϵ
i
h
,
kkkkkkkkkkkkk
k
∀
h
∈
P
i
,
X
i
,
ϵ
i
≥
0
,
where e
m
i is a column vector with all entries equal to one.Proof.
Let(
X
i
*
,
ϵ
i
*
) be the optimal solution for a linear program (43), for some i
∈
N. If the optimal objective function value is strictly positive, then at least one of the ϵ
i
h variables is strictly positive.
In other words, there is at least oneϵ
i
h
>
0, with h
∈
P
i, such that
(44)
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
+
ϵ
i
h
.
Therefore, we have(
X
i
)
T
∑
j
≠
i
A
i
j
e
j
h
>
(
X
^
i
)
T
∑
j
≠
i
A
i
j
e
j
h, which means that
(45)
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≠
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
while (
X
i
)
T
∑
j
≠
i
A
i
j
e
j
h
≥
(
X
^
i
)
T
∑
j
≠
i
A
i
j
e
j
h
+
ϵ
i
h is satisfied. Hence, the equilibrium X
^
=
(
X
^
1
,
…
,
X
^
n
) is not perfect.
If all the optimal objective functions are equal to zero, for alli
∈
N, then all the entries of the ϵ
i
* vectors are equal to zero. The ϵ
i
* vectors correspond to the maximum slack vectors between (
X
i
)
T
∑
j
≠
i
A
i
j
e
j
h and (
X
^
i
)
T
∑
j
≠
i
A
i
j
e
j
h. Therefore,
(46)
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
=
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
.
Hence, if all theϵ
i
* vectors are equal to zero, the equilibrium (
X
^
1
,
…
,
X
^
n
) is perfect.We note that the linear programs (43) are always feasible for X
i
=
X
^
i and ϵ
i
=
0.Example 8.
Consider a three-player polymatrix game(
3
×
3
×
3
) taken from Audet et al. [4], where A
1
., A
2
., and A
3
. are the payoff matrices of players I, II, and III, respectively. As presented in Table 1, the E
χMIP algorithm enumerated seven extreme Nash equilibria for this game using exact arithmetics:
(47)
A
1
.
=
(
10
10
-
10
20
30
25
20
-
10
-
10
-
10
0
20
30
-
15
-
10
-
10
20
10
)
,
A
2
.
=
(
-
10
20
10
-
20
30
10
30
0
35
10
-
10
-
10
30
35
30
20
10
-
20
)
,
A
3
.
=
(
-
30
-
10
10
10
20
-
30
40
10
40
20
10
20
10
20
22
30
20
40
)
.
This game has five maximal Nash subsets T
1
=
{
1,7
}, T
2
=
{
2,3
}, T
3
=
{
4
}, T
4
=
{
5
}, and T
5
=
{
6
}. For the second extreme Nash equilibrium, the linear program (43), for player III, is expressed as follows:
(48)
maximize
X
3
,
ϵ
3
ϵ
3
1
+
ϵ
3
2
+
ϵ
3
3
+
ϵ
3
4
+
ϵ
3
5
+
ϵ
3
6
+
ϵ
3
7
+
ϵ
3
8
+
ϵ
3
9
subject
to
x
31
+
x
32
+
x
33
=
1
,
kkkkkkkkkk
20
x
31
+
60
x
32
+
40
x
33
≥
40
+
ϵ
3
1
,
kkkkkkkkkk
10
x
31
+
50
x
32
+
30
x
33
≥
30
+
ϵ
3
2
,
kkkkkkkkkk
-
60
x
31
+
60
x
32
+
50
x
33
≥
50
+
ϵ
3
3
,
kkkkkkkkkk
30
x
32
+
50
x
33
≥
50
+
ϵ
3
4
,
kkkkkkkkkk
10
x
31
+
20
x
32
+
40
x
33
≥
40
+
ϵ
3
5
,
kkkkkkkkkk
-
40
x
31
+
30
x
32
+
60
x
33
≥
60
+
ϵ
3
6
,
kkkkkkkkkk
20
x
31
+
60
x
32
+
52
x
33
≥
52
+
ϵ
3
7
,
kkkkkkkkkk
30
x
31
+
50
x
32
+
42
x
33
≥
42
+
ϵ
3
8
,
kkkkkkkkkk
-
20
x
31
+
60
x
32
+
62
x
33
≥
62
+
ϵ
3
9
,
kkk
kkkkkkkkkkkkkkkkkkkkkkkkk
i
k
X
3
,
ϵ
3
≥
0
.Table 1
Extreme Nash equilibria for Example8.
Eq.
α
1
α
2
α
3
X
1
X
2
X
3
1
50
40
60
(
0,0
,
1
)
(
1,0
,
0
)
(
0,1
,
0
)
2
40
30
50
(
0,1
,
0
)
(
1,0
,
0
)
(
0,0
,
1
)
3
40
160
/
7
360
/
7
(
0
,
2
/
7
,
5
/
7
)
(
1,0
,
0
)
(
0,0
,
1
)
4
30
818
/
55
2592
/
55
(
309
/
550
,
118
/
275
,
1
/
110
)
(
8
/
11,0
,
3
/
11
)
(
0
,
1
/
11
,
10
/
11
)
5
25
12
49
(
3
/
5
,
2
/
5,0
)
(
1
/
2,0
,
1
/
2
)
(
0,0
,
1
)
6
20
40
60
(
1,0
,
0
)
(
0,0
,
1
)
(
0,1
,
0
)
7
30
40
60
(
0,0
,
1
)
(
1
/
2,0
,
1
/
2
)
(
0,1
,
0
)As in Audet et al. [28], we have used exact arithmetics to obtain exact solutions for these linear programs. For this polymatrix game, all of the seven extreme Nash equilibria enumerated are found to be perfect.


## 3.1. Polymatrix Game Perfect Equilibrium Definition

Using Selten’s definition of perfect equilibrium for a strategic form game (see [20, Chapter 5]), we define a perfect equilibrium for a polymatrix game as follows.Definition 1.
LetX
^
=
(
X
^
1
,
…
,
X
^
n
) be a Nash equilibrium of a polymatrix game G
[
(
A
i
j
)
i
≠
j
] with n players. The equilibrium X
^ isperfect if there exists a sequence {
X
r
}
r
∈
N
=
{
(
X
1
r
,
…
,
X
n
r
)
}
r
∈
N of completely mixed strategies n-tuples converging to X
^
=
(
X
^
1
,
…
,
X
^
n
), such that, for all r
∈
N and i
∈
N,
(8)
X
^
i
∈
C
M
i
[
A
i
.
,
X
-
i
r
]
.In other words, a perfect Nash equilibriumX
^ is the limit point of a sequence {
X
r
}
r
∈
N of completely mixed strategy combinations such that, for every player i
∈
N, X
^
i is a best response against every X
-
i
r in every element in this sequence. An equivalent definition which uses ϵ-perfect equilibria can also be stated (see [27, Chapter 2]).Definition 2.
LetX
^
=
(
X
^
1
,
…
,
X
^
n
) be a Nash equilibrium of a polymatrix game G
[
(
A
i
j
)
i
≠
j
] with n players. Given any strictly positive number ϵ
r, with r
∈
N, the equilibrium X
^ isperfect if there exists a sequence of ϵ-perfect equilibria {
X
ϵ
r
}
r
∈
N
=
{
(
X
1
ϵ
r
,
…
,
X
n
ϵ
r
)
}
r
∈
N in completely mixed strategies converging to X
^
=
(
X
^
1
,
…
,
X
^
n
) as ϵ
r goes to zero, such that, for all r
∈
N and i
∈
N,
(9)
if
s
i
k
∉
M
i
,
then
x
i
ϵ
r
,
k
<
ϵ
r
.This second characterization describes a perfect Nash equilibriumX
^ as the limit point of a sequence {
X
ϵ
r
}
r
∈
N of ϵ-perfect equilibria of the polymatrix game. Every strategy in an ϵ-perfect equilibrium is played with a strictly positive probability. As shown by van Damme in his corollary 2.2.6 in [27], the convergence of the sequences of ϵ-perfect equilibria to the perfect equilibrium X
^ certifies that X
^ is undominated. In other words, in every perfect equilibrium, for any given player i, any strategy s
i
k
∉
M
i is assigned a zero probability.


## 3.2.  New Definition for Polymatrix Game Perfect Equilibria

In the following, we reformulate the conditions on polymatrix games perfect equilibria to show that every player’s mixed strategic choice is a best response to any combination of the other players pure strategic choices. In other words, we show that every perfect equilibrium of a polymatrix game is undominated and every undominated equilibrium of a polymatrix game is perfect. While this result is known to always be satisfied for bimatrix games, the second part of it is not true in general for games with more than two players. Nevertheless, it appears from the next development that the particular structure of polymatrix games payoffs allows us to extend the perfectness undominance property to polymatrix games. To reach this result, we first show thatX
^ is a Nash equilibrium of a polymatrix game if and only if X
^
i
∈
C
M
i.Proposition 3.
Then-tuple X
^
=
(
X
^
1
,
…
,
X
^
n
) is a Nash equilibrium of the polymatrix game G
[
(
A
i
j
)
i
≠
j
] with n players if and only if X
^
i
∈
C
M
i for each player i
∈
N.Proof.
In the first part of the proof, we show that ifX
^
=
(
X
^
1
,
…
,
X
^
n
) is a Nash equilibrium, then X
^
i
∈
C
M
i for each player i
∈
N. In the second part, we show that if X
^
i
∈
C
M
i for each player i
∈
N, then X
^
=
(
X
^
1
,
…
,
X
^
n
) is a Nash equilibrium.
Part I(X
^
=
(
X
^
1
,
…
,
X
^
n
) is a Nash equilibrium). Since X
^ is a Nash equilibrium, for each player i and for each X
i
∈
S
~
i, we have
(10)
X
^
i
T
∑
j
≠
i
‍
A
i
j
X
^
j
≥
X
i
T
∑
j
≠
i
‍
A
i
j
X
^
j
.
Let X
^
i
=
∑
h
=
1
m
i
‍
α
i
h
e
i
h, with α
i
h
≥
0 and ∑
h
=
1
m
i
‍
α
i
h
=
1. Assume that X
^
i
∉
C
M
i. Then, there exist at least one h
=
k (s
i
k
∈
S
i), such that α
i
k
>
0 and s
i
k
∉
M
i. Thus, we can write X
^
i
=
α
i
k
e
i
k
+
∑
h
=
1
,
h
≠
k
m
i
‍
α
i
h
e
i
h. Moreover, there exists at least one strategy s
i
l
∈
S
i, such that s
i
l
∈
M
i. Since s
i
k
∉
M
i, we have
(11)
(
e
i
l
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
>
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
.
Therefore,α
i
k
(
e
i
l
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
>
α
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
X
^
j.
Hence,(12)
α
i
k
(
e
i
l
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
+
∑
h
=
1
,
h
≠
k
m
i
‍
α
i
h
(
e
i
h
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
>
α
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
+
∑
h
=
1
,
h
≠
k
m
i
‍
α
i
h
(
e
i
h
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
,
which yields
(13)
(
α
i
k
(
e
i
l
)
T
+
∑
h
=
1
,
h
≠
k
m
i
‍
α
i
h
(
e
i
h
)
T
)
︸
=
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
>
(
α
i
k
(
e
i
k
)
T
+
∑
h
=
1
,
h
≠
k
m
i
‍
α
i
h
(
e
i
h
)
T
)
︸
=
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
.
Since α
i
k
+
∑
h
=
1
,
h
≠
k
m
i
‍
α
i
h
=
∑
h
=
1
m
i
‍
α
i
h
=
1, X
i
∈
S
~
i. Thus, the mixed strategy vector X
i
∈
S
~
i is a strictly better response than X
^
i, which contradicts the fact that X
^ is a Nash equilibrium. Therefore, if X
^
=
(
X
^
1
,
…
,
X
^
n
) is a Nash equilibrium, then X
^
i
∈
C
M
i for each player i
∈
N.
Part II(X
^
i
∈
C
M
i for each player i
∈
N). Since X
^
i
∈
C
M
i for each player i
∈
N, X
^
i
=
∑
h
=
1
m
i
‍
α
i
h
e
i
h, with α
i
h
>
0 only if s
i
h
∈
M
i, and ∑
h
=
1
m
i
‍
α
i
h
=
1. We now refer to h by l if α
i
h
>
0. Then, for each pair (
l
,
k
) such that l
≠
k (s
i
k
∈
S
i), s
i
l
∈
M
i and α
i
l
>
0, we have
(14)
(
e
i
l
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
≥
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
.
Thus,
(15)
α
i
l
(
e
i
l
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
≥
α
i
l
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
.
If we sum all thel
∈
M
i, we obtain
(16)
∑
h
=
1
,
h
=
l
m
i
‍
α
i
l
(
e
i
l
)
T
︸
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
≥
∑
h
=
1
,
h
=
l
m
i
‍
α
i
l
(
e
i
k
)
T
︸
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
X
^
j
.
Since∑
h
=
1
,
h
=
l
m
i
‍
α
i
l
=
1, X
i
∈
S
~
i. Hence, for each player i, X
^
i is a better response than any mixed strategy vector X
i
∈
S
~
i. We deduce that if X
^
i
∈
C
M
i for each player i
∈
N, then X
^ is a Nash equilibrium.
We conclude that an-tuple X
^
=
(
X
^
1
,
…
,
X
^
n
) is a Nash equilibrium of the polymatrix game G
[
(
A
i
j
)
i
≠
j
] with n players if and only if X
^
i
∈
C
M
i, for each player i
∈
N.As shown in [4], a strategy s
i
k of a given player i is weakly dominated if, for every pure strategic combination of the other players choices, there exists X
i
-
k, a convex combination of the pure strategies of player i, such that the total payoff for i, if he plays this weakly dominated strategy, is always less or equal to his payoff if he plays the convex combination of his pure strategies X
i
-
k. In the following development, we show that in every perfect equilibrium, for any given player i, any weakly dominated strategy s
i
k that provides a total payoff strictly less than the total payoff provided by one of the dominant convex combinations X
i
-
k of his pure strategies, for some pure strategic combination of the other players choices, should be assigned a zero probability. To do so, let us define P
i
=
{
1
,
…
,
∏
j
≠
i
‍
m
j
} to be the set of indices of all pure strategy reply combinations by all players j
≠
i.Proposition 4.
LetX
^
=
(
X
^
1
,
…
,
X
^
n
) be a Nash equilibrium of a polymatrix game. For any player i, let s
i
k
∈
S
i be any weakly dominated pure strategy. Also let X
i
-
k be a convex combination of the pure strategies of player i that weakly dominates s
i
k. If for some combination g
∈
P
i the dominant convex combination X
i
-
k is such that
(17)
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
g
<
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
g
,
and if the probability x
^
i
k assigned by player i to s
i
k is strictly positive, then X
^ is not perfect.Proof.
For any playeri, if s
i
k
∈
S
i is weakly dominated, there exists a convex combination X
i
-
k of all the other pure strategies of player i, such that X
i
-
k
=
∑
h
=
1
,
h
≠
k
m
i
‍
ω
i
h
e
i
h, ∑
h
=
i
,
h
≠
k
m
i
‍
ω
i
h
=
1, and the following inequality is satisfied:
(18)
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
f
≤
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
f
,
∀
f
∈
P
i
.
If for some combinationg
∈
P
i, we have (
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
g
<
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
g, then we can write
(19)
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
f
=
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
f
,
∀
f
≠
g
∈
P
i
.
By Definition1, if X
^ is a perfect equilibrium, then X
^
i
∈
C
M
i
[
A
i
.
,
X
-
i
r
]. Since, for each player j
≠
i, X
j
r is completely mixed, each pure strategy of j in a combination f or g
∈
P
i is assigned a strictly positive probability ω
j
f
>
0 and ω
j
g
>
0, such that X
j
r
=
∑
f
∈
P
i
,
f
≠
g
‍
ω
j
f
e
j
f
+
∑
g
∈
P
i
‍
ω
j
g
e
j
g.
Thus, we have(20)
ω
j
g
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
g
<
ω
j
g
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
g
,
for
some
g
∈
P
i
,
and ω
j
f
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
f
=
ω
j
f
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
f
,
∀
f
≠
g
∈
P
i, which is equivalent to
(21)
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
ω
j
g
e
j
g
<
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
ω
j
g
e
j
g
,
for
some
g
∈
P
i
,
and (
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
ω
j
f
e
j
f
=
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
ω
j
f
e
j
f
,
∀
f
≠
g
∈
P
i.
If the weakly dominated strategys
i
k is assigned a strictly positive probability ω
i
k, then
(22)
ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
g
e
j
g
)
<
ω
i
k
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
g
e
j
g
)
,
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
for
some
g
∈
P
i
,
and ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
f
e
j
f
)
=
ω
i
k
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
f
e
j
f
)
,
∀
f
≠
g
∈
P
i.
Therefore, if we sum, respectively, on allg and f
∈
P
i, we obtain
(23)
∑
g
∈
P
i
‍
ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
g
e
j
g
)
<
∑
g
∈
P
i
‍
ω
i
k
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
g
e
j
g
)
,
and ∑
f
∈
P
i
,
f
≠
g
‍
ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
f
e
j
f
)
=
∑
f
∈
P
i
,
f
≠
g
‍
ω
i
k
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
(
ω
j
f
e
j
f
), which is equivalent to
(24)
ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
∑
g
∈
P
i
‍
(
ω
j
g
e
j
g
)
<
ω
i
k
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
∑
g
∈
P
i
‍
(
ω
j
g
e
j
g
)
,
ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
∑
f
∈
P
i
,
f
≠
g
‍
(
ω
j
f
e
j
f
)
=
ω
i
k
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
∑
f
∈
P
i
,
f
≠
g
‍
(
ω
j
f
e
j
f
)
.
Since X
j
r
=
(
∑
f
∈
P
i
,
f
≠
g
‍
(
ω
j
f
e
j
f
)
+
∑
g
∈
P
i
‍
(
ω
j
g
e
j
g
)
), adding side by side inequality (24) yields
(25)
ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
X
j
r
<
ω
i
k
(
X
i
-
k
)
T
∑
j
≠
i
‍
A
i
j
X
j
r
.
Also, we know that the mixed strategy vectorX
^
i can be expressed using the weakly dominated strategy s
i
k and all other pure strategies. Hence, we can write
(26)
X
^
i
=
ω
i
k
e
i
k
+
∑
h
=
1
,
h
≠
k
m
i
‍
ω
i
h
e
i
h
,
such that ω
i
k
+
∑
h
=
1
,
h
≠
k
m
i
‍
ω
i
h
=
1. Thus, if we add the term
(27)
∑
h
=
1
,
h
≠
k
m
i
‍
ω
i
h
(
e
i
h
)
T
∑
j
≠
i
‍
A
i
j
(
∑
f
∈
P
i
,
f
≠
g
‍
(
ω
j
f
e
j
f
)
+
∑
g
∈
P
i
‍
(
ω
j
g
e
j
g
)
)
,
to both sides of inequality (25), we obtain
(28)
(
ω
i
k
(
e
i
k
)
T
+
∑
h
=
1
,
h
≠
k
m
i
‍
ω
i
h
(
e
i
h
)
T
)
︸
=
X
^
i
∑
j
≠
i
‍
A
i
j
X
j
r
<
(
ω
i
k
(
X
i
-
k
)
T
+
∑
h
=
1
,
h
≠
k
m
i
‍
ω
i
h
(
e
i
h
)
T
)
︸
=
X
i
∑
j
≠
i
‍
A
i
j
X
j
r
.
Thus,X
^
i
∉
C
M
i
[
A
i
.
,
X
-
i
r
], which contradicts the fact that X
^ is perfect. Therefore, if X
^ is a perfect Nash equilibrium, then for any given player i, any weakly dominated strategy s
i
k that provides a total payoff strictly less than the total payoff provided by a dominant convex combination X
i
-
k, for some pure strategic combination of the other players choices, should be assigned a zero probability.We now show that every perfect equilibrium of a polymatrix game is undominated and every undominated equilibrium of a polymatrix game is perfect. Theorem5 sets an alternate definition of perfect equilibrium for polymatrix games.Theorem 5.
LetX
^
=
(
X
^
1
,
…
,
X
^
n
) be a Nash equilibrium of a polymatrix game, and let e
j
h be any pure strategy reply vector by any player j
≠
i. The Nash equilibrium X
^ is perfect if and only if for each player i and any vector X
i
∈
S
~
i, the vector X
^
i
∈
S
~
i satisfies
(29)
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
.Proof.
In the first part of the proof, we show that ifX
^
=
(
X
^
1
,
…
,
X
^
n
) is a perfect Nash equilibrium, then (
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h for each player i
∈
N. In the second part, we show that if (
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h for each player i
∈
N, then X
^
=
(
X
^
1
,
…
,
X
^
n
) is a perfect Nash equilibrium.
Part I(the Nash equilibrium X
^ is perfect). Firstly, we write X
^
i
=
∑
k
=
1
m
i
‍
ω
i
k
e
i
k, with ∑
k
=
1
m
i
‍
ω
i
k
=
1 and ω
i
k
≥
0. Since X
^
=
(
X
^
1
,
…
,
X
^
n
) is a perfect Nash equilibrium of a polymatrix game, Proposition 4 implies that, for each player i
∈
N, X
^
i is such that any pure strategy s
i
k is assigned a nonzero probability ω
i
k
>
0 only if for any pure strategy reply vector e
j
h, by any player j
≠
i, we have
(30)
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
e
i
l
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
∀
s
i
l
≠
s
i
k
∈
S
i
,
∀
i
∈
N
.
Thus, we can write(31)
ω
i
k
(
e
i
k
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
ω
i
k
(
e
i
l
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
∀
s
i
l
≠
s
i
k
∈
S
i
,
∀
i
∈
N
.
Therefore, we obtain(32)
∑
k
=
1
m
i
‍
ω
i
k
(
e
i
k
)
T
︸
=
X
^
i
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
∑
k
=
1
m
i
‍
ω
i
k
(
e
i
l
)
T
︸
=
X
i
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
kkkkkkkkkkkkk
i
k
∀
s
i
l
≠
s
i
k
∈
S
i
,
∀
i
∈
N
.
Since∑
k
=
1
m
i
ω
i
k
=
1, ∑
k
=
1
m
i
‍
ω
i
k
(
e
i
l
)
T
=
X
i
T
∈
S
~
i. Hence
(33)
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
i
∈
N
.
We deduce that ifX
^ is a perfect Nash equilibrium, then X
^
i is a best response to any combination of the other players pure strategic choices.
Part II((
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h for each player i
∈
N). Many authors show how to construct a sequence of completely mixed strategies converging to a given Nash equilibrium under some refinement conditions [20, 26]. In the absence of any particular refinement condition, we can assume that it is easy to construct a sequence {
X
r
}
r
∈
N
=
{
(
X
1
r
,
…
,
X
n
r
)
}
r
∈
N of completely mixed strategies n-tuples converging to X
^
=
(
X
^
1
,
…
,
X
^
n
).
LetX
j
r
=
∑
h
=
1
m
j
‍
ω
j
r
h
e
j
h. Then, each real parameter ω
j
r
h is strictly positive (ω
j
r
h
>
0) and ∑
h
=
1
m
j
‍
ω
j
h
=
1. Since (
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h for all i
∈
N, for each positive real parameter ω
j
r
h, we can write
(34)
ω
j
r
h
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
ω
j
r
h
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
i
∈
N
.
Thus, if we sum all the h
∈
m
j, we obtain
(35)
∑
h
=
1
m
j
‍
ω
j
r
h
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
∑
h
=
1
m
j
‍
ω
j
r
h
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
i
∈
N
.
Hence,
(36)
(
X
^
i
)
T
∑
j
≠
i
‍
∑
h
=
1
m
j
‍
ω
j
r
h
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
∑
h
=
1
m
j
‍
ω
j
r
h
A
i
j
e
j
h
,
i
∈
N
.
Therefore,
(37)
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
∑
h
=
1
m
j
‍
ω
j
r
h
e
j
h
︸
=
X
j
r
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
∑
h
=
1
m
j
‍
ω
j
r
h
e
j
h
︸
=
X
j
r
,
i
∈
N
.
Since∑
h
=
1
m
j
ω
j
h
=
1, we obtain
(38)
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
X
j
r
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
X
j
r
,
i
∈
N
,
which shows that X
^
i is a best response to every X
j
r in the sequence
(39)
X
^
i
∈
C
M
i
[
A
i
.
,
X
-
i
r
]
.
Hence,X
^ satisfies the conditions of Definition 1; that is, X
^ is a perfect Nash equilibrium.
We finally conclude that the Nash equilibriumX
^ is perfect if and only if for any pure strategy reply vector e
j
h by any player j
≠
i, for each player i and any vector X
i
∈
S
~
i, the vector X
^
i
∈
S
~
i satisfies
(40)
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
.
This shows thatX
^ is a perfect Nash equilibrium if and only if it is a best response to any combination of the other players pure strategic choices.While this perfectness undominance property is generally not right forn-player normal form games, Theorem 5 showed how the additive structure of polymatrix games payoffs allows this property to be extended to this particular class of n-player games. Hence, if there exists a vector of mixed strategies X such that
(41)
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≠
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
then the equilibrium X
^
=
(
X
^
1
,
…
,
X
^
n
) is not perfect. An immediate corollary can be stated.Corollary 6.
LetX
^
=
(
X
^
1
,
…
,
X
^
n
) be a Nash equilibrium of a polymatrix game. For any player i, if there is a vector X
i
∈
S
~
i such that
(42)
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
∀
h
∈
P
i
,
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
g
≠
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
g
,
f
o
r
s
o
m
e
g
∈
P
i
,
then X
^ is not perfect.This characterization of equilibrium strategies can be used to verify if a Nash equilibriumX
^
=
(
X
^
1
,
…
,
X
^
n
) is perfect or not.Proposition 7.
The equilibriumX
^
=
(
X
^
1
,
…
,
X
^
n
) is perfect if and only if all optimal objective functions values of the following linear programs are equal to zero, for all i
∈
N:
(43)
maximize
(
X
i
,
ϵ
i
)
∈
R
m
i
×
R
|
P
i
|
∑
h
∈
P
i
‍
ϵ
i
h
subject
to
i
e
m
i
t
X
i
=
1
,
kkkkkkkkk
kkk
i
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
kkkkkkkkk
kkk
i
≥
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
+
ϵ
i
h
,
kkkkkkkkkkkkk
k
∀
h
∈
P
i
,
X
i
,
ϵ
i
≥
0
,
where e
m
i is a column vector with all entries equal to one.Proof.
Let(
X
i
*
,
ϵ
i
*
) be the optimal solution for a linear program (43), for some i
∈
N. If the optimal objective function value is strictly positive, then at least one of the ϵ
i
h variables is strictly positive.
In other words, there is at least oneϵ
i
h
>
0, with h
∈
P
i, such that
(44)
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
+
ϵ
i
h
.
Therefore, we have(
X
i
)
T
∑
j
≠
i
A
i
j
e
j
h
>
(
X
^
i
)
T
∑
j
≠
i
A
i
j
e
j
h, which means that
(45)
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≠
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
while (
X
i
)
T
∑
j
≠
i
A
i
j
e
j
h
≥
(
X
^
i
)
T
∑
j
≠
i
A
i
j
e
j
h
+
ϵ
i
h is satisfied. Hence, the equilibrium X
^
=
(
X
^
1
,
…
,
X
^
n
) is not perfect.
If all the optimal objective functions are equal to zero, for alli
∈
N, then all the entries of the ϵ
i
* vectors are equal to zero. The ϵ
i
* vectors correspond to the maximum slack vectors between (
X
i
)
T
∑
j
≠
i
A
i
j
e
j
h and (
X
^
i
)
T
∑
j
≠
i
A
i
j
e
j
h. Therefore,
(46)
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
=
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
.
Hence, if all theϵ
i
* vectors are equal to zero, the equilibrium (
X
^
1
,
…
,
X
^
n
) is perfect.We note that the linear programs (43) are always feasible for X
i
=
X
^
i and ϵ
i
=
0.Example 8.
Consider a three-player polymatrix game(
3
×
3
×
3
) taken from Audet et al. [4], where A
1
., A
2
., and A
3
. are the payoff matrices of players I, II, and III, respectively. As presented in Table 1, the E
χMIP algorithm enumerated seven extreme Nash equilibria for this game using exact arithmetics:
(47)
A
1
.
=
(
10
10
-
10
20
30
25
20
-
10
-
10
-
10
0
20
30
-
15
-
10
-
10
20
10
)
,
A
2
.
=
(
-
10
20
10
-
20
30
10
30
0
35
10
-
10
-
10
30
35
30
20
10
-
20
)
,
A
3
.
=
(
-
30
-
10
10
10
20
-
30
40
10
40
20
10
20
10
20
22
30
20
40
)
.
This game has five maximal Nash subsets T
1
=
{
1,7
}, T
2
=
{
2,3
}, T
3
=
{
4
}, T
4
=
{
5
}, and T
5
=
{
6
}. For the second extreme Nash equilibrium, the linear program (43), for player III, is expressed as follows:
(48)
maximize
X
3
,
ϵ
3
ϵ
3
1
+
ϵ
3
2
+
ϵ
3
3
+
ϵ
3
4
+
ϵ
3
5
+
ϵ
3
6
+
ϵ
3
7
+
ϵ
3
8
+
ϵ
3
9
subject
to
x
31
+
x
32
+
x
33
=
1
,
kkkkkkkkkk
20
x
31
+
60
x
32
+
40
x
33
≥
40
+
ϵ
3
1
,
kkkkkkkkkk
10
x
31
+
50
x
32
+
30
x
33
≥
30
+
ϵ
3
2
,
kkkkkkkkkk
-
60
x
31
+
60
x
32
+
50
x
33
≥
50
+
ϵ
3
3
,
kkkkkkkkkk
30
x
32
+
50
x
33
≥
50
+
ϵ
3
4
,
kkkkkkkkkk
10
x
31
+
20
x
32
+
40
x
33
≥
40
+
ϵ
3
5
,
kkkkkkkkkk
-
40
x
31
+
30
x
32
+
60
x
33
≥
60
+
ϵ
3
6
,
kkkkkkkkkk
20
x
31
+
60
x
32
+
52
x
33
≥
52
+
ϵ
3
7
,
kkkkkkkkkk
30
x
31
+
50
x
32
+
42
x
33
≥
42
+
ϵ
3
8
,
kkkkkkkkkk
-
20
x
31
+
60
x
32
+
62
x
33
≥
62
+
ϵ
3
9
,
kkk
kkkkkkkkkkkkkkkkkkkkkkkkk
i
k
X
3
,
ϵ
3
≥
0
.Table 1
Extreme Nash equilibria for Example8.
Eq.
α
1
α
2
α
3
X
1
X
2
X
3
1
50
40
60
(
0,0
,
1
)
(
1,0
,
0
)
(
0,1
,
0
)
2
40
30
50
(
0,1
,
0
)
(
1,0
,
0
)
(
0,0
,
1
)
3
40
160
/
7
360
/
7
(
0
,
2
/
7
,
5
/
7
)
(
1,0
,
0
)
(
0,0
,
1
)
4
30
818
/
55
2592
/
55
(
309
/
550
,
118
/
275
,
1
/
110
)
(
8
/
11,0
,
3
/
11
)
(
0
,
1
/
11
,
10
/
11
)
5
25
12
49
(
3
/
5
,
2
/
5,0
)
(
1
/
2,0
,
1
/
2
)
(
0,0
,
1
)
6
20
40
60
(
1,0
,
0
)
(
0,0
,
1
)
(
0,1
,
0
)
7
30
40
60
(
0,0
,
1
)
(
1
/
2,0
,
1
/
2
)
(
0,1
,
0
)As in Audet et al. [28], we have used exact arithmetics to obtain exact solutions for these linear programs. For this polymatrix game, all of the seven extreme Nash equilibria enumerated are found to be perfect.


## 4. Geometry of The Set of Perfect Equilibria

The preceding game example suggests that the enumeration of the extreme Nash equilibria of a polymatrix game leads to a description of the set of Nash perfect equilibria. However, to the best of our knowledge, there are no published results on the geometric properties of the set of Nash perfect equilibria for polymatrix games. By Proposition9, we show that the set of Nash equilibria of a polymatrix game is a finite union of convex polytopes.Proposition 9.
LetG
[
(
A
i
j
)
i
≠
j
]
n be a polymatrix game with n players. Any perfect Nash equilibrium X
^
=
(
X
^
1
,
…
,
X
^
n
) is a convex combination of extreme perfect Nash equilibria.Proof.
Given thatX
^
=
(
X
^
1
,
…
,
X
^
n
) is a Nash equilibrium, then X
^ can be expressed as a convex combination of a number of extreme Nash equilibria belonging to the same Nash maximal subset T.
LetX
s
=
(
X
1
,
X
2
,
…
,
X
i
-
1
,
Y
i
s
,
X
i
+
1
,
…
,
X
n
) be any extreme Nash equilibrium representing any extreme point of the Nash maximal subset T.
Then, we can writeX
^
=
∑
s
=
1
e
T
ω
s
X
s, where e
T is the number of extreme Nash equilibria in T, ω
s
≥
0, and ∑
s
=
1
e
T
ω
s
=
1. Therefore, X
^
i
=
∑
s
=
1
e
T
ω
s
Y
i
s.
Given thatX
^ is a perfect equilibrium, then for any vector X
i
∈
S
~
i, the vector X
^
i
∈
S
~
i is such that
(49)
(
X
^
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
,
where e
j
h
∈
P
i is a vector of pure strategy reply by any player j
≠
i.
Thus, for any vectorX
i
∈
S
~
i, we have
(50)
∑
s
=
1
e
T
‍
ω
s
(
Y
i
s
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
.
Now let us suppose thatX
^ can be expressed as a combination of extreme perfect and extreme nonperfect Nash equilibria of the Nash maximal subset T. In particular, let X
q
=
(
X
1
,
X
2
,
…
,
X
i
-
1
,
Y
i
q
,
X
i
+
1
,
…
,
X
n
) be an extreme nonperfect Nash equilibrium of T. Also, let X
p
=
(
X
1
,
X
2
,
…
,
X
i
-
1
,
Y
i
p
,
X
i
+
1
,
…
,
X
n
) be an extreme perfect Nash equilibrium of T. Then, we can write
(51)
X
^
=
∑
p
‍
ω
p
X
p
+
∑
q
‍
ω
q
X
q
,
with at least one ω
p
>
0 and at least one ω
q
>
0.
Thus, for everyk
≠
i, X
^
k
=
∑
p
ω
p
X
k
p
+
∑
q
ω
q
X
k
q. Since all extreme Nash equilibria of T are interchangeable and have in common X
k for every k
≠
i, we can write X
^
k
=
∑
p
ω
p
X
k
+
∑
q
ω
q
X
k. Hence, X
^
k
=
X
k, for every k
≠
i. Therefore,
(52)
(
X
^
k
)
T
∑
j
≠
k
‍
A
k
j
e
j
h
=
(
X
k
)
T
∑
j
≠
k
‍
A
k
j
e
j
h
,
∀
k
≠
i
.
On one hand, condition (52) is satisfied for X
q except for Y
i
q (k
=
i), since X
q is not perfect. Therefore, there exists a vector X
i
q
∈
S
~
i such that
(53)
(
Y
i
q
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
<
(
X
i
q
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
.
Hence, withω
q
>
0 we have
(54)
ω
q
(
Y
i
q
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
<
ω
q
(
X
i
q
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
.
On the other hand, sinceX
p is perfect, condition (52) is satisfied for X
p including Y
i
p (k
=
i). Then, for any vector X
i
p
∈
S
~
i, we have
(55)
(
Y
i
p
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
(
X
i
p
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
.
Therefore, withω
p
>
0 we have
(56)
ω
p
(
Y
i
p
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
≥
ω
p
(
X
i
p
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
.
Inequalities (54) and (56) imply
(57)
(
∑
q
‍
ω
q
(
Y
i
q
)
T
+
∑
p
‍
ω
p
(
Y
i
p
)
T
)
∑
j
≠
i
‍
A
i
j
e
j
h
<
(
∑
q
‍
ω
q
(
X
i
q
)
T
+
∑
p
‍
ω
p
(
Y
i
p
)
T
)
∑
j
≠
i
‍
A
i
j
e
j
h
.
SinceX
^
i
=
∑
s
=
1
e
T
ω
s
Y
i
s
=
∑
q
ω
q
Y
i
q
+
∑
p
ω
p
Y
i
p, we have
(58)
∑
s
=
1
e
T
‍
ω
s
(
Y
i
s
)
T
∑
j
≠
i
‍
A
i
j
e
j
h
<
(
∑
q
ω
q
(
X
i
q
)
T
+
∑
p
ω
p
(
Y
i
p
)
T
)
∑
j
≠
i
A
i
j
e
j
h
.
It is now made clear that Condition (58) contradicts Condition (50). Therefore, if X
q is a nonperfect extreme Nash equilibrium, then ω
q
=
0. Hence, any perfect Nash equilibrium X
^
=
(
X
^
1
,
…
,
X
^
n
) is a convex combination of extreme perfect Nash equilibria.A set of perfect Nash equilibria belonging to the same Nash subset is called aSelten subset. If a Selten subset is not properly contained in another Selten subset, then it is called amaximal Selten subset.Corollary 10.
Any maximal Selten subset is a convex polytope.Proof.
Following Proposition9, any perfect equilibrium is a convex combination of a number of extreme Nash equilibria belonging to the same maximal Nash subset. Therefore, any maximal Selten subset is a convex polytope.Example 11.
Given the Nash maximal subsets identified for Example8, the maximal Selten subsets of this game are S
1
=
{
1,7
}, S
2
=
{
2,3
}, S
3
=
{
4
}, S
4
=
{
5
}, and S
5
=
{
6
}.Quintas [12] showed that the set of Nash equilibrium points in a polymatrix game is a finite union of convex polytopes. These convex polytopes are possibly disjoint as in Example 8. Following Proposition 9 and Corollary 10, we state that the set of perfect Nash equilibrium points of a polymatrix game is a finite union of convex polytopes, possibly disjoint.Theorem 12.
The set of perfect Nash equilibrium points of a polymatrix game is a finite union of convex polytopes, possibly disjoint.Proof.
Any maximal Selten subset is a convex polytope contained in a maximal Nash subset. Therefore, the set of perfect Nash equilibrium points of a polymatrix game is a finite union of convex polytopes. The maximal Selten subsets are possibly disjoint as in Example8.


## 5. Applications

Many applications can be found to illustrate how polymatrix games can be used. In the following, we illustrate our results on a three-player chain store competition game and a three-player inspection management game inspired from Fandel and Trockel [29].Application 1. Figure 1 illustrates an extensive competition game with imperfect information involving three chain stores. Each of the chain stores 1, 2, and 3 has to decide either to enter the market zones of both of its opponents or not. Hence, each chain store randomizes on two pure strategic decisions “In” and “out.” Each chain store gets a partial payoff depending on its decision and the opponents’ decisions. For example, if chain store 1 decides to get “In” while chain stores 2 and 3 decide to stay out, chain store 1 gets 4
+
5 as a total payoff and chain stores 2 and 3 get, respectively, 4
+
3 and 3
+
2, respectively. This game can be reduced to a three-person polymatrix game with the following payoff matrices:
(59)
A
1
.
=
(
1
4
0
2
2
5
3
3
)
,
A
2
.
=
(
-
1
2
4
1
3
4
-
1
3
)
,
A
3
.
=
(
-
1
-
2
3
1
5
4
1
2
)
.Figure 1
Chain store competition game.Using exact arithmetics, theE
χMIP algorithm enumerated three extreme Nash equilibria for this game, as presented in Table 2. This game has three completely disjoint maximal Nash subsets T
1
=
{
1
}, T
2
=
{
2
}, and T
3
=
{
3
}. The extreme Nash equilibria 1 and 3 are not perfect. In fact, for both of these extreme equilibria, X
1
=
(
1,0
) dominates X
^
1
=
(
0,1
) and X
^
1
=
(
5
/
6
,
1
/
6
)
, respectively. The second strategy of player 1 is weakly dominated by his first strategy. Therefore, any Nash equilibrium which assigns to this strategy a strictly positive probability cannot be perfect. The extreme Nash equilibrium 2 is perfect and defines by itself the unique maximal Selten subset of this game. This equilibrium is also the unique subgame perfect Nash equilibrium of the original extensive game with imperfect information.Table 2
Extreme Nash equilibria for Application 1.
Eq.
α
1
α
2
α
3
X
1
X
2
X
3
T
Perfect
1
3
5
3
(
0,1
)
(
1,0
)
(
1,0
)
1
No
2
9
7
5
(
1,0
)
(
0,1
)
(
0,1
)
2
Yes
3
3
5
/
2
23
/
6
(
5
/
6
,
1
/
6
)
(
1,0
)
(
1,0
)
3
NoApplication 2. A polymatrix management inspection game involves three players; the manager (M), the controller (C), and the company’s management (U). The manager has to randomize between two pure strategies: m, to plan methodically, or n
m, not to plan methodically. The controller controls the manager’s work and has to randomize between two pure strategies: h, to compile a precise report on the manager’s activity, or n
h, not to compile a precise report on the manager’s activity. The company’s management inspects the controller’s report and has to randomize between two pure strategies: a, to perform an intensive inspection of the controller’s report, or n
a, not to perform an intensive inspection of the controller’s report.If the manager (M) plans methodically, he is rewarded by the company’s board with a bonus compensation B
D
a or B
D
n
a depending on the company’s board inspection. Otherwise, a penalty S
D
a or S
D
n
a is subtracted from his salary. If the controller (C) compiles a precise report he is rewarded by the company’s board with a bonus amount B
C
a or B
C
n
a depending on the company’s board inspection. Otherwise, a penalty S
C
a or S
C
n
a is subtracted from his remuneration. The manager not planning methodically has a leisure gain payoff L. The cost of a precise report to the controller is K
C
m if the manager plans methodically. Otherwise the cost of the report is K
C
n
m. The cost of an intensive inspection to the company’s board is K
U
h if the controller compiles a precise report. Otherwise the cost is K
U
n
h. If the manager plans methodically the company’s board (U) earns a profit Π. Otherwise a loss Δ is registered. The payoff matrices can be expressed as follows:
(60)
A
D
=
(
0
0
L
L
B
D
a
B
D
n
a
-
S
D
a
-
S
D
n
a
)
A
C
=
(
-
K
C
m
-
K
C
n
m
0
0
B
C
a
B
C
n
a
-
S
C
a
-
S
C
n
a
)
A
U
=
(
Π
-
B
D
a
-
Δ
+
S
D
a
Π
-
B
D
n
a
-
Δ
+
S
D
n
a
-
K
U
h
-
B
C
a
-
K
U
n
h
+
S
C
a
-
B
C
n
a
S
C
n
a
)
.The current values of the game parameters are displayed in Table3.Table 3
Three-player management inspection game parameters.
(D)
(C)
(U)
L
=
440
K
C
m
=
400, K
C
n
m
=
600
K
U
h
=
100, K
U
n
h
=
200
B
D
a
=
40
B
C
a
=
300
Π
=
1000
B
D
n
a
=
10
B
C
n
a
=
100
Δ
=
500
S
D
a
=
400
S
C
a
=
200
S
D
n
a
=
100
S
C
n
a
=
100This game has three extreme Nash equilibria and two maximal Nash subsetsT
1
=
{
1,2
} and T
2
=
{
2,3
}. As presented in Table 4, the extreme Nash equilibria 2 and 3 are not perfect. In fact, for both of these extreme equilibria, X
1
=
(
0,1
) dominates X
^
1
=
(
1
/
2
,
1
/
2
). For the manager (D), the weakly dominated strategy m cannot be assigned a nonzero probability strategy. The extreme Nash equilibrium 1 is perfect and defines by itself the unique maximal Selten subset of this game.Table 4
Extreme Nash equilibria for Application 1.
Eq.
α
1
α
2
α
3
X
1
X
2
X
3
T
Perfect
1
40
-
200
-
100
(
0,1
)
(
0,1
)
(
1,0
)
1
Yes
2
40
-
200
430
(
1
/
2
,
1
/
2
)
(
0,1
)
(
1,0
)
1, 2
No
3
40
-
200
360
(
1
/
2
,
1
/
2
)
(
7
/
40
,
33
/
40
)
(
1,0
)
2
No


## 6. Computational Results

Our computational experiments on randomly generated polymatrix games with different size and density are presented in Table5. Using C++ implementations of the E
χMIP algorithm, these experimental results were obtained under Windows XP on workstations with 3.3 GHz Intel Core i5 vPro processors and 3.2 GB RAM. The optimization of the linear programs defined by Proposition 7 is performed using an exact arithmetics implementation of the Simplex algorithm [30].Table 5
Computational results on randomly generated polymatrix games.
Size
d
=
0.125
d
=
0.25
d
=
0.5
d
=
0.75
d
=
1.0
ne
np
%
ne
np
%
ne
np
%
ne
np
%
ne
np
%
2
×
2
×
2
53
32
60
29
22
76
15
13
87
16
16
100
10
10
100
3
×
3
×
3
110
66
60
76
20
26
29
23
79
20
19
95
16
15
94
4
×
4
×
4
157
48
31
75
38
51
39
37
95
32
27
84
39
30
77The column (Size) indicates the number of strategies of each player before elimination of strongly dominated strategies as performed in [4]. The value (d) indicates the density of the generated partial payoff matrices. The column (ne) indicates the total number of extreme Nash equilibria enumerated over 10 randomly generated polymatrix games. The column (np) indicates the total number of extreme perfect equilibria obtained. Finally the column (%) indicates the percentage of extreme perfect equilibria.


### 6.1. Discussion

The experimental results show that the percentage of extreme perfect equilibria increases with an increase of the polymatrix games density. Hence, reducing the partial payoff matrices density increases the number of extreme Nash equilibria of the polymatrix game and decreases the probability of generating perfect extreme equilibria. For2
×
2
×
2 three-person polymatrix games, Table 5 illustrates how the percentage of extreme perfect equilibria goes from 60
%, for the sparsest case where the polymatrix games density is 12.5
%, to 100
%, for a density of 100
%. Meanwhile, the average number of extreme Nash equilibria decreases from 53 to 10. This could be explained by the fact that the high number of zeros in the payoff matrices reduces the number of strictly dominated strategies and increases the number of extreme Nash equilibria by offering a number of strategies with the same zero payoff for each player. At the same time, the high number of zeros in the payoff matrices increases the number of weakly dominated strategies which decreases the probability of meeting extreme perfect equilibria. This behavior was already observed for bimatrix games [26].


## 6.1. Discussion

The experimental results show that the percentage of extreme perfect equilibria increases with an increase of the polymatrix games density. Hence, reducing the partial payoff matrices density increases the number of extreme Nash equilibria of the polymatrix game and decreases the probability of generating perfect extreme equilibria. For2
×
2
×
2 three-person polymatrix games, Table 5 illustrates how the percentage of extreme perfect equilibria goes from 60
%, for the sparsest case where the polymatrix games density is 12.5
%, to 100
%, for a density of 100
%. Meanwhile, the average number of extreme Nash equilibria decreases from 53 to 10. This could be explained by the fact that the high number of zeros in the payoff matrices reduces the number of strictly dominated strategies and increases the number of extreme Nash equilibria by offering a number of strategies with the same zero payoff for each player. At the same time, the high number of zeros in the payoff matrices increases the number of weakly dominated strategies which decreases the probability of meeting extreme perfect equilibria. This behavior was already observed for bimatrix games [26].


## 7. Conclusion

Game theoretic applications have been increasingly encountered in engineering, management and political sciences. Decision makers can often be represented by autonomous agents such as hardware (central units) or software (program applications), which are unable to distinguish between a set of Nash equilibria unless a refinement procedure is used. This paper presents a new characterization of perfect Nash equilibria for polymatrix games. This characterization shows that a Nash equilibrium is perfect if and only if it is a best response to any combination of the other players pure strategic plays. While this characterization is generally not right forn-player games as shown by van Damme (see [27, Chapter 2]), the additive structure of polymatrix games payoffs allows the undominance property of perfect equilibria to be extended to this particular class of n-player normal form games.Moreover, we show that any perfect Nash equilibrium is a convex combination of extreme perfect Nash equilibria. As an immediate implication of this result, the set of perfect Nash equilibria of a polymatrix game is a finite union of convex polytopes. A linear programming formulation to identify perfect equilibria for polymatrix games is presented. Finally, the results of this paper are used to perform computational experiments on randomly generated polymatrix games with different size and density.



---

*Source: 937070-2014-09-29.xml*