# An Algorithm for Computing All Berge Equilibria

Authors: H. W. Corley; Phantipa Kwain
Journal: Game Theory
 (2015)

---

## Abstract

An algorithm is presented in this note for determining all Berge equilibria for ann-person game in normal form. This algorithm is based on the notion of disappointment, with the payoff matrix (PM) being transformed into a disappointment matrix (DM). The DM has the property that a pure strategy profile of the PM is a BE if and only if (0,…,0) is the corresponding entry of the DM. Furthermore, any (0,…,0) entry of the DM is also a more restrictive Berge-Vaisman equilibrium if and only if each player’s BE payoff is at least as large as the player’s maximin security level.


---

## Body

## 1. Introduction

In a Berge equilibrium (BE) for ann-person game, every n
-
1 player has pure strategies that maximized the remaining player’s payoff. The BE was intuitively defined for pure strategies in [1] as a refinement to the Nash equilibrium (NE) [2]. The BE was formalized in [3] as a game-theoretic solution concept modeling mutual support and cooperation, as opposed to the selfishness of the NE. However, the BE was not studied extensively until recently. For example, see [4–9]. Only [6, 7] offer approaches for obtaining BEs, though, and these methods are stated abstractly without examples.A simple algorithm is presented here for computing all BEs for ann-person game G
=
(
N
,
(
S
i
)
i
∈
N
,
(
u
i
)
i
∈
N
) in normal form, with N
=
{
1
,
…
,
n
} the set of players, S
i the finite set of pure strategies for player i, and u
i
(
s
1
,
…
,
s
n
) the von Neumann-Morgenstern utility of player i for a pure strategy profile s
=
(
s
1
,
…
,
s
n
)
∈
×
j
∈
N
S
j
=
S. The BE is defined as follows, where an incomplete strategy profile s
-
i
=
(
s
1
,
…
,
s
i
-
1
,
s
i
+
1
,
…
,
s
n
) denotes a member of S
-
i
=
×
j
∈
N
∖
{
i
}
S
j.Definition 1.
The strategy profiles
* is a BE of G if and only if
(1)
u
i
s
*
=
max
⁡
s
-
i
∈
S
-
i
u
i
s
i
*
,
s
-
i
∀
i
∈
N
.
The BE s
* is further called a Berge-Vaisman equilibrium (BVE) if and only if the maximin security levels α
i of the players satisfy
(2)
α
i
=
max
⁡
s
i
∈
S
i
min
⁡
s
-
i
∈
S
-
i
u
i
s
i
,
s
-
i
≤
u
i
s
*
∀
i
∈
N
so that no player is guaranteed better payoff than that given by s
*.In Section2 we define the disappointment matrix (DM) corresponding to the payoff matrix (PM) for G and prove that a pure strategy s
* is a BE if and only if (
0
,
…
,
0
) is the corresponding entry of the DM. In Section 3 the approach of Section 2 is formalized as an algorithm to obtain all BEs and BVEs for G. In Section 4 a computational example is presented for n
=
3.


## 2. The Disappointment Matrix

The disappointment function is defined as a transformation of a player’s payoffs to losses.Definition 2.
For the gameG, the disappointment incurred by any player i choosing s
i and the other n
-
1 players choosing s
-
i is defined as
(3)
d
i
s
=
d
i
s
i
,
s
-
i
=
max
⁡
t
-
i
∈
S
-
i
u
i
s
i
,
t
-
i
-
u
i
s
i
,
s
-
i
hhhhhhhhhhhhhhhh
∀
i
∈
N
.The disappointment incurred by playeri for a strategy profile s
=
(
s
i
,
s
-
i
) is thus the difference between the best payoff that player i could obtain by choosing s
i and the actual payoff that player i would obtain for the strategy profile (
s
i
,
s
-
i
). This definition immediately gives the following result.Theorem 3.
The pure strategy profiles
* is a BE for the game G if and only if the disappointment d
i
(
s
*
)
=
0 for all i
∈
N. Moreover, a BE s
* is also a BVE if and only if α
i
≤
u
i
(
s
*
) for all i
∈
N.Proof.
The strategy profiles
* is a BE if and only if it satisfies (1) of Definition 1. However, (1) holds if and only if d
i
(
s
*
)
=
0 in (3) for all i
∈
N. To complete the proof, the BE s
* is also a BVE if and only if it satisfies (2).The DM of a game is now defined.Definition 4.
The disappointment matrix ofG is the matrix obtained from its PM by replacing (
u
1
(
s
)
,
…
,
u
n
(
s
)
) by (
d
1
(
s
)
,
…
,
d
n
(
s
)
) for all s
∈
S.


## 3. Algorithm

Consider the gameG in which each player i
∈
N has m
i pure strategies. Denote the jth strategy of player i by s
i
j
,
j
=
1
,
…
,
m
i. Algorithm 1 describes the algorithmBECOMP for obtaining all BEs and BVEs for G from its DM. The computational complexity ofBECOMPis O
(
n
∏
i
=
1
n
m
i
) because of the unavoidable enumeration in Step 4 of all strategy profiles (
s
i
j
,
s
-
i
)
,
j
=
1
,
…
,
m
i, for each player i.Algorithm 1
(1)1
←
i
,
1
←
j
(2)While
i
≤
n
do
(3)While
j
≤
m
j
do
(4) Computed
i
(
s
i
j
,
s
-
i
) for all s
-
i
∈
S
-
i from (3).
(5)d
i
(
s
i
j
,
s
-
i
)
←
u
i
(
s
i
j
,
s
-
i
) for all s
-
i
∈
S
-
i
(6)End While
(7)End While
(8)BE = ⋃
{
s
∈
S
:
d
i
(
s
)
=
0
,
i
=
1
,
…
,
n
}.
(9)BVE = {
s
∈ BE: α
i
≤
u
i
s
,
i
=
1
,
…
,
n
}.


## 4. Example

Forn
=
3 we use the notation ofBECOMP with m
1
=
m
2
=
m
3
=
2 and consider the game G with a PM of Table 1. The DM for G is obtained from the PM viaBECOMP and shown in Table 2. The unique BE for G is s
*
=
(
s
1
2
,
s
2
1
,
s
3
2
) with associated payoffs (
u
1
(
s
*
)
,
…
,
u
n
(
s
*
)
)
=
(
2,4
,
4
). However, s
* is not a BVE since α
1
=
3
>
u
1
s
*
=
2. Player 1 is guaranteed better payoff by choosing s
1
1 instead of s
1
2.Table 1
PM forG.
Player 1
Player 3
s
3
1
s
3
2
Player 2
Player 2
s
2
1
s
2
2
s
2
1
s
2
2
s
1
1
(3, 1, 2)
(3, 4, 0)
(6, 3, 0)
(3, 5, 1)
s
1
2
(1, 4, 5)
(2, 2, 3)
(2, 4, 4)
(−1, 2, 3)Table 2
DM forG.
Player    1
Player 3
s
3
1
s
3
2
Player 2
Player 2
s
2
1
s
2
2
s
2
1
s
2
2
s
1
1
(3, 3, 3)
(3, 1, 5)
(0, 1, 4)
(3, 0, 3)
s
1
2
(1, 0, 0)
(0, 3, 2)
(0, 0, 0)
(3, 3, 1)



---

*Source: 862842-2015-01-29.xml*