# A Mixed Cooperative Dual to the Nash Equilibrium

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

---

## Abstract

A mixed dual to the Nash equilibrium is defined forn-person games in strategic form. In a Nash equilibrium every player’s mixed strategy maximizes his own expected payoff for the other n
-
1 players’ strategies. Conversely, in the dual equilibrium every n
-
1 players have mixed strategies that maximize the remaining player’s expected payoff. Hence this dual equilibrium models mutual support and cooperation to extend the Berge equilibrium from pure to mixed strategies. This dual equilibrium is compared and related to the mixed Nash equilibrium, and both topological and algebraic conditions are given for the existence of the dual. Computational issues are discussed, and it is shown that for each n
>
2 there exists a game for which no dual equilibrium exists.


---

## Body

## 1. Introduction

The mathematical analysis of both competition and cooperation falls within the realm of game theory, whose systematic development began with von Neumann and Morgenstern [1]. For a game with n players, Nash [2] later assumed that the players are rational and hence selfish. He then defined an equilibrium in which every player’s strategy maximizes his payoff for the other n
-
1 players’ strategies. Modern game theory [3–5] has long required that any rational solution concept for a game should be a Nash equilibrium. However, in games known as social dilemmas [6, 7] selfish behavior conflicts with group interests; and individual players do better by cooperating. The less well-known Berge equilibrium was introduced for pure strategies in [8] and formalized in [9]. A Berge equilibrium is a pure strategy profile in which every n
-
1 players have strategies that maximize the remaining player’s payoff. It has been increasingly studied as a model of mutual support and cooperation as in [10–15].In this paper we considern-person games in strategic form and extend the Berge equilibrium from pure to mixed strategies to provide a dual to the Nash equilibrium. In this dual equilibrium, every n
-
1 players have strategies that maximize the remaining player’s expected payoff. The Nash equilibrium and the dual equilibrium thus model opposite decision criteria for choosing the n player’s actions, regardless of whether these actions are independently selected by the players, are coordinated by the players, or are even prescribed. For example, the results here are valid if an arbiter assigns actions to the players as in [16].In Section2 the dual equilibrium is formally defined and related to the Nash equilibrium. In Section 3 topological and algebraic conditions are established for the existence of a dual equilibrium. In Section 4 computation complexity issues are discussed. In Section 5 it is shown that for each n
>
2 there exists a game for which no dual equilibrium exists. Conclusions are stated in Section 6.


## 2. Relationships between the Dual and Nash Equilibria

The following definitions and notation are used. LetG
n
=
(
I
,
(
S
i
)
i
∈
I
,
(
u
i
)
i
∈
I
) be an n-person game in strategic form, where I
=
{
1
,
…
,
n
} is the index set for the n players, S
i is the finite set of m
i actions for player i, and u
i
(
s
1
,
…
,
s
n
) is the von Neumann-Morgenstern utility of player i for a pure strategy profile s
=
(
s
1
,
…
,
s
n
)
∈
⨉
j
∈
I
S
j
=
S. Write u
(
s
) for (
u
1
(
s
)
,
…
,
u
n
(
s
)
) and denote the set of mixed strategies for player i by Δ
S
i. A mixed-strategy profile σ
=
(
σ
1
,
…
,
σ
n
)
∈
⨉
j
∈
I
Δ
S
j
=
Δ
S is an n-tuple of individual randomized strategies, where σ
i
(
s
i
) is the probability that player i uses the pure strategy s
i
∈
S
i. For any τ
i
∈
Δ
S
i, abbreviate the strategy profile (
σ
1
,
…
,
σ
i
-
1
,
τ
i
,
σ
i
+
1
,
…
,
σ
n
) by (
τ
i
,
σ
-
i
). Similarly write I
-
i
=
I
-
{
i
}, S
-
i
=
⨉
j
∈
I
-
i
S
j, and Δ
S
-
i
=
⨉
j
∈
I
-
i
Δ
S
j. For ∀
i
∈
I, extend u
i
:
S
→
R
1 from S to Δ
S by defining the expected utility function u
i
(
σ
)
=
∑
(
s
1
,
…
,
s
n
)
∈
S
∏
j
∈
I
σ
j
(
s
j
)
u
i
(
s
1
,
…
,
s
n
). Writing σ
-
i
(
s
-
i
)
=
∏
j
∈
I
-
i
σ
j
(
s
j
), ∀
s
-
i
∈
S
-
i, and noting that a pure strategy is a special case of a mixed strategy, we can derive the following useful identities:(1)
u
i
σ
i
,
σ
-
i
=
∑
s
i
∈
S
i
σ
i
s
i
u
i
s
i
,
σ
-
i
,
(2)
u
i
s
i
,
σ
-
i
=
∑
s
-
i
∈
S
-
i
σ
-
i
s
-
i
u
i
s
i
,
s
-
i
,
(3)
u
i
σ
i
,
σ
-
i
=
∑
s
-
i
∈
S
-
i
σ
-
i
s
-
i
u
i
σ
i
,
s
-
i
,
(4)
u
i
σ
i
,
s
-
i
=
∑
s
i
∈
S
i
σ
i
s
i
u
i
s
i
,
s
-
i
.The Nash equilibrium is now formally defined for comparison with the dual equilibrium.Definition 1 (NE).
The strategy profileσ
∗ is a Nash equilibrium (NE) of G
n if and only if (5)
u
i
σ
∗
=
max
σ
i
∈
Δ
S
i
⁡
u
i
σ
i
,
σ
-
i
∗
,
∀
i
∈
I
.Definition 2 (DE).
The strategy profileσ
∗ is a dual equilibrium (DE) of G
n if and only if (6)
u
i
σ
∗
=
max
σ
-
i
∈
Δ
S
-
i
⁡
u
i
σ
i
∗
,
σ
-
i
,
∀
i
∈
I
.
Designating a strategy profileσ
∗ satisfying (6) as a dual equilibrium may be justified as follows. Equations (5) and (6) involve systems of optimization problems defining NEs and DEs. These systems may be regarded as symmetric dual systems in the sense that Definition 1 becomes Definition 2 and vice versa when the subscripts i and -
i are interchanged on the right (but not left) sides of (5) and (6). Thus if (5) is considered the primal system and (6) the dual system, then the dual system of the dual system is the primal system. This duality is manifested in the fact that in Definition 1 every player’s NE strategy selfishly maximizes his own payoff for the other n
-
1 players’ NE strategies, while the opposite situation occurs in Definition 2. For a DE, every n
-
1 players have DE strategies that maximize the remaining player’s payoff. Thus a DE exhibits themusketeer property in [17] of “all for one, one for all.” Alternately, in an NE no individual player can improve his expected payoff with a unilateral change in strategy, while in a DE no individual player’s payoff can be improved by any change in the remaining players’ DE strategies.
The DE is the mixed extension of the Berge equilibrium (BE) of [11–14] and the mutual-max outcome of [18]. For a BE, which involves only pure strategies, mutual cooperation occurs in a single game. For a mixed-strategy DE, the probability σ
i
(
s
i
) can be interpreted in two ways [19]. The first interpretation is the fraction of time in the long run that player i would choose to play pure strategy s
i in a series of repeated games in which the n mutually cooperative players invoke decision criterion (6). The second interpretation of σ
i
(
s
i
) considers a mixed-strategy equilibrium as a steady state in a large population with n subpopulations. In this case σ
i
s
i is the fraction of subpopulation i preferring pure strategy s
i according to decision criteria (6).
Some results relating DE and NE are now established. Let the functiond
:
I
→
I be one-to-one on the index set I. Then d is a derangement of I if and only if d
i
≠
i, ∀
i
∈
I. Thus associated with G
n
=
(
I
,
(
S
i
)
i
∈
I
,
(
u
i
)
i
∈
I
) is the deranged game G
n
(
d
)
=
(
I
,
(
S
i
)
i
∈
I
,
(
v
i
)
i
∈
I
), where v
i
=
u
d
(
i
). In other words, for G
n
(
d
) the expected utility function of any player i is u
d
(
i
). In addition, for a strategy profile σ of G
n, let σ
(
d
) be its deranged strategy profile (
σ
1
(
d
)
,
…
,
σ
n
(
d
)
), where σ
j
(
d
) is the unique σ
i for which d
(
i
)
=
j. Obviously if σ is a DE of G
n, then the deranged strategy profile σ
(
d
) is also a DE of the deranged game G
n
(
d
).Theorem 3.
Ifσ
∗ is a dual equilibrium for any n-person game G
n, then σ
∗
(
d
) is a Nash equilibrium for G
n for any derangement d of I.Proof.
It is first proved that ifσ
∗ is a DE of a game G
n, then σ
∗ is an NE of G
n
(
d
) for any derangement d of I. Let i
∈
I and d be an arbitrary derangement such that d
(
i
)
=
j. From (6)(7)
u
j
σ
j
∗
,
σ
-
j
≤
u
j
σ
∗
,
∀
σ
-
j
∈
Δ
S
-
j
.Expanding (7) gives that (8)
u
j
σ
1
,
…
,
σ
j
-
1
,
σ
j
∗
,
σ
j
+
1
,
…
,
σ
n
≤
u
j
σ
∗
,
∀
σ
k
∈
Δ
S
k
,
k
∈
I
-
j
.In (8) set σ
k
=
σ
k
∗ for k
∈
I, k
≠
i
,
j. Hence, for j
=
d
(
i
),(9)
u
j
σ
1
∗
,
…
,
σ
i
-
1
∗
,
σ
i
,
σ
i
+
1
∗
,
…
,
σ
n
∗
=
u
j
σ
i
,
σ
-
i
∗
≤
u
j
σ
∗
,
∀
σ
i
∈
Δ
S
i
.From (9), for ∀
i
∈
I and any derangement d of I, (10)
u
d
i
σ
i
,
σ
-
i
∗
≤
u
d
i
σ
∗
,
∀
σ
i
∈
Δ
S
i
.Thus from (10) and (5), σ
∗ is an NE for G
n
(
d
). It follows that if σ
∗ is a DE of any n-person game G
n, then σ
∗ is an NE of G
n
(
d
) for any derangement d of I.
We next use the fact that ifσ
∗ is a DE of G
n, the deranged strategy profile σ
∗
(
d
) is also a DE of the deranged game G
n
(
d
). Then from the first part of the proof, σ
∗
(
d
) is an NE of the original game G
n obtained by applying the inverse derangement d
-
1 of d to G
n
(
d
).Corollary 4.
G
n has at least as many NEs as DEs.Proof.
Letd be the cyclic derangement given by d
(
i
)
=
i
+
1, i
=
1
,
…
,
n
-
1, and d
(
n
)
=
1. Since d is one-to-one, it follows from Theorem 3 that there is a one-to-one correspondence between the DEs of G
n and a subset of the NEs for G
n. Hence there are at least as many NEs as DEs.In Section5 it is shown that there can be more NEs than DEs. The converse of Theorem 3 is true in general only for two-person games, in which case an argument similar to that for Theorem 3 yields the following result of [20], where the zero-sum case is also considered.Corollary 5.
A strategy profileσ
∗ is a DE for the two-person game where Player 1 has utility function u
1 and Player 2 has utility function u
2 if and only if σ
∗ is an NE for the dual two-person game where Player 1 has utility function u
2 and Player 2 has utility function u
1.Example 6.
ConsiderG
2, with the payoff matrix of Table 1, where Player 1 has pure strategies S
1
=
{
s
1
,
t
1
} and Player 2 has pure strategies S
2
=
{
s
2
,
t
2
}. For simplicity, write σ
1
(
s
1
)
=
p
1, σ
1
(
t
1
)
=
p
2 for Player 1 and σ
2
(
s
2
)
=
q
1, σ
2
(
t
2
)
=
q
2 for Player 2. We apply Corollary 5. Using standard procedures for finding all NEs of two-person games [3], we obtain all DEs of G
2 by determining all NEs associated with the payoff matrix obtained by interchanging the payoffs in Table 1. The unique DE has p
1
=
0.75, p
2
=
0.25 and q
1
=
0.80, q
2
=
0.20, with expected payoffs (2.75, 5.60) with respect to the original payoff matrix of Table 1. By comparison, the unique NE of G
2 has p
1
=
0.40, p
2
=
0.60 and q
1
=
0.75, q
2
=
0.25, with expected payoffs (2.75, 5.65). Thus, the expected payoff vector for the NE dominates that of the DE in a Pareto sense. In general, the expected DE payoff u
i
(
σ
∗
) for any player i in G
n may be larger than, smaller than, or equal to the expected NE payoff for i. In this regard, neither mutual cooperation nor selfishness is necessarily better than the other.Table 1
Payoff matrix forG
2.
Player 2
s
2
t
2
Player 1
s
1
(3, 5)
(2, 8)
t
1
(2, 6)
(5, 4)


## 3. Existence Conditions for Dual Equilibria

In this section sufficient conditions are presented for the existence of a DE forG
n. For any two-person game, Corollary 5 implies that a DE exists since an NE exists [2]. For n
>
2, however, the existence of a DE is more complicated. The following preliminaries are needed.Definition 7.
A correspondenceΦ
:
X
↦
2
Y is a set-valued mapping Φ such that Φ
(
x
) is a subset of Y, ∀
x
∈
X. The domain of Φ is {
x
:
x
∈
X
,
Φ
(
x
)
≠
⌀
}, the range is ⋃
x
∈
X
Φ
(
x
), and the graph is {
(
x
,
y
)
:
x
∈
X
,
y
∈
Y
,
y
∈
Φ
(
x
)
}.Definition 8.
LetX and Y be topological vector spaces. The correspondence Φ
:
X
↦
2
Y is upper semicontinuous at x
∈
X if and only if whenever the sequence x
k
,
y
k
k
=
1
∞ in X
×
Y has lim
k
→
∞
⁡
(
x
k
,
x
k
)
=
(
x
,
y
)
∈
X
×
Y, then y
∈
Φ
(
x
).Definition 9.
LetX be a topological vector space, and let C be a nonempty convex set in X. The function f
:
X
→
R
1 is quasiconcave on C if and only if the level set L
α
=
{
x
∈
C
:
f
(
x
)
≥
α
} is a convex set for all real α.Result 1 (Kakutani fixed point theorem [21]).
LetC be a nonempty compact convex set in a finite-dimensional topological vector space X, and let Φ
:
C
↦
2
C. If Φ is upper semicontinuous at ∀
x
∈
C and if Φ
(
x
) is a nonempty convex subset of C, then ∃
x
∗
∈
C for which x
∗
∈
Φ
(
x
∗
). The point x
∗ is called a fixed point of Φ on C.Topological conditions for the existence of a dual equilibrium are now derived. For each playeri
∈
I and each σ
i
∈
Δ
S
i, denote the best support correspondence Γ
i
:
Δ
S
i
↦
Δ
S by Γ
i
(
σ
i
)
=
{
(
σ
i
,
σ
-
i
∗
)
∈
Δ
S
:
σ
-
i
∗
∈
arg
max
σ
-
i
∈
Δ
S
-
i
⁡
u
i
(
σ
i
,
σ
-
i
)
}
. From [3] the sets Δ
S, Δ
S
i, and Δ
S
-
i can be identified, respectively, with nonempty, convex, and compact subsets of the finite-dimensional Euclidean spaces R
m for m
=
∑
i
∈
I
m
i, R
m
i, and R
m
-
i for m
-
i
=
∑
j
∈
I
-
i
m
j. For each i
∈
I, u
i
(
σ
i
,
σ
-
i
) is continuous with respect to σ
-
i
∈
Δ
S
-
i and σ
i
∈
Δ
S
i, so the sets arg
max
σ
-
i
∈
Δ
S
-
i
⁡
u
i
(
σ
i
,
σ
-
i
) and Γ
i
(
σ
i
) are nonempty. Hence the correspondence Γ
:
Δ
S
↦
Δ
S given by Γ
(
σ
∗
)
=
⋂
i
∈
N
Γ
i
(
σ
i
∗
) is nonempty if and only if σ
∗ satisfies (6). The following lemma has thus been established.Lemma 10.
A strategy profileσ
∗ is a DE for the game G
n if and only if σ
∗ is a fixed point of  Γ on Δ
S.Result1 and Lemma 10 are next used to prove a topological sufficient condition.Theorem 11.
IfΓ
(
σ
) is a nonempty convex set, ∀
σ
∈
Δ
S, then there exists a DE σ
∗ for the game G
n.Proof.
We show thatΓ is upper semicontinuous on the nonempty, compact, and convex set Δ
S. Consider convergent sequences σ
k
k
=
1
∞ and τ
k
k
=
1
∞ in Δ
S, where lim
k
→
∞
⁡
σ
k
=
σ, lim
k
→
∞
⁡
τ
k
=
τ, and τ
k
∈
Γ
(
σ
k
), ∀
k
∈
{
1,2
,
3
,
…
}. For ∀
i
∈
I it follows from the definition of Γ that u
i
(
σ
i
k
,
τ
-
i
k
)
≥
u
i
(
σ
i
k
,
σ
-
i
), ∀
σ
-
i
∈
Δ
S
-
i. But the expected utility function u
i is continuous on Δ
S, so u
i
(
σ
i
,
τ
-
i
)
≥
u
i
(
σ
i
,
σ
-
i
), ∀
σ
-
i
∈
Δ
S
-
i. Hence τ
∈
Γ
i
(
σ
i
,
), ∀
i
∈
N, and so τ
∈
Γ
(
σ
). Thus Γ is upper semicontinuous on Δ
S. By assumption Γ
(
σ
) is also a nonempty convex set of Δ
S, ∀
σ
∈
Δ
S. Hence from Result 1 there exists σ
∗
∈
Δ
S for which σ
∗
∈
Γ
(
σ
∗
), and so σ
∗ is a DE by Lemma 10.More restrictive sufficient conditions are given as a corollary.Corollary 12.
Ifu
i
(
σ
i
,
σ
-
i
), ∀
i
∈
I, is a quasiconcave function of σ
-
i for each fixed σ
i
∈
Δ
S
i and if  Γ
(
σ
) is nonempty, ∀
σ
∈
Δ
S, then there exists a DE σ
∗ for the game G
n.Proof.
Fixi
∈
N and σ
i
∈
Δ
S
i. Since u
i
(
σ
i
,
σ
-
i
) is a quasiconcave on Δ
S
-
i, it follows that the level set L
α
=
{
σ
-
i
∈
Δ
S
-
i
:
u
i
(
σ
i
,
σ
-
i
)
≥
α
} is a convex set in Δ
S
-
i for all real α. In particular, setting α
∗
=
max
σ
-
i
∈
Δ
S
-
i
⁡
u
i
(
σ
i
,
σ
-
i
) implies that u
i
(
σ
i
,
λ
σ
-
i
′
+
(
1
-
λ
)
σ
-
i
′
′
)
≥
max
σ
-
i
∈
Δ
S
-
i
⁡
u
i
(
σ
i
,
σ
-
i
), ∀
σ
-
i
′, σ
-
i
′
′
∈
Δ
S
-
i, ∀
λ
∈
[
0,1
]
. Thus (
σ
i
,
λ
σ
-
i
′
+
(
1
-
λ
)
σ
-
i
′
′
)
∈
Γ
i
(
σ
i
), and Γ
i
(
σ
i
) is a nonempty convex set, ∀
i
∈
N, ∀
σ
i
∈
Δ
S
i. Hence, for ∀
σ
∈
Δ
S, Γ
(
σ
)
=
⋂
i
∈
N
Γ
i
(
σ
i
) is convex in addition to being nonempty by assumption, so Theorem 11 applies.


## 4. Computational Complexity

For the DE to be useful as a solution concept, it must be computable. Since NEs can be difficult to obtain [22, 23], we briefly discuss the computational complexity of DEs as compared to NEs. Let N
=
n
∏
j
∈
I
m
j
= (# players) (# all possible joint actions) denote the size of the input data for the game G
n
=
(
I
,
(
S
i
)
i
∈
N
,
(
u
i
)
i
∈
N
). It is shown in [22] that O
(
N
) is the computational complexity on a deterministic Turing machine for checking whether a pure NE exists for G
n and then computing all such NEs. An algorithm described in [20] uses a regret matrix to compute all pure NEs of G
2 and readily extends to G
n. A similar algorithm to compute all Berge equilibria (pure DEs) was proposed for G
n in [24] using a disappointment matrix. Both algorithms have computational complexity O
(
N
). The general problem of finding a mixed NE for G
n, which is well known to exist, involves solving the following algebraic equivalence for (5), which is proved in [25] using (1) and (2).Result 2.
The strategy profileσ
∗ is an NE of G
n if and only if (11)
∑
s
1
,
…
,
s
n
∈
S
∏
j
∈
I
σ
j
∗
s
j
u
i
s
1
,
…
,
s
n
=
max
s
i
∈
S
i
⁡
∑
s
-
i
∈
S
-
i
∏
j
∈
I
-
i
σ
j
∗
s
j
u
i
s
1
,
…
,
s
n
,
∀
i
∈
I
.
For a givenσ
∗ and ∀
i
∈
I, (11) can be checked by total enumeration in O
(
N
) to determine if σ
∗ is an NE. The problem of computing an NE for G
n is thus a member of the complexity class NP, yet obtaining an NE σ
∗ from (11) by solving for σ
j
∗
(
s
j
) may not be feasible for large n. Indeed, it is shown in [23] that this problem is PPAD-complete. In other words, this problem is believed to be computationally very difficult but may not be NP-complete. The next theorem gives an algebraic equivalence for (6) similar to (11) for DEs.Theorem 13.
The strategy profileσ
∗ is a DE of G
n if and only if (12)
∑
s
1
,
…
,
s
n
∈
S
∏
j
∈
I
σ
j
∗
s
j
u
i
s
1
,
…
,
s
n
=
max
s
-
i
∈
S
-
i
⁡
∑
s
i
∈
S
i
σ
i
∗
s
i
u
i
s
1
,
…
,
s
n
,
∀
i
∈
I
.Proof.
From (3) and (6), σ
∗ is a DE if and only if(13)
u
i
σ
∗
=
m
a
x
σ
-
i
∈
Δ
S
-
i
u
i
σ
i
∗
,
σ
-
i
=
m
a
x
σ
-
i
∈
Δ
S
-
i
∑
s
-
i
∈
S
-
i
σ
-
i
s
-
i
u
i
σ
i
∗
,
s
-
i
,
∀
i
∈
I
.Fix i
∈
I and let s
^
-
i maximize u
i
σ
i
∗
,
s
-
i over S
-
i. This maximum exists since u
i
(
σ
i
∗
,
s
-
i
) is continuous in s
-
i on the closed and bounded set S
-
i. Then by inspection, max
σ
-
i
∈
Δ
S
-
i
⁡
∑
s
-
i
∈
S
-
i
σ
-
i
(
s
-
i
)
u
i
(
σ
i
∗
,
s
-
i
) on the right side of (13) is maximized over σ
-
i
(
s
-
i
)
∈
Δ
S
-
i when σ
-
i
(
s
-
i
)
=
∏
j
∈
I
-
i
σ
j
(
s
j
)
=
1 for s
-
i
=
s
^
-
i and σ
-
i
(
s
-
i
)
=
0 for s
-
i
≠
s
^
-
i. Hence (14)
u
i
σ
∗
=
max
s
-
i
∈
S
-
i
⁡
u
i
σ
i
∗
,
s
-
i
,
∀
i
∈
I
,and (12) follows from (4) and (14).For a givenσ
∗ and ∀
i
∈
I, (12) can also be checked by total enumeration in O
(
N
) to determine if σ
∗ is a DE. Hence the problem of computing a DE for G
n is also a member of the complexity class NP. Nonetheless, for n
>
2, using (12) to obtain a DE or else determine that one does not exist is computationally harder than using (11) to find an NE. For DEs, the maximization for each i
∈
I on the right side of (12) is over S
-
i, as opposed to being over S
i in (11) for NEs. This increased difficulty results from the fact that determining a DE σ
∗ from (6) requires that the n
-
1 components σ
-
i
∗ for each of the n maximizations of (6) must match, whereas in (5) only the single component σ
i
∗ for all the n maximizations of (5) must match. Thus it appears more likely for the DE computational problem to be NP-complete than the NE computational problem. Theorem 11 further suggests this fact since stringent conditions are required there to guarantee the existence of a DE, whereas an NE always exists. Indeed, it is next shown that a DE may not exist.


## 5. Mutual Cooperation Impossibility Theorem

The following result establishes that mutual cooperation in the form of a DE may be impossible when the number of players is greater than two. As noted above, a DE always exists whenn
=
2. For n
>
2, however, existence depends on the payoff matrix.Theorem 14.
For everyn
>
2 there exists a game G
n
=
(
I
,
(
S
i
)
i
∈
I
,
(
u
i
)
i
∈
I
) with no DE.Proof.
The result is first proved forn
=
3. Consider a game G
3 with the payoff matrix P
3 of Table 2, where Player 1 has pure strategies S
1
=
{
s
1
,
t
1
}, Player 2 has pure strategies S
2
=
{
s
2
,
t
2
}, and Player 3 has pure strategies S
3
=
{
s
3
,
t
3
}. For simplicity, write σ
1
(
s
1
)
=
p
1 and σ
1
(
t
1
)
=
p
2 for Player 1, σ
2
(
s
2
)
=
q
1 and σ
2
(
t
2
)
=
q
2 for Player 2, and σ
3
(
s
3
)
=
r
1 and σ
3
(
t
3
)
=
r
2 for Player 3.
Assume thatG
3 has a DE σ
∗
=
(
σ
1
∗
,
σ
2
∗
,
σ
3
∗
). Then it follows from (6) that there exist p
i
∗, q
i
∗, r
i
∗, i
=
1,2, such that(15)
u
1
σ
∗
=
p
1
∗
q
1
∗
r
1
∗
+
p
2
∗
q
2
∗
r
2
∗
=
max
q
i
,
r
i
⁡
p
1
∗
q
1
r
1
+
p
2
∗
q
2
r
2
:
q
1
+
q
2
=
1
;
r
1
+
r
2
=
1
;
q
1
,
q
2
,
r
1
,
r
2
≥
0
,
(16)
u
2
σ
∗
=
p
1
∗
q
1
∗
r
1
∗
+
p
2
∗
q
2
∗
r
2
∗
=
max
p
i
,
r
i
⁡
p
1
q
1
∗
r
1
+
p
2
q
2
∗
r
2
:
p
1
+
p
2
=
1
;
r
1
+
r
2
=
1
;
p
1
,
p
2
,
r
1
,
r
2
≥
0
,
(17)
u
3
σ
∗
=
p
1
∗
q
1
∗
r
2
∗
+
p
2
∗
q
2
∗
r
1
∗
=
max
p
i
,
q
i
⁡
p
1
q
1
r
2
∗
+
p
2
q
2
r
1
∗
:
p
1
+
p
2
=
1
;
q
1
+
q
2
=
1
;
p
1
,
p
2
,
q
1
,
q
2
≥
0
.Solving the maximization in (15) yields the only possible solutions q
i
∗, r
i
∗, i
=
1,2, for (15) as follows.
Ifp
1
∗
>
p
2
∗, the solution is(18)
q
1
∗
=
r
1
∗
=
1
q
2
∗
=
r
2
∗
=
0
.If p
1
∗
<
p
2
∗, the solution is(19)
q
1
∗
=
r
1
∗
=
0
q
2
∗
=
r
2
∗
=
1
.If p
1
∗
=
p
2
∗
=
1
/
2, the two solutions are(20)
q
1
∗
=
r
1
∗
=
1
q
2
∗
=
r
2
∗
=
0
,as well as(21)
q
1
∗
=
r
1
∗
=
0
q
2
∗
=
r
2
∗
=
1
.Equations (18)–(21) therefore require that any DE in (6) must satisfy(22)
q
i
∗
,
r
i
∗
∈
0,1
,
i
=
1,2
.
Next utilizing (22) to solve the maximization in (16) yields the only two possible solutions p
i
∗, r
i
∗, i
=
1,2, for (16) as follows. If q
1
∗
=
1 and q
2
∗
=
0, the solution is(23)
p
1
∗
=
r
1
∗
=
1
p
2
∗
=
r
2
∗
=
0
.If q
1
∗
=
0 and q
2
∗
=
1, the solution is(24)
p
1
∗
=
r
1
∗
=
0
p
2
∗
=
r
2
∗
=
1
.Hence (22)–(24) require that (25)
p
i
∗
,
q
i
∗
,
r
i
∗
∈
0,1
,
i
=
1,2
.
Thus from (18)–(25), the only two possible solutions p
i
∗
,
q
i
∗
,
r
i
∗, i
=
1,2, jointly solving the maximizations in (15) and (16) are(26)
p
1
∗
=
q
1
∗
=
r
1
∗
=
1
p
2
∗
=
q
2
∗
=
r
2
∗
=
0
,as well as(27)
p
1
∗
=
q
1
∗
=
r
1
∗
=
0
p
2
∗
=
q
2
∗
=
r
2
∗
=
1
.But using (25) to solve the maximization in (17) gives the only two possible solutions p
i
∗
,
q
i
∗
,
r
i
∗
,
i
=
1,2, solving the maximization in (17) to be(28)
p
1
∗
=
q
1
∗
=
r
2
∗
=
1
p
2
∗
=
q
2
∗
=
r
1
∗
=
0
,as well as(29)
p
1
∗
=
q
1
∗
=
r
2
∗
=
0
p
2
∗
=
q
2
∗
=
r
1
∗
=
1
.It now follows that the only possible solutions (26) and (27) for (15) and (16) differ from the only possible solutions (28) and (29) for (17), in contradiction to the assumption that G
3 has a DE. Hence G
3 does not have a DE, and the theorem is true for n
=
3.
Forn
>
3 we generalize G
3 to a game G
n with no DE. Let S
i
=
{
s
i
,
t
i
}, i
=
1
,
…
,
n, and let the von Neumann-Morgenstern utility vector u on S be(30)
u
s
1
,
s
2
,
…
,
s
n
-
1
,
s
n
=
1,1
,
…
,
1,0
,
u
s
1
,
s
2
,
…
,
s
n
-
1
,
t
n
=
0,0
,
…
,
0,1
,
u
t
1
,
t
2
,
…
,
t
n
-
1
,
t
n
=
1,1
,
…
,
1,0
,
u
t
1
,
t
2
,
…
,
t
n
-
1
,
s
n
=
0,0
,
…
,
0,1
,
u
s
=
0,0
,
…
,
0,0
o
t
h
e
r
w
i
s
e
.Assume that G
n has a DE σ
∗
=
(
σ
1
∗
,
…
,
σ
n
∗
). In a manner similar to that giving equations (26) and (27) for n
=
3, it can be shown from (30) that the joint maximizations for Players 1
,
…
,
n in (6) yield the only possible two solutions (31)
σ
i
∗
s
i
=
1
σ
i
∗
t
i
=
0
,for 1
,
…
n, and(32)
σ
i
∗
s
i
=
0
σ
i
∗
t
i
=
1
,for 1
,
…
n. However, in a manner similar to that giving (28) and (29) for n
=
3, it can also be shown from (30) that the maximization for Player n in (6) yields the only possible two solutions(33)
σ
1
∗
s
1
=
⋯
=
σ
n
-
1
∗
s
n
-
1
=
σ
n
∗
t
n
=
1
σ
1
∗
t
1
=
⋯
=
σ
n
-
1
∗
t
n
-
1
=
σ
n
∗
s
n
=
0
,as well as(34)
σ
1
∗
s
1
=
⋯
=
σ
n
-
1
∗
s
n
-
1
=
σ
n
∗
t
n
=
0
σ
1
∗
t
1
=
⋯
=
σ
n
-
1
∗
t
n
-
1
=
σ
n
∗
s
n
=
1
.Since (31) and (32) contradict (33) and (34), G
n has no DE, and the proof is complete.Table 2
Payoff matrix forG
3.
Player 3
Player 1
s
3
t
3
Player 2
Player 2
s
2
t
2
s
2
t
2
s
1
(1, 1, 0)
(0, 0, 0)
(0, 0, 1)
(0, 0, 0)
t
1
(0, 0, 0)
(0, 0, 1)
(0, 0, 0)
(1, 1, 0)Theorem14 states that mutually cooperative behavior as defined by the DE cannot always be achieved for three or more players, no matter how the strategies are selected by the players or for the players. The result is quite intuitive. Depending on the payoff matrix, it is not always possible for every player to accommodate every other player when n
>
2.


## 6. Conclusions

The Berge equilibrium has been extended to a mixed dual equilibrium for the Nash equilibrium. In this duality, NEs embody selfishness for all players, as opposed to selflessness for DEs. The two concepts are closely related mathematically, however. Relabeling each player in a DE yields an NE for the original payoff matrix, from which it follows that a game has at least as many NEs as DEs. But an NE always exists for anyn
=
1,2
,
3
,
…, while for n
>
2 a DE may not exist—even on the average in the long run, even if the players try to be selfless. Mutual cooperation thus differs from the notion of compromise as defined in [16], which exists for any n. In particular, for a given payoff matrix, mutual cooperation is not always possible for strictly mathematical reasons as a consequence of sociological information about the players reflected in their joint von Neumann-Morgenstern utilities. Because of such issues, the DE computational problem appears more difficult than the NE one.



---

*Source: 647246-2015-09-15.xml*