See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/46605951

Congestion Games and Potentials Reconsidered

Article  in  International Game Theory Review · November 2011

DOI: 10.1142/S0219198999000219 · Source: OAI

CITATIONS READS
53 238

5 authors, including:

Mark Voorneveld Giovanni Facchini

Stockholm School of Economics Erasmus University Rotterdam
94 PUBLICATIONS   974 CITATIONS    81 PUBLICATIONS   1,387 CITATIONS   

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Mark Voorneveld on 15 July 2014.

The user has requested enhancement of the downloaded file.

May 11, 2000 9:44 WSPC/151-IGTR 0010

International Game Theory Review, Vol. 1, Nos. 3 & 4 (1999) 283–299

c World Scientific Publishing Company

CONGESTION GAMES AND POTENTIALS RECONSIDERED

MARK VOORNEVELD∗ , PETER BORM, FREEK VAN MEGEN and STEF TIJS
Department of Econometrics and CentER, Tilburg University,
P.O. Box 90153, 5000 LE Tilburg, The Netherlands

GIOVANNI FACCHINI
Department of Economics, Stanford University, Stanford, CA 94305, USA

In congestion games, players use facilities from a common pool. The benefit that a player
derives from using a facility depends, possibly among other things, on the number of users
of this facility. The paper gives an easy alternative proof of the isomorphism between
exact potential games and the set of congestion games introduced by Rosenthal (1973).
It clarifies the relations between existing models on congestion games, and studies a
class of congestion games where the sets of Nash equilibria, strong Nash equilibria and
potential-maximising strategies coincide. Particular emphasis is on the computation of
potential-maximising strategies.

1. Introduction
In recent years, there has been a growing interest in the study of specific classes of
non-cooperative games for which there exist pure strategy Nash equilibria. This pa-
per deals with games derived from congestion models. In a congestion model, players
use several facilities — also called machines or (primary) factors — from a common
pool. The costs or benefits that a player derives from the use of a facility are, pos-
sibly among other factors, determined by the number of users of that same facility.
Congestion models can, for instance, be used to model the foraging behaviour
of a population of bees in a field of flowers. In deciding which flower to visit, each
insect will take into account the quantity of nectar available and the number of
bees already on the flower, because, as is intuitively clear, the more crowded the
source of nectar, the less food is available per capita. In economics, this kind of
problems is studied in the literature on local public goods, where it is common to
speak about “anonymous crowding” [cf. Wooders (1989)] to describe the negative
externality arising from the presence of more than one user of the same facility.
Another example is the problem faced by a set of unemployed workers who have to
decide where to emigrate to get a job. The attraction of different countries depends

∗ Corresponding author. E-mail: [email protected]. This author’s research is financially sup-

ported by the Netherlands Mathematics Research Foundation, part of the Netherlands Organiza-
tion for Scientific Research (NWO). Comments of the two referees are gratefully acknowledged.

283
May 11, 2000 9:44 WSPC/151-IGTR 0010

284 M. Voorneveld et al.

on the conditions of the local labor market and, on the other hand, a crowding-out
effect reduces the appeal of emigrating.
Rosenthal (1973) constitutes one of the pioneering papers on congestion games.
In his model, each player chooses a subset of facilities. The benefit associated with
each facility is a function only of the number of players using it. The payoff to a
player is the sum of the benefits associated with each facility in his strategy choice,
given the choices of the other players. Monderer and Shapley (1996) define exact po-
tential games, games where information concerning the Nash equilibria can be incor-
porated in a potential function, a single real-valued function on the strategy space.
Strategy profiles maximising the potential are Nash equilibria of the potential game.
By constructing a potential function for Rosenthal’s congestion games, the exis-
tence of pure-strategy equilibria can be established. Monderer and Shapley (1996)
not only prove that every such congestion game is an exact potential game, but
also establish that every exact potential game is isomorphic to a congestion game.
Konishi, Le Breton and Weber (1997), Milchtaich (1996), and Quint and Shubik
(1994) considered different classes of congestion games which in general do not
admit a potential function, but were still able to prove the existence of pure Nash
equilibria. Konishi, Le Breton and Weber (1997), considering the same model as
Milchtaich, have even shown the existence of a strong Nash equilibrium.
This paper has several goals. First, after reviewing some results on exact poten-
tial games in Sec. 2, we provide a new, simple proof of the isomorphism between
exact potential games and Rosenthal’s congestion games in Sec. 3.
Secondly, the relations and differences between the congestion models of Konishi
et al. (1997), Milchtaich (1996), and Quint and Shubik (1994) are clarified in Sec. 4.
Thirdly, in Secs. 5 and 6 we return to potential games and focus on a class of
congestion games that combines features from the congestion models mentioned
above. This class is shown to have interesting properties. In particular, it is shown
that for each game in this class, the set of strong Nash equilibria is non-empty
and coincides with the set of Nash equilibria and the set of potential-maximising
strategies.
In Sec. 5, we analyse the geometric properties of this class of games, showing
that it can be represented by a finitely generated cone. The aim of this section is
twofold. First, it provides an easy way to compute potential-maximising strategies,
and second, it facilitates the proof that the sets of strong Nash equilibria, Nash
equilibria, and potential-maximising strategies are equal.
Implications of relaxing some of the assumptions underlying the congestion effect
are discussed in Sec. 7.

2. Exact Potential Games

This section defines exact potential games and surveys some results that are used in
the remainder of the paper. A (strategic) game is a tuple G = hN, (Xi )i∈N , (ui )i∈N i,
where N is a non-empty, finite set of players, each player i ∈ N has a non-empty,
May 11, 2000 9:44 WSPC/151-IGTR 0010

Congestion Games and Potentials Reconsidered 285

Q
finite set Xi of pure strategies and a payoff function ui : j∈N Xj → R specifying
Q
for each strategy profile x = (xj )j∈N ∈ j∈N Xj player i’s payoff ui (x) ∈ R.
Mixed strategies are not considered in this paper. Conventional game-theoretic
Q
notation is used: X = j∈N Xj denotes the set of strategy profiles. Let i ∈ N .
Q
X−i = j∈N\{i} Xj denotes the strategy profiles of i’s opponents. Let S ⊆ N .
Q
XS = j∈S Xj denotes the set of strategy profiles of players in S. With a slight
abuse of notation strategy profiles x = (xj )j∈N ∈ X will be denoted by (xi , x−i ) or
(xS , xN\S ) if the strategy choice of player i or of the set S of players needs stressing.
Monderer and Shapley (1996) introduce exact potential games.

Definition 2.1. A strategic game G = hN, (Xi )i∈N , (ui )i∈N i is an exact potential
game if there exists a function P : X → R such that for all i ∈ N , for all x−i ∈ X−i ,
and all xi , yi ∈ Xi :
ui (xi , x−i ) − ui (yi , x−i ) = P (xi , x−i ) − P (yi , x−i ) .
The function P is called an (exact) potential (f unction) for G.

In other words, a strategic game is an exact potential game if there exists a

real-valued function on the strategy space which exactly measures the difference in
the payoff that accrues to a player if he unilaterally deviates.

Example 2.1. The Prisoner’s Dilemma game of Fig. 1(a) is an exact potential
game with an exact potential function given by P (c, c) = 5, P (c, d) = P (d, c) = 4,
P (d, d) = 3. The game in Fig. 1(b) is an exact potential game with an exact
potential function given by P (T, L) = 0, P (T, R) = 1, P (B, L) = 2, P (B, R) = 3.

If G = hN, (Xi )i∈N , (ui )i∈N i has an exact potential P , the definition
of an exact potential game immediately implies that the Nash equilibria of
hN, (Xi )i∈N , (P )i∈N i, the game obtained by replacing each payoff function by the
potential P , and the game G coincide.

Proposition 2.1. [Monderer and Shapley (1996), Corollary 2.2] Let G =

hN, (Xi )i∈N , (ui )i∈N i be an exact potential game. Then G has at least one (pure-
strategy) Nash equilibrium.

Proof. Let P be an exact potential for G. Since X is finite, arg maxx∈X P (x)
is a non-empty set. Clearly, all elements in this set are pure-strategy Nash
equilibria.

c d L R
c 1,1 4,0 T 0,2 2,3
d 0,4 3,3 B 2,5 4,6
(a) (b)

Fig. 1. Two exact potential games.

May 11, 2000 9:44 WSPC/151-IGTR 0010

286 M. Voorneveld et al.

Facchini et al. (1997) provide a characterisation of exact potential games by

splitting them up into coordination games and dummy games.

Definition 2.2. A game G = hN, (Xi )i∈N , (ui )i∈N i is a

• coordination game if there exists a function u : X → R such that ui = u for all

i ∈ N;
• dummy game if for all i ∈ N and all x−i ∈ X−i there exists a k ∈ R such that
ui (xi , x−i ) = k for all xi ∈ Xi , or equivalently, if for all i ∈ N , all x−i ∈ X−i ,
and all xi , yi ∈ Xi : ui (xi , x−i ) = ui (yi , x−i ).

In a coordination game, players pursue the same goal, reflected by the identical
payoff functions. In a dummy game, a player’s payoff does not depend on his own
strategy. Coordination games and dummy games are exact potential games.

Theorem 2.1. Let G = hN, (Xi )i∈N , (ui )i∈N i be a strategic game. G is an exact
potential game if and only if there exist functions (ci )i∈N and (di )i∈N such that

• ui = ci + di for all i ∈ N ,
• hN, (Xi )i∈N , (ci )i∈N i is a coordination game, and
• hN, (Xi )i∈N , (di )i∈N i is a dummy game.

Proof. The “if”-part is obvious: the payoff function of the coordination game is
an exact potential function of G. To prove the “only if”-part, let P be an exact
potential for G. For all i ∈ N , ui = P + (ui − P ). Clearly, hN, (Xi )i∈N , (P )i∈N i
is a coordination game. Let i ∈ N, x−i ∈ X−i and xi , yi ∈ Xi . Then ui (xi , x−i ) −
ui (yi , x−i ) = P (xi , x−i ) − P (yi , x−i ) implies ui (xi , x−i ) − P (xi , x−i ) = ui (yi , x−i ) −
P (yi , x−i ). So hN, (Xi )i∈N , (ui − P )i∈N i is a dummy game.

The difference between two exact potential functions of a game is a constant

function [see also Monderer and Shapley (1996), Lemma 2.7].

Proposition 2.2. Let G = hN, (Xi )i∈N , (ui )i∈N i be a game with exact potential
functions P and Q. Then P − Q is a constant function.

Proof. Let i ∈ N . By Theorem 2.1, ui − Q and ui − P do not depend on the

strategy choice of player i. Hence (P − Q) = (ui − Q) − (ui − P ) does not depend
on the strategy choice of player i. This holds for every player i ∈ N : (P − Q) is a
constant function.

Proposition 2.2 implies that the set of strategy profiles maximising a potential
function of an exact potential game does not depend on the particular potential
function that is chosen. Potential-maximising strategies were used in the proof
of Proposition 2.1 to show that exact potential games have pure-strategy Nash
May 11, 2000 9:44 WSPC/151-IGTR 0010

Congestion Games and Potentials Reconsidered 287

equilibria. The potential maximiser, formally defined for an exact potential game
G = hN, (Xi )i∈N , (ui )i∈N i as
P M (G) = {x ∈ X|x ∈ arg max P (y) for some potential function P of G}
y∈X

can therefore, as shown by Monderer and Shapley (1996), act as an equilibrium

refinement tool. Peleg, Potters and Tijs (1996) provide an axiomatic approach to
potential-maximising strategies.

3. Rosenthal’s Congestion Model

In a congestion model, players use several facilities — also called machines or (pri-
mary) factors — from a common pool. The costs or benefits that a player derives
from the use of a facility are, possibly among other factors, determined by the
number of users of a facility. In this section we focus on the congestion model of
Rosenthal (1973). In this model, each player chooses a subset of facilities. The bene-
fit (possibly negative) associated with each facility is a function only of the number
of players using it. The payoff to a player is the sum of the benefits associated
with each facility in his strategy choice, given the choices of the other players. By
constructing an exact potential function for such congestion games, the existence of
pure-strategy Nash equilibria can be established. Moreover, Monderer and Shapley
(1996) showed that every exact potential game is isomorphic to a congestion game.
Their proof is rather complex. In this section, we present a different proof which
is shorter and in our opinion more intuitive. In fact, we use the decomposition of
exact potential games into dummy games and coordination games stated in The-
orem 2.1 to decompose the problem into two sub-problems. It is shown that each
coordination game and each dummy game is isomorphic to a congestion game as
defined by Rosenthal.
A congestion model is a tuple hN, F, (Xi )i∈N , (wf )f ∈F i, where
• N = {1, . . . , n} is a non-empty, finite set of players;
• F is a non-empty, finite set of facilities;
• For each player i ∈ N , his collection of pure strategies Xi is a non-empty, finite
family of subsets of F ;
• For each facility f ∈ F , wf : {1, . . . , n} → R is the benefit function of facility f ,
with wf (r), r ∈ {1, . . . , n}, the benefits to each of the users of facility f if there
is a total of r users.
This gives rise to a congestion game G = hN, (Xi )i∈N , (ui )i∈N i where N and
(Xi )i∈N are as above and for i ∈ N , ui : X → R is defined thus: for each x =
(x1 , . . . , xn ) ∈ X, and each f ∈ F , let nf (x) = |{i ∈ N : f ∈ xi }| be the number
P
of users of facility f if the players choose x. Then ui (x) = f ∈xi wf (nf (x)). This
definition implies that each player derives benefit from the facilities he uses, with
benefits depending only on the number of users of the facility. Notice that benefit
functions can achieve negative values, representing costs of using a facility.
May 11, 2000 9:44 WSPC/151-IGTR 0010

288 M. Voorneveld et al.

The main result from Rosenthal’s paper, formulated in terms of exact potentials,
is given in the next proposition. Its proof is straightforward and therefore omitted.

Proposition 3.1. Let hN, F, (Xi )i∈N , (wf )f ∈F i be a congestion model and G its
congestion game. Then G is an exact potential game. A potential function is given
by P : X → R defined for all x = (xi )i∈N ∈ X as

X X
nf (x)
P (x) = wf (`).
f ∈∪i∈N xi `=1

Since X is finite, the game has a Nash equilibrium in pure strategies.

Let G = hN, (Xi )i∈N , (ui )i∈N i and H = hN, (Yi )i∈N , (vi )i∈N i be two strategic
games with identical player set N . G and H are isomorphic if for all i ∈ N there
exists a bijection ϕi : Xi → Yi such that
ui (x1 , . . . , xn ) = vi (ϕ1 (x1 ), . . . , ϕn (xn )) for all (x1 , . . . , xn ) ∈ X.
A congestion game where the facilities have non-zero benefits only if all players
use it as part of their strategy choice is clearly a coordination game. Also, each
coordination game can be expressed in this form, as shown in the proof of the next
theorem.

Theorem 3.1. Each coordination game is isomorphic to a congestion game.

Proof. Let G = hN, (Xi )i∈N , (u)i∈N i be an n-player coordination game in which
each player has payoff function u. Introduce for each x ∈ X a different facility f (x).
Define the congestion model hN, F, (Yi )i∈N , (wf )f ∈F i with F = ∪x∈X {f (x)}, for
each i ∈ N : Yi = {gi (xi )|xi ∈ Xi } where gi (xi ) = ∪x−i ∈X−i {f (xi , x−i )}, and for
each f (x) ∈ F :
(
u(x) if r = n
wf (x) (r) =
0 otherwise .
For each x ∈ X: ∩i∈N gi (xi ) = {f (x)}, so the game corresponding to this congestion
model is isomorphic to G (where the isomorphisms map xi to gi (xi )).

The proof is illustrated with a simple example.

Example 3.1. Consider the coordination game in Fig. 2(a). For each strategy
profile we introduce a facility as in Fig. 2(b). These are the facilities that we want
to be used by both players if they play the corresponding strategy profile. To do
this, give each player in a certain row (column) all facilities mentioned in this row
(column). For instance, the second strategy of the row player will correspond with
choosing facility set {C, D}. Now indeed, if both players play their second strategy,
facility D is used by both players and all other facilities have one or zero users.
Defining the benefits of D in case of two simultaneous users to be 3 and in case of
May 11, 2000 9:44 WSPC/151-IGTR 0010

Congestion Games and Potentials Reconsidered 289

{A, C} {B, D}
0,0 1,1 A B {A, B} 0,0 1,1
2,2 3,3 C D {C, D} 2,2 3,3
(a) (b) (c)

Fig. 2. A coordination game.

less users zero, we obtain the payoff (3,3) in the lower right-hand corner of Fig. 2(c).
Similar reasoning applies to the other cells.

Consider a congestion game in which the benefits for a facility are non-zero only
if it is used by a single player. If for each player, given the strategy choices of the
other players, it holds that his benefits arise from using one and the same facility,
irrespective of his own strategy choice, we have a dummy game. Also, as shown in
the next theorem, each dummy game is isomorphic to a congestion game with this
property.

Theorem 3.2. Each dummy game is isomorphic to a congestion game.

Proof. Let G = hN, (Xi )i∈N , (ui )i∈N i be a dummy game. Introduce for each i ∈
N and each x−i ∈ X−i a different facility f (x−i ). Define the congestion model
hN, F, (Yi )i∈N , (wf )j∈F i with F = ∪i∈N ∪x−i ∈X−i {f (x−i )}, for each i ∈ N : Yi =
{hi (xi )|xi ∈ Xi } where
hi (xi ) = {f (x−i )|x−i ∈ X−i }

∪ {f (y−j )|j ∈ N \{i} and y−j ∈ X−j is such that yi 6= xi } ,

and for each f (x−i ) ∈ F :
(
ui (xi , x−i ) if r = 1(with xi ∈ Xi arbitrary)
wf (x−i ) (r) =
0 otherwise .
For each i ∈ N , x̄−i ∈ X−i and x̄i ∈ Xi : i is the unique user of f (x̄−i ) in (hj (x̄j ))j∈N
and all other facilities in hi (x̄i ) have more than one user. Why? Let i ∈ N , x̄−i ∈
X−i , and x̄i ∈ Xi . Then f (x̄−i ) ∈ hi (x̄i ) and for each j ∈ N \{i}: f (x̄−i ) ∈ / hj (x̄j ),
so i is indeed the unique user of f (x̄−i ) in (hj (x̄j ))j∈N . Let f ∈ hi (x̄i ), f 6= f (x̄−i ).
• If f = f (y−i ) for some y−i ∈ X−i , then y−i 6= x̄−i implies that yj 6= x̄j for some
j ∈ N \{i}, so f = f (y−i ) ∈ hj (x̄j ).
• If f = f (y−j ) for some j ∈ N\{i} and y−j ∈ X−j with yi 6= x̄i , then f = f (y−j ) ∈
hj (x̄j ).
In both cases f has more than one user. So the game corresponding to this conges-
tion model is isomorphic to G (where the isomorphisms map xi to hi (xi )).

Once again, this argumentation is illustrated by an example.

May 11, 2000 9:44 WSPC/151-IGTR 0010

290 M. Voorneveld et al.

{β, γ, δ} {α, γ, δ}
0,2 1,2 α, γ β, γ {α, β, δ} 0,2 1,2
0,3 1,3 α, δ β, δ {α, β, γ} 0,3 1,3
(a) (b) (c)

Fig. 3. A dummy game.

Example 3.2. Consider the dummy game in Fig. 3(a). Introduce a different facil-
ity for each profile of opponent strategies as in Fig. 3(b). Facility α, for instance, is
associated with the strategy profile in which player 2, the only opponent of player 1,
choosing the left column. Include a facility f (x−i ) in each strategy of each player,
except for the strategies of players j ∈ N \ {i} specified by the profile x−i . For
instance, facility α was introduced for the first column of player 2; then α is part of
every strategy, except for the first column of player 2. This yields the strategies as
in Fig. 3(c). Define benefits for multiple users equal to zero. No matter what player
1 does, if his opponent chooses his second strategy, the benefits to player 1 can
be attributed to facility β. Assign benefit 1 to a single user of this facility. Similar
reasoning for the other payoffs yields the isomorphic congestion game in Fig. 3(c).

In the previous two theorems it was shown that coordination and dummy games
are isomorphic to congestion games. Using the decomposition of Theorem 2.1 we
obtain that every exact potential game is isomorphic to a congestion game.

Theorem 3.3. Every exact potential game is isomorphic to a congestion game.

Proof. Let G = hN, (Xi )i∈N , (ui )i∈N i be an exact potential game. Split it into a
coordination game and a dummy game as in Theorem 2.1 and take their isomorphic
congestion games as in Theorems 3.1 and 3.2. Without loss of generality, take their
facility sets disjoint. Construct a congestion game isomorphic to G by taking the
union of the two facility sets, benefit functions as in Theorems 3.1 and 3.2, and
strategy sets Yi = {gi(xi ) ∪ hi (xi )|xi ∈ Xi }.

Example 3.3. The exact potential game in Fig. 1(b) is the sum of the coordina-
tion game from Example 3.1 and the dummy game from Example 3.2. Combining
the two isomorphic congestion games from these examples yields a congestion game
isomorphic to the exact potential game. See Fig. 4.

{A, C} ∪ {β, γ, δ} {B, D} ∪ {α, γ, δ}

0,2 2,3 {A, B} ∪ {α, β, δ} 0 + 0,0 + 2 1 + 1,1 + 2
2,5 4,6 {C, D} ∪ {α, β, γ} 2 + 0,2 + 3 3 + 1,3 + 3
(a) (b)

Fig. 4. Exact potential game and isomorphic congestion game.

May 11, 2000 9:44 WSPC/151-IGTR 0010

Congestion Games and Potentials Reconsidered 291

4. Congestion Games
The games introduced by Konishi, Le Breton and Weber (1997), Milchtaich (1996),
and Quint and Shubik (1994) are similar, in the sense that the utility functions of
the players are characterised by a congestion effect. The various classes of games
we discuss are identified by means of different sets of properties concerning the
structure of the strategic interaction. In particular, Konishi et al. (1997) impose
the following assumptions (P1)–(P4) on a game G = hN, (Xi )i∈N , (ui )i∈N i.

(P1) There exists a finite set F such that Xi = F for all players i ∈ N .

The set F is called the “facility set” and a strategy for player i is choosing an
element of F .

(P2) For each strategy profile x ∈ X and all players i, j ∈ N : if xi 6= xj and

x0j ∈ Xj is such that xi 6= x0j , then ui (xj , x−j ) = ui (x0j , x−j ).

Konishi et al. (1997) call this assumption independence of irrelevant choices: for
each player i ∈ N and each strategy profile x the utility of i will not be altered if
the set of players that choose the same facility as player i is not modified.
Let x ∈ X, f ∈ F . Denote as before by nf (x) the number of users of facility f
in the strategy profile x. Then the third property can be stated as follows:

(P3) For each player i ∈ N and all strategy profiles x, y ∈ X with xi = yi : if

nf (x) = nf (y) for all f ∈ F , then ui (x) = ui (y).

This anonymity condition reflects the idea that the payoff of player i depends
on the number of players choosing the facilities, rather than on their identity. The
fourth assumption, called partial rivalry, states that each player i would not regret
that other players, choosing the same facility, would select another one. Formally:

(P4) For each player i ∈ N , each strategy profile x ∈ X, each player j 6= i such
that xj = xi and each x0j 6= xi : ui (xj , x−j ) 5 ui (x0j , x−j ).

Although Milchtaich (1996) introduces his model in a slightly different way, the
resulting class of games is the same. More specifically Milchtaich (1996) introduces
the conditions (P1), (P4) and the following assumption:

(P20 ) For each player i ∈ N and all strategy profiles x, y with xi = yi = f : if

nf (x) = nf (y), then ui (x) = ui (y).

In other words the utility of player i depends only on the number of users of the
facility that i has chosen. Assuming (P1), it is straightforward to prove that (P20 )
implies both (P2) and (P3). The converse implication is also true.

Lemma 4.1. Any game G = hN, (Xi )i∈N , (ui )i∈N i satisfying (P1), (P2) and (P3)
satisfies (P20 ).
May 11, 2000 9:44 WSPC/151-IGTR 0010

292 M. Voorneveld et al.

Proof. Let G = hN, (Xi )i∈N , (ui )i∈N i satisfy (P1), (P2) and (P3). Let i ∈ N ,
x, y ∈ X such that xi = yi = f and assume that nf (x) = nf (y). If |F | = 1, (P20 )
follows directly. Otherwise, from repeated use of (P2), we know that for a fixed
g 6= xi , ui (xi , x−i ) = ui (xi , x0−i ) where for each j ∈ N \{i}:
(
0
xi if xj = xi ,
xj =
g otherwise ,
0
and that ui (xi , y−i ) = ui (xi , y−i ), where for each j ∈ N \{i}:
(
xi if yj = xi ,
yj0 =
g otherwise .

Notice that for each h ∈ F , nh (xi , x0−i ) = nh (xi , y−i 0

). So (P3) implies ui (xi , x0−i ) =
0 0 0
ui (xi , y−i ). Therefore, ui (xi , x−i ) = ui (xi , x−i ) = ui (xi , y−i ) = ui (yi , y−i ).

Konishi et al. (1997) and Milchtaich (1996) independently proved the following:

Theorem 4.1. Each game hN, (Xi )i∈N , (ui )i∈N i satisfying (P1), (P2), (P3) and
(P4), possesses a pure-strategy Nash equilibrium.

Recall that, given a game G = hN, (Xi )i∈N , (ui )i∈N i, a strategy profile x is
called a strong Nash equilibrium if for every S ⊆ N and all strategy profiles yS ∈
XS , there is at least one player i ∈ S such that ui (yS , x−S ) 5 ui (x). The set of
strong Nash equilibria of a game G is denoted by SN E(G). In general, the existence
of a strong Nash equilibrium is not guaranteed, not even in exact potential games
[see, for instance, the Prisoners’ Dilemma in Fig. 1(a)], but Konishi et al. (1997)
show:

Theorem 4.2. For each game satisfying (P1), (P2), (P3) and (P4), the set of
strong Nash equilibria is non-empty.

Finally, we mention the model introduced by Quint and Shubik (1994), where
the assumption that all players have the same set of facilities [as stated by (P1)] is
relaxed.

(P10 ) There exists a finite set F such that Xi ⊆ F for all players i ∈ N .

Assuming that (P10 ) holds, it is still easy to see that (P20 ) implies (P2) and
(P3). But the analogon of Lemma 4.1 does not hold.

Example 4.1. Take N = {1, 2, 3}, F = {a, b, c} and strategy sets X1 = {a, b},
X2 = {a}, X3 = {a, c}. This game satisfies (P10 ). Assumption (P3) imposes
no additional requirements and (P2) requires that u1 (b, a, a) = u1 (b, a, c) and
u3 (a, a, c) = u3 (b, a, c). This does not imply u2 (a, a, c) = u2 (b, a, a), which is
required by (P20 ).
May 11, 2000 9:44 WSPC/151-IGTR 0010

Congestion Games and Potentials Reconsidered 293

Quint and Shubik (1994) show:

Theorem 4.3. All strategic games satisfying (P10 ), (P20 ) and (P4) possess a pure
Nash equilibrium.

Games in the classes considered so far do not necessarily admit a potential

function. Consider now the following cross-symmetry condition, which states that
the payoffs on a certain facility are player-independent, provided that the number
of users is the same.
(P5) For all strategy profiles x, y ∈ X and all players i, j ∈ N : if xi = yj = f and
nf (x) = nf (y), then ui (x) = uj (y).

Notice that (P5) together with (P1) implies (P20 ), and thus (P2) and (P3). More-
over, (P1) and (P5) guarantee the existence of a potential.

Theorem 4.4. Each game satisfying (P1) and (P5) is an exact potential game.

Proof. Let G = hN, (Xi )i∈N , (ui )i∈N i satisfy (P1) and (P5). For any f ∈ F and
x, y ∈ X such that nf (x) = nf (y), we have by (P5): if there are i, j ∈ N such
that xi = yj = f , then ui (x) = uj (y). This shows that for all f ∈ F there exists
a benefit function wf : {1, . . . , n} → R such that for all x ∈ X, if xi = f , then
ui (x) = wf (nf (x)). This makes the game G a congestion game as defined in Sec. 3.a
The result now follows from Proposition 3.1.

Remark 4.1. The theorem still holds if (P10 ) is substituted for (P1). It also follows
from Proposition 3.1, that the benefit functions (wf )f ∈F give rise to a potential
P Pnf (x)
P : x 7→ f ∈∪i∈N {xi } `=1 wf (`).

The remainder of this paper focuses on games that admit an exact potential
and have strong Nash equilibria. Therefore, attention is restricted to the class C of
congestion games satisfying not only (P1) and (P5), but also (P4). So
C = {G = hN, (Xi )i∈N , (ui )i∈N i|G satisfies (P1), (P4) and (P5)} . (1)

5. On the Structure of the Class C

We analyse the structure of the class C defined in (1). Let n ∈ N be a number of
players and F a finite set of facilities. Denote by C(F, n) the set of all games in
C with n players and facility set F . Identifying each game G ∈ C(F, n) with a set
of vectors (wf )f ∈F like in the proof of Theorem 4.4, it is shown that C(F, n) is a
finitely generated cone in (Rn+ )F . The vector notation of the games simplifies the
proofs of the theorems on strong equilibria and the potential maximiser presented
in Secs. 6 and 7.

a Where we identify choosing a facility f ∈ F with choosing facility set {f } ⊆ F .

May 11, 2000 9:44 WSPC/151-IGTR 0010

294 M. Voorneveld et al.

Let G ∈ C(F, n). Recall from Theorem 4.4 that for every f ∈ F there exists
a function wf : {1, . . . , n} → R such that for all x ∈ X, if xi = f , then ui (x) =
wf (nf (x)). From (P4), we have for each f ∈ F and t ∈ {1, . . . , n − 1} that wf (t) =
wf (t + 1). For convenience and without loss of generality (by adding a positive
constant to all functions wf if necessary) we assume that wf (t) = 0 for all f ∈
F, t ∈ {1, . . . , n}. This means that the game G ∈ C(F, n) is described by |F | vectors
of the form (wf (1), . . . , wf (n)), f ∈ F , each in the set V = {v = (v1 , . . . , vn ) ∈
Rn+ |vt = vt+1 for all t ∈ {1, . . . , n − 1}}.

Proposition 5.1. The set V is a finitely generated cone in Rn+ . The extreme direc-
tions of V are the vectors b1 , b2 , . . . , bn with bi = (1, 1, 1, 1, 0, . . . , 0). Furthermore,
| {z }
i times
dim(V ) = n.

Proof. The vectors

b1 = (1, 0, 0, . . . , 0), bi = (1, 1, 1, 1, 0, . . . , 0), . . . , bn = (1, 1, 1, 1, . . . , 1)

| {z }
i times

are elements of V and each vector v ∈ V can be uniquely written as a non-negative

combination of b1 , b2 , . . . , bn . To show this, let v ∈ V and define
 1
b
 b2 
 
Bn =  .  .
 .. 
bn

So Bn is the n × n matrix whose ith row is bi . Since det(Bn ) = 1, the equa-

tion αBn = v has exactly one solution. Clearly, α is non-negative because of
the decreasingness property of v. The set V is therefore the cone C(Bn ) where
C(Bn ) := {αBn |α ∈ Rn+ }.
The extreme directions of the cone C(Bn ) are the vectors bi , i ∈ {1, . . . , n}.
This cone has furthermore the property that its dimension is the number of extreme
directions. In other words we have that dim C(Bn ) = rank(Bn ) = n.

This proves:

Corollary 5.1. The class of games C(F, n) can be identified with a cone in (Rn+ )F
and dim(C(F, n)) = |F | × n.

In the next example we consider an extreme game of C(F, n), i.e. a game with
facility set F such that wf is an extreme direction in the cone V for each f ∈ F .

Example 5.1. Let G be a game in C({f, g}, 4) such that wf = (1, 0, 0, 0) and
wg = (1, 1, 0, 0). Nash equilibria are either those strategy profiles in which one of
May 11, 2000 9:44 WSPC/151-IGTR 0010

Congestion Games and Potentials Reconsidered 295

the players chooses f and the other three g, or those in which both facilities are
chosen by two players. These situations will be depicted
 
1 , 0, 0, 0
 
1, 1, 0 , 0

for the first case and

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

for the second one, where the numbers in the square boxes indicate the payoff
received by each player choosing this facility. Notice furthermore that the players
are interchangeable as suggested by the cross-symmetry condition (P5). One easily
checks that all Nash equilibria are strong.

6. Strong Nash Equilibria and the Potential Maximiser

In this section it is shown that on the class C, the set of Nash equilibria, strong
Nash equilibria, and potential maximisers coincide:

Theorem 6.1. On the class C of games, SN E = N E = P M .

A proof of this result is given in parts. Recall that for any strategic game G,
SN E(G) ⊆ N E(G) and that for any exact potential game G, P M (G) ⊆ N E(G).
It therefore suffices to prove the following propositions.

Proposition 6.1. For each game G ∈ C, N E(G) ⊆ P M (G).

Proposition 6.2. For each game G ∈ C, N E(G) ⊆ SN E(G).

The proofs are based on the structure of the class C described in the previous
section. We assume n ∈ N and a finite facility set F to be fixed. Each game G ∈
C(F, n) is given by a collection of vectors
((wf (1), . . . , wf (n)))f ∈F ,

(wf (1), . . . , wf (n)) ∈ {v ∈ Rn+ |vt = vt+1 for all t ∈ {1, . . . , n − 1}} .
To compute the potential of Remark 4.1, it is necessary to add the utilities of the
used facilities up to the number of users. This means that in each vector wf all the
first nf (x) numbers are added.
As a consequence it is clear that a potential maximising profile is found by n
times consecutively choosing the facilities with highest remaining numbers, from
left on, in the set of vectors {(wf (1), . . . , wf (n))}f ∈F . This is illustrated in the
following example.
May 11, 2000 9:44 WSPC/151-IGTR 0010

296 M. Voorneveld et al.

Example 6.1. Let G ∈ C({f, g}, 4) such that

wf = (4, 3, 2, 1)

wg = (5, 2, 1, 0) .

In the first step we take the first cell in wg , in the second step the first cell in wf ,
in the third step the second cell of wf , and finally, in the fourth step either the
third cell of wf or the second cell of wg . Consequently, the potential maximising
strategy combinations are those x ∈ F N with nf (x) = 3, ng (x) = 1 and those
with nf (x) = 2, ng (x) = 2. Notice that for these x, P (x) = 14 and that all Nash
equilibria are potential maximising.

Based on a switching argument the next lemma shows the similarities in utilities
for different Nash equilibria.

Lemma 6.1. Let G ∈ C(F, n) be determined by ((wf (1), . . . , wf (n)))f ∈F and let
x and y be Nash equilibria of G. For all f, g ∈ F such that nf (x) < nf (y) and
ng (y) < ng (x), and for all l ∈ {nf (x)+1, . . . , nf (y)} and m ∈ {ng (y)+1, . . . , ng (x)}
it holds that

wf (l) = wf (nf (y)) = wg (ng (x)) = wg (m) .

Proof. Let f, g ∈ F and l, m be as described in the lemma. Both x and y are Nash
equilibria, so wf (nf (y)) = wg (ng (y) + 1) = wg (m) = wg (ng (x)) = wf (nf (x) + 1) =
wf (l) = wf (nf (y)).

This lemma is used in the proof of Proposition 6.1.

Proof. [Proposition 6.1] Let G ∈ C(F, n) be determined by the set of vectors

((wf (1), . . . , wf (n)))f ∈F . It suffices to show that P (x) = P (y) if x is a Nash equi-
librium and y a potential maximising strategy combination. Let x ∈ N E(G) and
y ∈ P M (G). Facilities f ∈ F such that nf (x) = nf (y) add as much to P (x) as to
P (y). Furthermore, by Lemma 6.1, if nf (x) < nf (y) and ng (y) < ng (x) for certain
f, g ∈ F , then there exists a w ∈ R such that wf (l) = wf (nf (y)) = wg (ng (x)) =
wg (m) for all l ∈ {nf (x) + 1, . . . , nf (y)} and m ∈ {ng (y) + 1, . . . , ng (x)}. By this
argument, the total contribution of the facilities in the set {f ∈ F |nf (x) 6= nf (y)}
to the potentials P (x) and P (y) is the same:

P (x) − P (y)
X X
nf (x)
X X
nf (y)
= wf (k) − wf (k)
{f ∈F |nf (x)>nf (y)} k=nf (y)+1 {f ∈F |nf (x)<nf (y)} k=nf (x)+1
X X
= [nf (x) − nf (y)]w − [nf (y) − nf (x)]w
{f ∈F |nf (x)>nf (y)} {f ∈F |nf (x)<nf (y)}
May 11, 2000 9:44 WSPC/151-IGTR 0010

Congestion Games and Potentials Reconsidered 297

 
X X
= w (nf (x) − nf (y)) − (nf (y) − nf (x))
{f ∈F |nf (x)>nf (y)} {f ∈F |nf (x)<nf (y)}

= 0,
completing the proof.

Remains to prove Proposition 6.2.

Proof. [Proposition 6.2]. Let G ∈ C(F, n) be given by ((wf (1), . . . , wf (n)))f ∈F

and let x ∈ N E(G). Suppose S ⊆ N can strictly improve the payoff for all
its members by switching to a strategy combination yS ∈ F S . Call the result-
ing strategy combination y = (yS , xN\S ). If nf (y) > nf (x) for some f ∈ F ,
a player i ∈ S exists such that yi = f and xi = g, g 6= f . This implies
wf (nf (x) + 1) = wf (nf (y)) > wg (ng (x)), which contradicts the fact that x is a
Nash equilibrium. So nf (x) = nf (y) for all f ∈ F . Therefore every player in S
chooses a new facility already chosen by a member of S and obtains a higher util-
ity. Among the utilities assigned to members of S there is a maximum, since S is
finite. Any player in S rewarded with this maximum cannot get more in the new
configuration. Hence a contradiction arises. Every Nash equilibrium is strong.

In the last part of this section we consider strictly strong Nash equilibria. Recall
that given a game hN, (Xi )i∈N , (ui )i∈N i, a strategy profile x ∈ X is a strictly
strong Nash equilibrium if for all coalitions S ⊆ N and strategy combinations yS ∈
XS , ui (yS , xN\S ) = ui (x) for all i ∈ S or ui (yS , xN\S ) < ui (x) for at least one i ∈ S.
The following example illustrates that the properties of C do not guarantee the
existence of strictly strong Nash equilibria.

Example 6.2. Consider the game G ∈ C({f, g}, 3) with wf , wg given by

 
wf = 4, 2 , 0 ,
 
wg = 3 , 2, 1 ,
where the squared numbers depict a strong Nash equilibrium payoff. If the two
players choosing f agree that one of them switches to g and the other one sticks
to f , the utility will still be 2 for the switching one but increases from 2 to 4 for
the remaining player. A similar argument holds for the other type of strong Nash
equilibria given by
 
wf = 4 , 2, 0
 
wg = 3, 2 , 1
Since these are the only two types of strong Nash equilibria, and neither of them
is strictly strong, strictly strong Nash equilibria do not exist.
May 11, 2000 9:44 WSPC/151-IGTR 0010

298 M. Voorneveld et al.

7. Extensions of the Model

The class C is defined by properties (P1), (P4) and (P5). It is obvious that relaxation
of those properties will have consequences on the result presented in Sec. 6.
First of all, the classes of congestion games of Quint and Shubik (1994), Milch-
taich (1996) and Konishi et al. (1997) without (P5) do not necessarily admit an
exact potential.
Secondly, consider the class CP of strategic games which satisfy the properties
(P1) and (P5). Each n-player game G in CP is a potential game and can be repre-
sented by a collection of arbitrary vectors ((wf (1), . . . , wf (n)))f ∈F ∈ (Rn )F . It is
obvious that not every game G ∈ CP has a strong Nash equilibrium. For instance,
the Prisoner’s Dilemma in Example 2.1 is an element of CP with F = {c, d},
wc = (4, 1) and wd = (0, 3), but does not have a strong Nash equilibrium. But
even the existence of a strong Nash equilibrium for a game G ∈ CP does not
guarantee that each Nash equilibrium is strong too, nor that a strong equilib-
rium is a potential maximiser. The next example gives a game G ∈ CP such that
∅ 6= SN E(G) ⊂ N E(G) and SN E(G) ∩ P M (G) = ∅.
Example 7.1. Let G ∈ CP({f, g}, 3) with
 
wf = 4, 0, 5
wg = (4, 2, 0) .
The unique strong Nash equilibrium in which all three players chooses facility f is
indicated. By Theorem 4.4, the potential can be computed as in Remark 4.1. The
maximal potential arises at the non-strong equilibria which are given by
 
wf = 4 , 0, 5
 
wg = 4, 2 , 0 .

Finally, consider the class of strategic games C 0 satisfying (P10 ), (P4) and (P5).
Similarly to Proposition 6.2 one can show:
Theorem 7.1. For every game G ∈ C 0 , N E(G) = SN E(G).
This result coincides with that of Holzman and Law-Yone (1997, Theorem 2.1).
In the class C 0 , however, the set of potential maximising strategy combinations need
not coincide with the set of Nash equilibria, as can be seen in the following example.
Example 7.2. Consider the game G ∈ C 0 ({f, g, h}, 5) in which three players have
strategy set {f, h} and two {g, h}. The benefit vectors are
 
wf = 4, 2, 1 , −, −
 
wg = 3 , 2, −, −, −
 
wh = 2 , 1, 1, 0, 0
May 11, 2000 9:44 WSPC/151-IGTR 0010

Congestion Games and Potentials Reconsidered 299

where the squared numbers depict a Nash equilibrium payoff. It represents strategy
combinations in which the three players with strategy set {f, h} all play f . Consider
now the equilibrium in which two of those three play f and the other plays h.
 
wf = 4, 2 , 1, −, −
 
wg = 3, 2 , −, −, −
 
wh = 2 , 1, 1, 0, 0

The potential can be computed as in Remark 4.1. For the first type of equilibrium
in this example, the potential value equals 4 + 2 + 1 + 3 + 2 = 12, which is less
than 4 + 2 + 3 + 2 + 2 = 13, the potential value associated to the second type of
equilibrium.

References
Facchini, G., F. Van Megen, P. Borm and S. Tijs (1997). “Congestion Models and Weighted
Bayesian Potential Games”. Theory and Decision, Vol. 42, 193–206.
Holzman R. and N. Law-Yone (1997). “Strong Equilibrium in Congestion Games”. Games
and Economic Behavior, Vol. 21, 85–101.
Konishi H., M. Le Breton and S. Weber (1997). “Equilibria in a Model with Partial
Rivalry”. Journal of Economic Theory, Vol. 72, 225–237.
Milchtaich I. (1996). “Congestion Models with Player Specific Payoff Functions”. Games
and Economic Behavior, Vol. 13, 111–124.
Monderer D. and L. S. Shapley (1996). “Potential Games”. Games and Economic Behav-
ior, Vol. 14, 124–143.
Peleg B., J. Potters and S. Tijs (1996). “Minimality of Consistent Solutions for Strategic
Games, in Particular for Potential Games”. Economic Theory, Vol. 7, 81–93.
Quint T. and S. Shubik (1994). “A Model of Migration”. Working paper, Cowles Founda-
tion, Yale University.
Rosenthal R. W. (1973). “A Class of Games Possessing Pure-Strategy Nash Equilibria”.
International Journal of Game Theory, Vol. 2, 65–67.
Wooders M. H. (1989). “A Tiebout Theorem”. Mathematical Social Sciences, Vol. 18,
33–55.
View publication stats