Strategic complementarities and nested potential games∗
Hiroshi Uno†
ISER, Osaka University
E-mail: uno@iser.osaka-u.ac.jp
First Version: August 1, 2008; This Version: January 27, 2009

Abstract
This paper shows that every ﬁnite game of weak strategic complementarities is
a nested pseudo-potential game if the action set of one player is multi-dimensional
and the action sets of the others are one-dimensional; the implication does not hold,however, if the action sets of more than two players are multi-dimensional. Moreover,the paper proposes a new class of games of nested strategic complementarities thatgeneralize the games of strategic complementarities and the nested potential games.
Journal of Economic Literature Classiﬁcation Numbers: C72, C73
Key words : strategic complementarities, nested potential games.

1

Introduction

This paper investigates a relationship between games of strategic complementarities andnested potential games, and proposes a new class of games that generalize those two classesof games.
∗

I am grateful to my supervisors Masaki Aoyagi and Atsushi Kajii for their instruction and encouragement. I also thank In-Koo Cho, Ori Haimanko, Mamoru Kaneko, Jeroen Swinkels, and the participants at
Summer Workshop on Economic Theory 2008 at Hokkaido University and the 5th Pan-Paciﬁc Conferencein Game Theory at The University of Auckland for helpful comments.
†
Correspondent: Institute of Social and Economic Research, Osaka University, 6-1 Mihogaoka, Ibaraki,
Osaka 567-0047, Japan1

Games of strategic complementarities are games where, if her competitors turn moreaggressive, an optimal reaction of a player is to become more aggressive as well. Many
economic models belong to this class.1 In the literature, various versions of strategic complementarities have been proposed and analyzed.2 The weakest version of “strategic complementarities” is given by the weak strategic complementarities discussed in Dubey et al.
(2006).
On the other hand, since Moderer and Shapley (1996), various versions of potential
games also have been proposed and analyzed.3 These potential games have in common an
attractive feature that every maximizer of a potential, a real valued function over the setof action proﬁles, is a (pure) Nash equilibrium of the game. Uno (2007a) shows that the
weakest version of potential games is the nested pseudo-potential games.
These two classes of games are useful at the following meanings: whenever we analyze
a strategic situation as a game, we face the issue of the existence and identiﬁcation of a(pure) Nash equilibrium. We can provide an aﬃrmative answer to the existence question
if the game has the structure of strategic complementarities or a potential function: if thegame has strategic complementarities or a potential function, there exists a (pure strategy)
Nash equilibrium in the game. If the game has strategic complementarities, a best response
path from the greatest (least) action proﬁle converges to an equilibrium; if the game has apotential function, a maximizer of the function is an equilibrium.
This paper shall show the followings: ﬁrst, we will show that every ﬁnite game ofstrategic complementarities is a nested pseudo-potential game if the action sets of two or
more players are multi-dimensional (Theorem 10). Next, we will illustrate that strategic
complementalities do not necessarily imply the existence of a nested potential if the action

1

See Topkis (1998) and Vives (1999) in detail.
For example, games of strategic complementarities are including supermodular games introduced by
Topiks (1979) and quasi-supermodular games introduced by Milgrom and Shannon (1994).
3
For example, exact potentials, weighted potentials, ordinal potentials, generalized ordinal potentials
are introduced in Monderer and Shapley (1996); (ordinal) best response potentials in Voorneveld (2000);
pseudo-potentials in Dubey et al. (2006); best response potentials and better response potentials in Morrisand Ui (2004); generalized potentials, monotone potentials, and local potentials in Morris and Ui (2005);
iterated potentials in Oyama and Tercieux (2004); nested best response potentials in Uno (2007b); and so
on.
2

2

sets of two or more players are multi-dimensional (Example 19). Finally, we will propose
a new class of games which generalizes games of weak strategic complementarities andnested potential games (Deﬁnition 24), and show that there exists a pure strategy Nashequilibrium in such games (Corollary 25).

2Preliminaries

Let X be a ﬁnite subset of m-dimensional Euclidean space. The inequality x ≥ y meansxi ≥ yi for each i, while x > y means x ≥ y and there exists i such that xi > yi .
For x, y ∈ X, let inf X {x, y} := sup{z ∈ X|z ≤ x, z ≤ y} denote the least upper boundfor x and y in X, and let supX {x, y} := inf{z ∈ X|z ≥ x, z ≥ y} denote the greatest lower
bound for x and y in X.
A set X is a lattice if X contains the least upper bound and the greatest lower boundof each pair of its elements, i.e., for each x, y ∈ X, inf X {x, y} ∈ X and supX {x, y} ∈ X.
Tarski (1955) showed that the collection of ﬁxed points of an increasing function from anonempty ﬁnite lattice into itself is a nonempty lattice, and he gave the form of the greatest
ﬁxed point and the least ﬁxed point:4
Theorem 1 (Tarski, 1955) Suppose that f is an increasing function from a nonempty
finite lattice X to X. Then, the set of fixed points of f in X is nonempty, sup{x ∈ X|x ≤f (x)} is the greatest fixed point, and inf{x ∈ X|x ≥ f (x)} is the least fixed point.

3

Strategic Complementarities

A strategic form game consists of a ﬁnite player set N = {1, . . . , n}, an action set Ai for∏
i ∈ N , and the payoﬀ function gi : A → R for i ∈ N , where A := i∈N Ai . Since we ﬁx
the set A of action proﬁles, we denote a strategic form game (N, (Ai )i∈N , (gi )i∈N ) simply
by gN := (gi )i∈N . For notational convenience, we write a = (ai )i∈N ∈ A; for i ∈ N ,4

In fact, Tarski (1955) provides the ﬁxed point theorem of an increasing function on a complete lattice
instead of a ﬁnite lattice.

3

∏
A
and
a
=
(a
)
∈
A
;
and
for
T
⊆
N
,
A
=
j
−i
j
j̸
=
i
−i
T
j̸=i
i∈T Ai , aT = (ai )i∈T ∈ AT ,∏A−T = i∈N \T Ai , and a−T = (ai )i∈N \T ∈ A−T . For each T ⊆ N , for any a−T ∈ A−T , let
A−i =

∏

gN |a−T denote the game where the action proﬁle of players outside T is ﬁxed to a−T .
Since Topkis (1979), various notions of strategic complementarities have been introduced.5 Among them, the weakest notion is the game of weak strategic complementarities.
A game has weak strategic complementarities if, for each player, there exists a nondecreasing best-response selection:
Deﬁnition 2 A game gN is a finite game of weak strategic complementarities if, for eachi ∈ N , Ai ⊂ Rmi is a ﬁnite lattice,6 where mi ∈ N, and there exists a function bi : A−i → Aisuch that
1. bi is i’s best-response selection: bi (a−i ) ∈ arg maxai ∈Ai gi (ai , a−i ) for all a−i ∈ A−i ,and
2. bi is increasing with a−i : bi (a−i ) ≤ bi (a′−i ) whenever a−i < a′−i .

4Nested Potential GamesLet gN be a strategic form game. Beginning with Monderer and Shapley (1996), various
notions of potential games have been proposed. Among them, one of the weakest notions
is the nested pseudo-potential games introduced in Uno (2007a). To introduce the nested
pseudo-potential games, we introduce the pseudo-potential games proposed by Dubey etal.(2006). A pseudo-potential of game gN is a real valued function f on the set A of action
proﬁles such that, for each player i, i’s best-response against the other players’ actions a−iin the alternative game where i’s payoﬀ function is given by f is that in the original gamegN :5For example, the supermodular games introduced by Topkis (1979), the games of strategic complementarities introduced by Bulow et al. (1985), the quasi-supermodular game introduced by Milgrom andShannon, and so on.
6
We can also consider a version of games with compact action sets. In the version, it is diﬃcult to show
our main result hold, which we will discuss in Remark 20.

4

Deﬁnition 3 (Dubey et al., 2006) A function f : A → R is a pseudo-potential of gN
if, for each i ∈ N ,arg max f (ai , a−i ) ⊆ arg max gi (ai , a−i )ai ∈Aiai ∈Ai(1)

for all a−i ∈ A−i . If gN has a pseudo-potential, gN is called a pseudo-potential game.7
We say that an action proﬁle a∗ is a pseudo-potential maximizer of gN if f (a∗ ) ≥ f (a)for all a ∈ A.
Dubey et al. (2006) showed that a pseudo-potential maximizer, if it exists, is a Nashequilibrium of the underlying game:
Proposition 4 (Dubey et al., 2006) If gN is a pseudo-potential game with a pseudopotential maximizer a∗ , then a∗ is a Nash equilibrium of gN .
If action sets are ﬁnite, every pseudo-potential game possesses a pure strategy Nashequilibrium, since there exists a maximizer of a function whose domain is ﬁnite.
Corollary 5 (Dubey et al., 2006) Every pseudo-potential game with finite action sets
possesses a pure strategy Nash equilibrium.
We shall extend Proposition 4 by introducing a weaker notion of potential where a‘pseudo-potential’ is considered for each subset of players instead of the entire set. For apartition T of N , we deﬁne the partition T pseudo-potentials as follows:
Deﬁnition 6 (Uno, 2007a) Let T be a partition of N . A partition T pseudo-potentialof gN is a tuple (T , (AT )T ∈T , (fT )T ∈T ), where, for each T ∈ T , fT : A → R satisﬁes that,for each i ∈ T ,arg max fT (ai , a−i ) ⊆ arg max gi (ai , a−i )ai ∈Aiai ∈Ai7

If the inclusion of (1) can be replaced by the equality, f is called an (ordinal)best-response potential,
which is introduced in Voorneveld (2000). The pseudo-potentials generalize the (ordinal) best-response
potentials. Morris and Ui (2004, 5) also introduced alternative best-response potentials, which are specialclasses of (ordinal) best-response potentials of Voorneveld (2000) and the pseudo-potentials in Dubey etal. (2006). See Morris and Ui (2004) for more discussion of this notion. We can apply the analogous
arguments in this section to these best-response potentials of Morris and Ui (2004).

5

for all a−i ∈ A−i .
We denote such a partition T pseudo-potential (T , (AT )T ∈T , (fT )T ∈T ) by f T := (fT )T ∈T
since action sets (AT )T ∈T can be derived from the partition T of N and the set A of action
proﬁles in the original game gN .8
Notice that we can regard each T -pseudo-potential f T as a strategic form game, where
T is the player set; for each T ∈ T , AT is the action set of T ; and for each T ∈ T , fT is the
payoﬀ function of T . The idea of the nested pseudo-potential games is to construct suchgames iteratively for a nested sequence of partitions:Deﬁnition 7 (Uno, 2007a) A function f : A → R is a nested pseudo-potential of gN ifkKthere exist a positive integer K and a sequence (f T )K
k=1 = ((fT )T ∈T k )k=1 such thatkk K
• {T k }K
k=1 is a nested sequence of N : {T }k=1 is an increasingly coarser sequence ofpartitions of N with T 1 = {{i}|i ∈ N } and T K = {N };1• f T = (fT1 )T ∈T 1 is the original game gN : for each i ∈ N , f{i}(a) = gi (a) for all a ∈ A;
1

• for each k = 2, 3, . . . , K, f T(fTk−1 )T ∈T k−1 , where f

T k−1

k

= (fTk )T ∈T k is a T k -pseudo-potential of f T

k−1=

is regarded as a strategic form game as above: for eachT k ∈ T k and each T k−1 ∈ T k−1 with T k−1 ⊆ T k ,
arg

max

aT k−1 ∈AT k−1

fTk k (aT k−1 , a−T k−1 ) ⊆ arg

max

aT k−1 ∈AT k−1

fTk−1
k−1 (aT k−1 , a−T k−1 )for all a−T k−1 ∈ A−T k−1 ; and• fTK= (fNK ) is such that fNK (a) = f (a) for all a ∈ A.

A game that admits a nested pseudo-potential is called a nested pseudo-potential game.

The partition T pseudo-potential generalizes Monderer (2007)’s q-potential: a strategic form game gN
has a q-potential if and only if gN has a partition T -potential, where q refers to the number of elements
in T and the potential is meant to be the exact potential in Monderer and Shapley (1996). If gN is aq-potential game, then it has a partition T pseudo-potential such that the number of elements of T is q.
The converse is not true, since there is a pseudo-potential game without an exact potential.
86

We say that an action proﬁle a∗ is a nested pseudo-potential maximizer of gN if f (a∗ ) ≥f (a) for all a ∈ A.
The essential property shared by all existing versions of potential games is that maximizers of a potential function are Nash equilibria as in Proposition 4. The nested pseudopotential proposed here inherits this property. Indeed, Uno (2007a) showed that a nested
pseudo-potential maximizer, if it exists, is a Nash equilibrium of the underlying game:
Proposition 8 (Uno, 2007a) Let gN be a nested pseudo-potential games with a nested
pseudo-potential maximizer a∗ . Then, a∗ is a Nash equilibrium of gN .
Proposition 8 implies the following corollary.
Corollary 9 (Uno, 2007a) Every nested potential game with finite action sets possesses
a pure strategy Nash equilibrium.

5

Nested Potentials in Games of Strategic Complementarities

This section shows that games of weak strategic complementarities are nested pseudopotential games if the action set of one player is multi-dimensional and the action sets of
the others are one-dimensional.9
Theorem 10 Let gN be a game of weak strategic complementarities, where Ai ⊂ Rm forsome unique player i ∈ N and for some m ∈ N, and Aj ⊂ R for any j ̸= i. Then gN is anested pseudo-potential game.
To prove the above theorem, we will use the following four facts.
Firstly, a game of weak strategic complementarities has a property that, for each subset
T of N , for any action a−T ∈ A−T of all players outside T , the Nash equilibrium of therestriction gN |a−T of gN is an increasing with respect to a−T :9As shown in Example 19, a game with strategic complementarities is not necessarily a nested potential
game when the action sets of more than one player is multi-dimensional.

7

Lemma 11 Let gN be a game of weak strategic complementarities. Let T be a subset of
N . For any a−T ∈ A−T , let gN |a−T be the restricted game by a−T . Then, there exists afunction eT : A−T → AT such that
1. eT is an equilibrium selection: eT (a−T ) is a pure strategy Nash equilibrium of gN |a−T
for any a−T ∈ A−T ; and2. eT (a−T ) is increasing with a−T : eT (a−T ) ≤ eT (a′−T ) whenever a−T < a′−T .
This lemma resembles the result from monotone comparative statics where a function
from a nonempty lattice into itself has an increasing ﬁxed point with the parameter. The
following proof is also similar to that of the monotone comparative statics in Milgrom andRoberts (1994) or Topkis (1998, p.41, Theorem 2.5.2).
Proof. See Appendix.
Secondly, in a pseudo-potential game, for each pure strategy Nash equilibrium, we canﬁnd a pseudo-potential such that a unique maximizer of the pseudo-potential is the Nashequilibrium:
Lemma 12 Let gN be a pseudo-potential game. If a∗ is a pure strategy Nash equilibriumof gN , then there exists a pseudo-potential f : A → R such that {a∗ } = arg maxa∈A f (a).
Proof. See Appendix.
Thirdly, we have the following characterization of partition pseudo-potentials by thedeﬁnition of the parition pseudo-potentials:
Lemma 13 (fT )T ∈T is a partition T pseudo-potential of gN if and only if, for each member
T of T , for any action a−T ∈ A−T of all players outside T , fT (·, a−T ) is a pseudo-potentialof the restricted game gN |a−T by a−T .
Finally, a ﬁnite two-person game of weak strategic complementarities has a pseudopotential. Indeed, Dubey et al. (2006) showed that a two-person ﬁnite game of weak strategic complementarities, where each action set is one-dimensional, has a pseudo-potential:1010

In fact, Dubey et al. (2006) showed that games with aggregators of weak strategic complementarities
or weak substitutes are pseudo-potential games.

8

Proposition 14 (Dubey et al, 2006) Let g{1,2} be a two-person finite game with A1 , A2 ⊂R. If g{1,2} has weak strategic complementarities, then it is a pseudo-potential game.
We extend Proposition 14 to the case where the action set of one player is multidimensional.
Proposition 15 Let g{1,2} be a finite two-person game with A1 ⊂ Rm , where m ∈ N, andA2 ⊂ R. If g{1,2} has weak strategic complementarities, then it is a pseudo-potential game.
Proof. See Appendix.
We prove Theorem 10 by applying Lemmas 11, 12, 13 and Proposition 15 iteratively.
The outline of the proof is followings: let gN be a game of weak strategic complementarities.
Firstly, by Lemma 13 and Proposition 15, we know there exists a partition {{1, 2}, 3, . . . , n}pseudo-potential of gN . Next, by Lemmas 11 and 12, in particular, we can ﬁnd a partition{{1, 2}, 3, . . . , n} pseudo-potential f {{1,2},3,...,n} such that a best-response of representative
agent {1, 2} is increasing with a−{1,2} . Then, we can regard f {{1,2},3,...,n} as a games of weakstrategic complementarities. Moreover, by applying Lemmas 11, 12, 13 and Proposition
15, we have a partition {{1, 2, 3}, . . . , n} pseudo-potential f {{1,2,3},...,n} of f {{1,2},3,...,n} suchthat f {{1,2},3,...,n} is a game of weak strategic complementarities, and so on. Finaly, we canﬁnd a partition {{1, 2, . . . , n}} pseudo-potential (f {{1,2,...,n}} ) of f {{1,2,...,n−1},n} . and thus,
we have a nested pseudo-potential f = f {{1,2,...,n}} .
Proof of Theorem 10. See Appendix.

9

6

ExamplesWhen the action set of a single player is allowed
multi-dimensional, in what follows, we show by way
of examples that the relationship among strategic
complementarities, a pseudo potential and a nested
pseudo potential is given as in Figure 1.
As mentioned in Proposition 14, Dubey et al. Figure 1: Strategic complementari(2006) show that two person games of weak strate- ties and nested potential games whengic complementarities is a pseudo-potential game. the action set of one player is multiHowever, games with more than two players of weak dimensional and the action sets ofstrategic complementarities may not be a pseudo- the others are one-dimensional
potential game as in the following example.
Example 16 Consider the three-person game g{1,2,3} in Table 1, where player 1 chooses
the row, player 2 chooses the column, and player 3 chooses the matrix.
10
1
0 1, 0, 0 0, 1, 0
1 0, 0, 1 4, 4, 4

00
1
0 4, 4, 4 0, 0, 1
1 0, 1, 0 1, 0, 0

Table 1: (g1 , g2 , g3 )We can show that g{1,2,3} has weak strategic complementarities.
However, this game is not a pseudo-potential game. Indeed, note that g{1,2,3} has astrict best-response cycle (1, 0, 0) → (1, 0, 1) → (0, 0, 1) → (0, 1, 1) → (0, 1, 0) → (1, 1, 0) →(1, 0, 0). Since pseudo-potential games cannot have strict best-response cycles as shown by
Schipper (2004), this game is not a pseudo-potential game. On the other hand, g{1,2,3} is2
1
a nested pseudo-potential game. Indeed, (f{1,2}, f{3}) given in Table 2 is a {{1, 2}, {3}}1
pseudo-potential of g{1,2,3} , where f{3}(·) = g3 (·).
2
1
Regarding the {{1, 2}, {3}}-pseudo-potential (f{1,2}, f{3}) as a strategic form game, we can221show that (f{1,2,3}) deﬁned in Table 3 is a {{1, 2, 3}}-pseudo-potential of (f{1,2}, f{3}). Thus10(0, 0)(0, 1)(1, 0)(1, 1)

0
3, 4
0, 1
2, 0
1, 0

1
1, 0
2, 0
0, 1
3, 4

(0, 0)(0, 1)(1, 0)(1, 1)

1
1
Table 2: (f{1,2}, f{3}
)

a3
2
1
0
0

1
0
0
1
2

2
Table 3: f{1,2,3}
or fg{1,2,3} is a nested pseudo-potential game.
A pseudo-potential game may not have strategic complementarities as in the following
example.
Example 17 Consider the three-person game g{1,2,3} in Table 5, where player 1 chooses
the row, player 2 chooses the column, and player 3 chooses the matrix.
101
2
0 1, 1, 1 1, 0, 1 0, 0, 0
1 1, 0, 1 0, 0, 0 1, 0, 10012
0 0, 0, 0 1, 1, 0 0, 0, 1
1 0, 0, 0 0, 0, 1 1, 1, 0

Table 4: g{1,2,3} is a pseudo-potential without weak strategic complementarities
We can show that g{1,2,3} has a pseudo-potential f in Table 5. We can also show thatg{1,2,3} does not have weak strategic complementarities.
1 0 1 20 4 3 01 1 0 30 0 1 20 0 2 11 0 1 2

Table 5: a pseudo-potential f of g{1,2,3}

The following game, which appeared in Uno (2007a), strategic complementarities or apseudo-potential game but it is a nested pseudo-potential game.
Example 18 (Uno, 2007a) Consider the three-person game g{1,2,3} in Table 6, where
player 1 chooses the row, player 2 chooses the column, and player 3 chooses the matrix;

11

players 1 and 2 have identical interests, player 3’s payoﬀ is the same as others when player
1 chooses a1 , but is reversed otherwise as in the matching pennies game.
00
1
03, 3, 30, 0, 01 −1, −1, 1 1, 1, −1

10
10 0, 0, 0
2, 2, 2
1 1, 1, −1 −1, −1, 1

Table 6: (g1 , g2 , g3 )Note that g{1,2,3} is not a game of strategic complementarities. Note also that g{1,2,3}
is not a pseudo-potential game. Indeed, g{1,2,3} has a strict best-response cycle (1, 0, 0) →(1, 1, 0) → (1, 1, 1) → (1, 0, 1) → (1, 0, 0). Since pseudo-potential games cannot have strict
best response cycles as shown by Schipper (2004), the game is not a pseudo-potential game.
However, we can show that g{1,2,3} is a nested pseudo-potential game.
The next example demonstrates the failure of Proposition 14 when the each action setof more than one player is multi-dimensional.
Example 19 Consider the two-person game g{1,2} represented as Table 7, where A1 =A2 = {0, 1} × {0, 1}, player 1 chooses the row and the column, and player 2 chooses thematrix. We can show that game (g1 , g2 ) has weak strategic complementarities. But it(0, 0) 01
01, 1 0, 0
1
0, 0 0, 0(0, 1) 01
00, 0 0, 1
1
1, 0 0, 0(1, 0) 01
00, 0 1, 0
1
0, 1 0, 0(1, 1) 01
00, 0 0, 0
1
0, 0 1, 1

Table 7: (g1 , g2 )does not have a nested pseudo-potential. Indeed, there exists a strict best-response cycle((0, 1), (0, 1)) → ((1, 0), (0, 1)) → ((1, 0), (1, 0)) → ((0, 1), (1, 0)) → ((0, 1), (0, 1)). So, by
Schipper (2004), this game is not a pseudo-potential game.
Remark 20 Dubey et al. (2006) presented a more general version of Proposition 14 where
action sets are compact subsets of R, provided that, for each player i, i’s best-response
selection bi is continous on the set A−i of the other players’ action proﬁles additionally.
12But, we cannot immediately extend Theorem 10 to games with compact action sets.
This is because it is diﬃcult to guarantee that there exists a partition potential f {{1,2},3,...,n}of a game gN such that a best-response selection b{1,2} of representative agent {1, 2} iscontinous on the set A−{1,2} of action proﬁles of players outside {1, 2}, since game of weakstrategic complementarities does not always have a continuous increasing equilibrium selection.

7

A Generalization of Strategic Complementarities and
Nested Potential GamesIf the action sets of two or more players are multi-dimensional, there is no relationshipbetween the games of weak strategic complementarities and the nested potential games, as
shown in Example 18 and Example 19. This section proposes a new class of games which
possess a pure strategy Nash equilibrium. To do so, we introduce the nested partition
pseudo-potential. A nested partition pseudo-potential is a partition pseudo-potential when
we give up the construction of the nested pseudo-potential halfway:
Deﬁnition 21 Let T be a partition of N . A tuple f T = (T , (AT )T ∈T , (fT )T ∈T ) is a nested
partition T pseudo-potential of gN , if there exist a positive integer K and a sequencekK(f T )K
k=1 = ((fT )T ∈T k )k=1 such thatk1
• (T k )K
k=1 is an increasingly coarser sequence of partitions of N with T = {{i}|i ∈ N }and T K = T ;1• f T is regarded as the original game gN : for each i ∈ N , f{i}(a) = gi (a) for all a ∈ A;
1

• fT

K

= f T : for any T ∈ T , fTK (a) = fT (a) for all a ∈ A.

• for each k = 2, 3, . . . , K, f T(fTk−1 )T ∈T k−1 , where f T

k−1k= (fTk )T ∈T k is a T k -pseudo-potential of f T

k−1=

is regarded as a strategic form game as above: for each13

T k ∈ T k and each T k−1 ∈ T k−1 with T k−1 ⊆ T k ,
arg

max

aT k−1 ∈AT k−1

fTk k (aT k−1 , a−T k−1 ) ⊆ arg

max

aT k−1 ∈AT k−1

fTk−1
k−1 (aT k−1 , a−T k−1 )for all a−T k−1 ∈ A−T k−1 .
If a nested partition potential of a strategic form game gN has a pure strategy Nashequilibrium a∗ , then the game gN also have a pure strategy Nash equilibrium a∗ :Theorem 22 Let T be a partition of N . Let f T be a nested partition T pseudo-potentialof a strategic form game gN . If an action profile a∗ ∈ A is a pure strategy Nash equilibriumof f T , then a∗ is also a pure strategy Nash equilibrium of gN .
We can prove Theorem 22 by applying Lemma 2.9 of Uno (2007a) iteratively.
We provide a necessary condition for the existence of a nested partition T pseudopotentials. We use this condition to demonstrate that a game does not have a nested
pseudo-potential below.
If a game has a nested partition T pseudo-potential and the number of elements of T isL, then we can ﬁnd a sequence of partitions which reaches T from {i|i ∈ N } in n − L steps
in the following way: at each step k, only two elements T1k and T2k of the partition T k areunited; and, for any action proﬁle aT2k of members of T2k , there exists a pure strategy Nashequilibrium selection eT1k (aT2k ) of f |a−T k and, for any action proﬁle aT1k of T1k ’s members,
2

there exists a pure strategy Nash equilibrium selection eT2k (aT1k ) of f |a−T k such that a cycle
1by eT1k and eT2k does not happen:
Lemma 23 If a game gN has a nested partition T pseudo-potential and the number ofn−Lsuch thatelements of T is L, then there exists a sequence of partitions (T k )k=11
= {{i}|i ∈• (T k )n−L
k=1 is an unit increasingly coarser sequence of partitions of N : T

N }, T n−L = T , and, for each k = 2, 3, . . . , n − L, there exist T1k , T2k ∈ T k such thatT k+1 \T k = {T1k ∪ T2k }\{T1k , T2k }; and14

• for each k = 2, 3, . . . , n−L and for each j = 1, 2, there exists a function eTjk : A−Tjk →ATjk such that– eTjk is an equilibrium selection: for any a−Tjk ∈ A−Tjk , eTjk (a−Tjk ) is a pure strategy
Nash equilibrium of gN |a−T k , andj– for any a−T1k ∪T2k ∈ A−T1k ∪T2k and for any akl ∈ Akl , where l ∈ {1, 2} with l ̸= j,eTjk (eTlk (eTjk (aTlk , a−T1k ∪T2k ), a−T1k ∪T2k ), a−T1k ∪T2k ) ̸= eTjk (aTlk , a−T1k ∪T2k ).
Proof. See Appendix.
We introduce the special class of games with nested partition potential:
Deﬁnition 24 A game has nested weak strategic complementarities if there exist a partition T of N and a nested partition T pseudo-potential f T such that f T has weak strategic
complementarities.
Note that games of the nested weak strategic complementarities generalize the gamesof weak strategic complementarities and the nested potential games: indeed, it is clearthat every game of weak strategic complementarities is a game of nested weak strategic
complementarities; it is also clear that every nested potential game is a game of nested
weak strategic complementarities since we can regard one person game as game of weakstrategic complementarities, and any Nash equilibrium of f T is also a Nash equilibrium of
the original game by Theorem 23.
Corollary 25 below states that implies games of nested weak strategic complementarities
have a pure strategy Nash equilibrium. This result holds, since there exists a pure strategy
Nash equilibrium in games of weak strategic complementarities:
Corollary 25 If gN has nested weak strategic complementarities, then there exists a purestrategy Nash equilibrium of gN .
Even if a game has neither weak strategic complementarities nor a nested pseudopotential, it may have nested weak strategic complementarities, as shown in the following
15

example.
Example 26 Consider the three-person game g{1,2,3} represented as Table 8, where A1 =A2 = {0, 1, 2}, and A3 = {0, 1} × {0, 1}, player 1 chooses the row, player 2 chooses thecolumn, and player 3 chooses the matrix.
(0, 0)
0
1
2(1, 0)
01
2

01, 1, 10, 1, 00, 1, 000, 1, 00, 1, 01, 1, 01
1, 0, 00, 0, 00, 1, 010, 0, 10, 0, 01, 0, 0(0, 1)
0
1
2(1, 1)
01
2

2
1, 0, 00, 0, 00, 0, 020, 0, 10, 0, 01, 0, 001, 0, 00, 0, 10, 0, 10
1, 1, 00, 1, 00, 0, 01
1, 0, 00, 1, 00, 0, 01
1, 0, 00, 0, 10, 0, 12
1, 1, 00, 0, 00, 1, 020, 0, 00, 0, 1
1, 1, 1

Table 8: g{1,2,3}
We can show that game g{1,2,3} dose not have weak strategic complementarities. Moreover, g{1,2,3} has neither weak strategic complementarities nor a nested pseudo-potential.
Indeed, if a1 = 1, there exists a strict best-response cycle (1, 0, (0, 1)) → (1, 1, (0, 1)) →(1, 1, (1, 1)) → (1, 0, (1, 1)) → (1, 0, (0, 1)); and, if a2 = 1, there exists a strict bestresponse cycle (0, 1, (1, 0)) → (2, 1, (1, 0)) → (2, 1, (1, 1)) → (0, 1, (1, 1)) → (0, 1, (1, 0)).
So, (g1 , g2 , g3 ) has {{1, 2}, {3}}-pseudo-potential, but neither {{1}, {2, 3}}-pseudo-potential
nor {{2}, {1, 3}}-pseudo-potential by Lemma 23.
And, for any a3 , there exists no strict best-response cycle. But if a3 = (1, 0), g{1,2,3} |a3
has a unique pure strategy Nash equilibrium (a1 , a2 ) = (2, 0); and if a3 = (0, 1), g{1,2,3} |a3
has also a unique pure strategy Nash equilibrium (a1 , a2 ) = (0, 2). So, {{1, 2}, {3}}pseudo-potential must have a strict best-response cycle (2, 0, (1, 0)) → (2, 0, (0, 1)) →(0, 2, (0, 1)) → (0, 2, (1, 0)) → (2, 0, (1, 0)). By Lemma 23, {{1, 2}, {3}}-pseudo-potential
have not a pseudo-potential. That is, g{1,2,3} is not a nested pseudo-potential game.
2
1
However, g{1,2,3} has nested weak strategic complementarities. Indeed, (f{1,2}, f{3})
1given in Table 9 is a {{1, 2}, {3}}-pseudo-potential of g{1,2,3} , where f{3}(·) = g3 (·). Re1
1
garding the {{1, 2}, {3}}-pseudo-potential (f{1,2}, f{3}) as a strategic form game, we can

16

1
1
show that (f{1,2}, f{3}) has weak strategic complementarities. Thus, g{1,2,3} has nested

weak strategic complementarities.
(0, 0)
0
1
2(1, 0)
0
1
2

0
2, 1
1, 0
1, 0
0
1, 0
1, 0
2, 0

1
1, 0
0, 0
0, 0
1
0, 1
0, 0
1, 0

2
1, 0
0, 0
0, 0
2
0, 1
0, 0
1, 0

(0, 1)
0
1
2(1, 1)
0
1
2

0
1, 0
0, 1
0, 1
0
2, 0
1, 0
0, 0

1
2, 0
1, 0
0, 0
1
1, 0
0, 1
0, 1

2
3, 0
0, 0
1, 0
2
0, 0
0, 1
1, 1

1
1
, f{3})
Table 9: (f{1,2}

By Examples 18, 19 and 26, If the action setsof two or more players are multi-dimensional, therelationship among Nested strategic complementarities, strategic complementarities and nested potential games is as depicted in Figure 2.

Figure 2:

Nested strategic com-plementarities, strategic complemen-

8Concluding Remarks

tarities and nested potential games
when the action sets of two or more

This paper investigates the relationship between theplayers are multi-dimensional
games of weak strategic complementarities and thenested potential games. For this, we introduce a newclass of games generalizing games of weak strategic
complementarities and nested potential games.
This result suggests the following. If the action set of one player is multi-dimensional
and the action sets of the others are one-dimensional, it is suﬃcient to check whether thegame has a nested pseudo-potential. If the action sets of two or more players are multidimensional, we should check whether the game has a nested partition pseudo-potential or
weak strategic complementarities iteratively.

17Appendix: Proofs
Proof of Lemma 11. Suppose that gN is a game of weak strategic complementarities.
For each i ∈ N , let bi : A−i → Ai be i’s best-response selection such that bi (a−i ) ≤ bi (a′−i )whenever a−i < a′−i . Fix any T ⊆ N . For any a−T ∈ A−T , let bT (·, a−T ) : AT → AT
be the function deﬁned by bT (aT , a−T ) := (bi (aT \{i} , a−T ))i∈T for any aT ∈ AT . For any
a−T ∈ A−T , since bT (·, a−T ) is an increasing function, by Tarski’s ﬁxed point theorem(Theorem 1), there exists the greatest (least) ﬁxed point of bT (·, a−T ), i.e., the greatest(least) pure strategy Nash equilibrium of gN |a−T .
Pick any a−T , a′−T ∈ A−T with a−T < a′−T . Let eT (a−T ) and eT (a′−T ) be the greatest pure strategy Nash equilibria of gN |a−T and gN |a′−T , respectively. Because eT (a−T ) =bT (eT (a−T ), a−T ) and bT (eT (a−T ), a−T ) ≤ bT (eT (a−T ), a′−T ), we have eT (a−T ) ≤ bT (eT (a−T ), a′−T ).
By Theorem 1, sup{aT ∈ AT |aT ≤ bT (aT , a′−T )} is the greatest pure strategy Nash equilibrium of gN |a′−T . Thus, we have eT (a−T ) ≤ eT (a′−T ).

Proof of Proposition 15.

Suppose that g{1,2} has weak strategic complementarities.

Then, for i, j = 1, 2 with i ̸= j, there exists a function bi : Aj → Ai such that bi (aj ) ∈arg maxai ∈Ai gi (ai , aj ) for all aj ∈ Aj , and bi (aj ) ≤ bi (a′j ) whenever aj < a′j . Let A′1 be therange of b1 , i.e., A′1 := {a1 ∈ A1 | there exists a2 ∈ A2 such that a1 = b1 (a2 )}. Since A′1 islinearly ordered and ﬁnite, there exist a subset A1 of R and a bijection h from A′1 to A1
such that for each a1 , a′1 ∈ A′1 , a1 < a′1 if and only if h(a1 ) < h(a′1 ). Such Â1 exists by theproperty of b1 . Let ĝ1 : Â1 × A2 → R be the function deﬁned by ĝ1 (â1 , a2 ) = g1 (h−1 (â1 ), a2 )for all â1 ∈ Â1 and all a2 ∈ A2 .
Consider a two-person game (ĝ1 , g2 ) given by (ĝ1 , g2 ) := ({1, 2}, (Â1 , A2 ), (ĝ1 , g2 )). It
then follows that there exists player 1’s best-response selection b̂1 : A2 → Â1 such thatb̂1 (a2 ) ≤ b̂1 (a′2 ) whenever a2 < a′2 , since A′1 and Â1 are order isomorphic, b1 (a2 ) ∈ A′1 for any
a2 ∈ A2 , and b1 (a2 ) ≤ b1 (a′2 ) whenever a2 < a′2 . Since g{1,2} has strategic complementarities,
there exists also player 2’s best-response selection b̂2 : Â1 → A2 such that b̂2 (a1 ) ≤ b̂2 (a′1 )18whenever a1 < a′1 . Thus, (ĝ1 , g2 ) has weak strategic complementarities. By proposition 14,(ĝ1 , g2 ) has a pseudo-potential fˆ : Â1 × A2 → R.
Let c ∈ R be suﬃciently small so that c < min(â1 ,a2 )∈Â1 ×A2 fˆ(â1 , a2 ), which exists sinceÂ1 × A2 is ﬁnite.
Let f : A → R be a function such that, for all a1 ∈ A1 and all a2 ∈ A2 ,fˆ(h(a1 ), a2 ) if a1 ∈ A′1f (a1 , a2 ) =if a1 ∈ A1 \A′1 and a2 ∈ b2 (a1 )

c



 c−1

(2)

otherwise

We will show that f is a pseudo-potential of g{1,2} . Fix any a2 ∈ A2 . Pick any a∗∗
1 ∈′arg maxa1 ∈A1 f (a1 , a2 ). Then, a∗∗
1 ∈ A1 must hold by the choice of constant c in the con∗∗ˆ
struction of f . Since a∗∗
1 ∈ arg maxa1 ∈A′1 f (a1 , a2 ), we have h(a1 ) ∈ arg maxâ1 ∈Â1 f (â1 , a2 ).
′Since fˆ is a pseudo-potential of (ĝ1 , g2 ), we have h(a∗∗1 ) ∈ arg maxâ1 ∈Â1 ĝ1 (â1 , a2 ). Since A1∗∗′and Â1 are order isomorphic, we have a∗∗
1 ∈ arg maxa1 ∈A′1 g1 (a1 , a2 ). And, since a1 ∈ A1 , we′∗∗have g1 (a∗∗1 , a2 ) ≥ g1 (a1 , a2 ) for all a1 ∈ A1 \A1 . Thus, we have a1 ∈ arg maxa1 ∈A1 g1 (a1 , a2 ).
′∗∗Fix any a1 ∈ A1 . Pick any a∗∗
2 ∈ arg maxa2 ∈A2 f (a1 , a2 ). If a1 ∈ A1 , we have a2 ∈arg maxa2 ∈A2 g2 (a1 , a2 ), since fˆ is a pseudo-potential of (ĝ1 , g2 ). If a1 ∈ A1 \A′1 , we must∗∗have a∗∗2 ∈ b2 (a1 ) by the construction of f . Thus, we have a2 ∈ arg maxa2 ∈A2 g2 (a1 , a2 ).

Hence, f is a pseudo-potential of g{1,2} .

Proof of Lemma 12. Suppose that gN is a game with pseudo-potential f . Let a∗ be apure strategy Nash equilibrium of gN . Let c ∈ R be a suﬃciently large number such thatc > maxa∈A f (a). Deﬁne a function fˆ : A → R such that, for each a ∈ A,

fˆ(a) =

 c

if a = a∗ f (a)otherwise

Then, we have {a∗ } = arg maxa∈A fˆ(a). And, we can show that fˆ is also a pseudo-19potential of gN . Indeed, ﬁx any i ∈ N and any a−i ∈ A−i . If a−i ̸= a∗−i , we havearg maxai ∈Ai fˆ(ai , a−i ) = arg maxai ∈Ai f (ai , a−i ).

Since f is a pseudo-potential of gN ,arg maxai ∈Ai fˆ(ai , a−i ) ⊆ arg maxai ∈Ai gi (ai , a−i ). If a−i = a∗−i , we have {a∗i } = arg maxai ∈Ai fˆ(ai , a−i ).
Since a∗ is a Nash equilibrium, we have a∗i ∈ arg maxai ∈Ai gi (ai , a−i ). Thus we havearg maxai ∈Ai fˆ(ai , a−i ) ⊆ arg maxai ∈Ai gi (ai , a−i ). Hence fˆ is a pseudo-potential of gN .

Proof of Theorem 10.

Without loss of generality, we will assume that m1 ∈ N andmi = 1 for each i ̸= 1. Suppose that gN is a game of weak strategic complementarities. Wel: A → R such thatshall show that, for each l = 1, 2, . . . , n, there exists a function f{1,...,l}l−1
l1. (f{1,...,l}, gl+1 , . . . , gn ) is a {{1, . . . , l}, {l+1}, . . . , {n}}-pseudo-potential of (f{1,...,l−1}, gl , . . . , gn ),0, g1 , . . . , gn ) := (g1 , . . . , gn );where (f{0}2. there exists a function b{1,...,l} : A−{1,...,l} → A{1,...,l} with
• b{1,...,l} (a−{1,...,l} ) ∈ arg

max

a{1,...,l} ∈A{1,...,l}lf{1,...,l}(a{1,...,l} , a−{1,...,l} ) for all a−{1,...,l} ∈A−{1,...,l} , and• b{1,...,l} (a−{1,...,l} ) ≥ b{1,...,l} (a′−{1,...,l} ) whenever a−{1,...,l} > a′−{1,...,l} .
1
The proof proceeds by induction on l. First, when l = 1, let f{1}(·) := g1 (·). Then,1(f{1}, . . . , gn ) is a {{1}, . . . , {n}}-potential of (g1 , . . . , gn ). Moreover, since gN is a gameof weak strategic complementarities, there exists a function b{1} : A−{1} → A{1} with
1b{1} (a−{1} ) ∈ arg max f{1}(a{1} , a−{1} ) for all a−{1} ∈ A−{1} , and b{1} (a−{1} ) ≥ b{1} (a′−{1} )a{1} ∈A{1}whenever a−{1} > a′−{1} .

lSuppose that, for each l ≤ k − 1 ≤ n − 1, there exist functions f{1,...,l}: A → R andb{1,...,l} : A−{1,...,l} → A{1,...,l} such that the conditions 1 and 2 hold. We will show that therekexists such functions f{1,...,k}: A → R and b{1,...,k} : A−{1,...,k} → A{1,...,k} .
k−1
Fix any a−{1,...,k} ∈ A−{1,...,k} . Consider a restricted game (f{1,...,k−1}, gk , . . . , gn )|a−{1,...,k}by a−{1,...,k} . By the assumption of induction, there exists a function b{1,...,k−1} (·, a−{1,...,k} ) :Ak → A{1,...,k−1} with b{1,...,k−1} (ak , a−{1,...,k} ) ∈ arg

max
f k−1
(a{1,...,k−1} , ak , a−{1,...,k} )a{1,...,k−1} ∈A{1,...,k−1} {1,...,k−1}
for all ak ∈ Ak , and b{1,...,k−1} (ak , a−{1,...,k} ) ≥ b{1,...,k−1} (a′k , a−{1,...,k} ) whenever ak > a′k .
20And, since bk is player k’s best-response selection such that bk (a{1,...,k−1} , a−{1,...,k} ) ≥bk (a′{1,...,k−1} , a−{1,...,k} ) whenever a{1,...,k−1} > a′1,...,k−1 , we can regard the restricted gamek−1
(f{1,...,k−1}, gk , . . . , gn )|a−{1,...,k} by a−{1,...,k} as a two-person game of weak strategic com-plementarities, where N = {{1, . . . , k − 1}, {k}}, A{1,...,k} ⊂ Rm+k−1 , and Ak ⊂ R. By
k−1
Proposition 15, (f{1,...,k−1}, gk , gk+1 , . . . , gn )|a−{1,...,k} has a pseudo-potential.

Now, consider a restricted game gN |a−{1,...,k} for any a−{1,...,k} ∈ A−{1,...,k} . Since gN
has weak strategic complementarities, by Lemma 11, there exists an equilibrium selection
e{1,...,k} : A−{1,...,k} → A{1,...,k} of gN |a−{1,...,k} such that e{1,...,k} (a−{1,...,k} ) ≤ e{1,...,k} (a′−{1,...,k} )whenever a−{1,...,k} < a′−{1,...,k} .
k−1
For any a−{1,...,k} ∈ A−{1,...,k} , since (f{1,...,k−1}, gk , . . . , gn )|a−{1,...,k} has a pseudo-potential,kby Lemma 12, there exists a pseudo-potential f{1,...,k}(·, a−{1,...,k} ) : A{1,...,k} → R such thatke{1,...,k} (a−{1,...,k} ) is a unique maximizer of f{1,...,k}:{e{1,...,k} (a−{1,...,k} )} = arg

maxa{1,...,k} ∈A{1,...,k}kf{1,...,k}(a{1,...,k} , a−{1,...,k} ).

(3)

Recall that, for any partition T of N , gN has a partition T pseudo-potential if and only if,for each member T of T , for any a−T ∈ A−T , the restricted game gN |a−T by a−T is a pseudopotential game (Deﬁnition 3). For any partition T of N , recall that (fT )T ∈T is a partition T
pseudo-potential of gN if and only if, for each member T of T , for any a−T ∈ A−T , fT (·, a−T )kis a pseudo-potential of the restricted game gN |a−T by a−T . Thus, (f{1,...,k}, gk+1 , . . . , gn )k−1
is a {{1, . . . , k}, {k + 1}, . . . , {n}}-pseudo-potential of (f{1,...,k−1}, gk , gk+1 , . . . , gn ). Hence,kf{1,...,k}satisﬁes Condition 1.

Let b{1,...,k} : A−{1,...,k} → A{1,...,k} be the function deﬁned by b{1,...,k} (a−{1,...,k} ) :=e{1,...,k} (a−{1,...,k} ) for any a−{1,...,k} ∈ A−{1,...,k} . Then, b{1,...,k} satisﬁes Condition 2, since (3)holds and eT (a−{1,...,k} ) is increasing with a−{1,...,k} . Thus, gN is a nested pseudo-potential
game.

Proof of Lemma 23.

Suppose that gN has a nested partition T pseudo-potential and21

the number of elements of T is L. Then, it is clear that we can ﬁnd a sequence of partition
potentials such that, at each step k, only two elements of the partition T k are united, andthe sequence of partitions reaches T from {i|i ∈ N } in n − L steps. That is, there exists ak n−L
sequence (f T )n−L
k=1 such that (T )k=1 is an unit increasingly coarser sequence of partitions
kof N ; f T = gN ; f T
1

of f Tk−1

n−L= f T ; and, for each k = 2, 3, . . . , n − L, f T is a T k -pseudo-potentialk.

Fix any k = 2, 3, . . . , n − L, any j, l = 1, 2 with j ̸= l, and any a−Tj ∈ A−Tjk .
If a∗Tj ∈ arg maxaTj ∈ATj fTjk (aTj , a−Tj ), then a∗Tj is a pure strategy Nash equilibrium ofgN |a−T k . That is, we can regard a best-response of Tj against a−Tj as a pure stratj

egy Nash equilibrium of gN |−aT k . And, since, for each k = 2, 3, . . . , n − L, f T

k−1

has a

j

T k -pseudo-potential, f T

k−1

cannot have any strict best-response cycle as shown by Schip-per (2004). Hence, by Lemma 12, we must ﬁnd best-response selections eT1k : A−T1k →AT1k and eT1k : A−T2k → AT2k such that, for any a−T1k ∪T2k ∈ A−T1k ∪T2k and any akj ∈ Akj ,eTjk (eTlk (eTjk (aTlk , a−T1k ∪T2k ), a−T1k ∪T2k ), a−T1k ∪T2k ) ̸= eTjk (aTlk , a−T1k ∪T2k ).

References[1] Bulow, J., Geanakoplos, J. D. and P. D, Klemperer (1985) “Multimarket Oligopoly:
Strategic Substitutes and Complements,” Journal of Political Economy 93(3), 488-511.
[2] Dubey, P., O. Haimanko, and A. Zapechelnyuk (2006) “Strategic complements andsubstitutes, and potential games,” Games and Economic Behavior 54, 77-94.
[3] Milgrom, P., and J. Roberts (1994) “Comparing equilibria,” American Economic Review 84, 441-459.
[4] Milgrom, P., and C. Shannon (1994) “Monotone comparative statics,” Econometrica
62 (1), 157-80.
[5] Monderer, D. (2007) “Multipotential games,” in Twentieth International Joint Conference on Artificial Intelligence (IJCAI-07), 1422-1427.

22

[6] Monderer, D., and L. Shapley (1996) “Potential games,” Games and Economic Behavior 14, 124-143.
[7] Morris, S., and T. Ui (2004) “Best response equivalence,” Games and Economic Behavior 49, 260-287.
[8] Morris, S., and T. Ui (2005) “Generalized potentials and robust sets of equilibria,”
Journal of Economic Theory 124, 45-78.
[9] Schipper,

B.

C.

(2004)“Pseudo-potential

games,”

mimeo(availableat

http://citeseer.ist.psu.edu/705206.html).
[10] Tarski, A. (1955) “A lattice-theoretical ﬁxpoint theorem and its applications,” Pacific
Journal of Mathematics 65, 525-532.
[11] Topkis, D. M. (1998) “Supermodularity and complementarity, Princeton University
Press.
[12] Uno, H. (2007a) “Nested potential games,” Economic Bulletin 3 (17), 1-8.
[13] Uno, H. (2007b) “Nested potentials and robust equilibria,” mimeo (available at
http://1st.geocities.jp/potential funs/papers/nested-pot robust-eq.pdf).
[14] Vives, X. (1999) Oligopoly pricing: old ideas and new tools, MIT Press.
[15] Voorneveld, M. (2000) “Best-response potential games,” Economics Letters 66, 289295.

23