MAGNITUDES OF PARETO INEFFICIENCY OFATOMIC AND NON-ATOMIC NASH EQUILIBRIA

Hisao Kameda

December 12, 2016
CS-TR-16-24

DEPARTMENT OF COMPUTER SCIENCE, UNIVERSITY OF TSUKUBATSUKUBA SCIENCE CITY, IBARAKI 305-8573, JAPANH. Kameda is with Department of Computer Science, University of Tsukuba, Tsukuba Science City, Ibaraki 305-8573, Japan.
Email: kameda@cs.tsukuba.ac.jp.

Magnitudes of Pareto Ineﬃciency of Atomic and Non-Atomic Nash
Equilibria
Hisao Kameda∗

Abstract
We present a measure that shows the magnitude of Pareto ineﬃciency, and show how to obtain it under certain
conditions. We prove that the price of anarchy (PoA) presents the magnitude of Pareto ineﬃciency of the unique Nashequilibrium in the case where the Nash equilibrium and the social optimum are both symmetric although utilities ofplayers may be asymmetric in other feasible states. That is, in that case, PoA is identical to the measure. Then we
study the general trend of how the magnitude of Pareto ineﬃciency depends on the number of non-cooperative players
in Nash equilibria, i.e., on the degree of dispersion in decision making. We examine a symmetric economic gameand a symmetric congestion game for examining the trend. We show, respectively, in the economic and congestion
games, the magnitude of Pareto ineﬃciency of the Nash and atomic Nash equilibrium (and also PoA therein) can
increase without bound.
Keywords: Pareto ineﬃciency, atomic and non-atomic Nash equilibrium, oligopoly, monopoly, perfect competition, congestion game, load balancing, Wardrop equilibrium, social optimum, price of anarchy.

1 Introduction
Decision makers in many systems can be regarded as players in games. Non-cooperative decisions which lead toNash equilibria have the advantage of independence and distribution of decision making. Non-cooperative decisions,however, may not always be beneficial. Nash equilibria may be Pareto ineﬃcient. It looks that the definition of
the magnitude of Pareto ineﬃciency has not been settled yet. In this article, we present a measure that shows themagnitude of Pareto ineﬃciency. Then, we examine how the magnitude of Pareto ineﬃciency of the Nash equilibrium
depends on the number of non-cooperative players.
The price of anarchy (Koutsoupias and Papadimitriou, 1999) is widely used for evaluating the degree of ineﬀectiveness of Nash equilibria. If the Nash equilibrium is unique, the price of anarchy, PoA, gives the ratio of the social
cost of the Nash equilibrium to that of the social optimum. In fact, however, it does not seem to have been rigorously
shown that PoA can serve as a measure that shows the magnitude of Pareto ineﬃciency of Nash equilibria for generalcases. In section 2, we prove that PoA can do so in the case where all players have the same values of utilities in theunique Nash equilibrium and the social optimum (symmetric, homogeneous), although other feasible system states
may be asymmetric (i.e., the utility of every player in each state may not be identical). We note that there can exist at
most one symmetric Nash equilibrium in each non-cooperative game. In the examples given in section 3, all players
have the same value of utilities in the Nash equilibrium and the social optimum, and then the measure of the magnitudeof Pareto ineﬃciency gives the same value as the price of anarchy.
The level of dispersion of decision making for systems reflects the number of non-cooperative players. In thisarticle, we think of various levels of non-cooperative decision making, that is, of various numbers of players in noncooperative games. In subsection 1.1, we examine the degrees in the dispersion of decision making or the number ofplayers in non-cooperative games.

1.1 Diﬀerent Degrees in the Dispersion of Decision Making
We can think of diﬀerent degrees in the dispersion of decision making.
∗ UniversityofTsukuba,

DepartmentofComputer

Science,kameda@cs.tsukuba.ac.jp

1

TsukubaScience

city,

Ibaraki

305-8573,

Japan,

E-mail:(A)[Completely centralized decision, monopoly]: There is only one decision maker or only one player. The
decision maker seeks to optimize a single social measure such as the overall utility or the total cost over all users(e.g., the expected sojourn time). If there are multiple users or agents in a system, then the only one decision makerdistributes the optimal benefit or cost among all users or agents. In the literature, the corresponding solution concept
is referred to as a system optimum, overall optimum, cooperative optimum or social optimum. In economics, thissituation is identical to that of monopoly. In this article, we call this optimum social optimum.
(B)[Intermediately dispersed decision, non-cooperative games with atomic players, oligopoly]: There are a
finite number (N(> 1)) of decision makers, agents, or players. Each decision maker optimizes non-cooperatively
his/her own utility or cost (e.g., the expected sojourn time). The decision of a single decision maker has a nonnegligible impact on the performance of other groups. We refer to the situation where each player’s decision has
a non-negligible impact on the system state as “atomic.” The situation where, in such a scheme, every player has
optimized his/her decision, given the decisions of other users, and furthermore, would not unilaterally deviate fromthis decision is called a Nash equilibrium. In this optimized situation, each of a finite number of players cannot receive
any further benefit by changing his/her decision. In the literature, the corresponding solution concept is referred to asa class optimum or Nash equilibrium with atomic players. This situation is identical to that of oligopoly in economics.
We may have diﬀerent levels in intermediately dispersed optimization according to the size of N. In this article, wecall this equilibrium atomic Nash equilibrium.
(C)[Completely dispersed decision, non-cooperative games with non-atomic players, perfect competition]:In this situation, the decision of a single decision maker has a negligible, infinitesimal impact on the performance ofthe entire system, since, probably, the number of such players is so large. In contrast, the status of the entire system
is determined from the whole decisions made by all players. We refer to the situation as “non-atomic.” Each player
optimizes his/her own utility or cost (e.g., his/her own expected sojourn time), independently and selfishly of theothers. In this optimized situation, each player cannot expect any further benefit by changing his/her own decision.
The situation where every infinitesimal player has optimized his/her decision, given the entire system status, andwould not unilaterally deviate from that choice, is called individual optimum, Wardrop equilibrium, or user optimum(Wardrop, 1952; Haurie and Marcotte, 1985; Patriksson, 1994) etc.). This situation is identical to that of perfectcompetition in economics. In this article, we call this equilibrium non-atomic Nash equilibrium.
Note that (B) is reduced to (A) when the number of players reduces to 1 (N = 1) and approaches (C) when thenumber of players increases without bound (N → ∞) (Haurie and Marcotte, 1985). In the cases of (B) and (C), there
are multiple players or independent decision makers and they can be regarded as ‘non-cooperative games.’

1.2 Pareto Superiority and Eﬃciency
We think that, for each state of the system, the utility (or cost) of each player is determined. We recall the definition of superiority/inferiority among system states as presented in the following paragraph. The notions of Pareto
superiority/inferiority and optimality/ineﬃciency have already been established, and we confirm the notions and theirdefinitions.
[Pareto superiority and inferiority]: We consider a system consisting of a number of users or players n, where ndenotes the set {1, 2, · · · , n}. Denote by S the system state (s1 , s2 , · · · , sn ) where si denotes the decision made byplayer i, i ∈ n. Denote by S the set of feasible system states each of which presents a realizable combination of player
decisions. For each state of the system, each player has his/her own utility. Denote a combination of utilities of all
players in a system state S ∈ S by U(S ) = (U1 (S ), U2 (S ), . . . , Un (S )). In general, we consider the cases where Ui (S )has a positive real value, Ui (S ) > 0, for all i ∈ n, S ∈ S.
Consider an arbitrary pair of two (achievable) states of the system, S a , S b , ∈ S. If Ui (S a ) ≤ Ui (S b ) for all i ∈ n
and U j (S a ) < U j (S b ) for some j ∈ n, then S a is Pareto inferior to S b and S b is Pareto superior to S a . In the cases
where Ui (S a ) = U(S a ) and Ui (S b ) = U(S b ) for all i ∈ n, that is, the resulting utility of every player is identical(symmetric) within each state, the degree of Pareto inferiority (superiority) between them can simply defined to be, forexample, U(S a )/U(S b ). In general (including asymmetric cases), however, the Pareto superiority/inferiority relations
induce partial ordering in the set of system states and is not subject to total ordering or single scalar measure, like the∑∑ratio, p U p (S a )/ p U p (S b ), of the social cost of state S b to that of S b . Therefore, we may rely on more complicatedmeasures such as follows. A definition of the measure of Pareto superiority/inferiority, respectively, of state S a to S b
has been given as (Kameda, 2009; Kameda, 2013)
P/ (S a , S b ) , min U p (S a )/U p (S b ) and Q/ (S a , S b ) , min U p (S b )/U p (S a )
p∈n

p∈n

2

(1)

Then, P/ (S a , S b ) < and ≥ 1, respectively, if S a is Pareto inferior/indiﬀerent and superior to S b . Q/ (S a , S b ) < and ≥ 1,
respectively, if S a is Pareto superior/indiﬀerent and inferior to S b .
[Pareto optimality and eﬃciency]: If there exists no system state that is Pareto superior to a system state, the latterstate is called a Pareto optimum or eﬃcient state. If there exists some system state that is Pareto superior to a system
state, the latter state is called a Pareto ineﬃcient state. In general, multiple Pareto-optimal states may exist for a system.
An overall (or social) optimum is evidently Pareto optimum. Non-atomic Nash equilibria (Wardrop equilibria) andNash equilibria may be Pareto optimal or ineﬃcient.

2 Magnitudes of the Pareto ineﬃciency of Nash Equilibria[The magnitude of Pareto ineﬃciency]: We consider such a definition of the degree of Pareto inferiority Q(S , S b ) of
system state S to S b that satisfies the following: Q(S a , S b ) < and ≥ 1, respectively, if S a is Pareto superior/indiﬀerent
and inferior to S b . Q/ (S , S b ) given in relation (1) is an example of this. Then, naturally, we have the magnitude of
Pareto ineﬃciency of a system state S a , simply by
MoI(S a ) , max Q(S a , S )
S ∈S

(2)

(the larger magnitude for the greater ineﬃciency). It shows the maximum ratio in which the Pareto ineﬃcient state
can be improved.
Proposition 1 MoI(S ) = 1 if S is Pareto optimal, and MoI(S ) ≥ 1 if S is Pareto ineﬃcient. Thus, MoI(S ) can serve
as a measure of the magnitude of Pareto ineﬃciency of system state S .
[Proof] If S a is Pareto optimal, then Q(S , S a ) < 1 for all S , S a , and Q(S a , S a ) = 1, and thus MoI(S a ) = 1. If S a isPareto ineﬃcient, then Q(S , S a ) ≥ 1 for some S , S a , and thus MoI(S a ) ≥ 1.
On the basis of the definition on Pareto inferiority given in relation (1), a definition of the magnitude of Pareto ineﬃciency MoI(S a ) of a system state S a is given as
max min U p (S )/U p (S a ) for the utility base andS ∈S p∈n

max min C p (S a )/C p (S ) for the cost base
S ∈S p∈n(3)where Ci (S ) denotes the cost for player i in system state S (Legrand and Touati, 2007).
Define the weighted sum of the utilities of players for state S ∈ S with constant V > 0:∑
O(U(S ), V) =U p /V p where V = (V1 , V2 , · · · , Vn ), Vi > 0, i ∈ n.

(4)p

Theorem 1 Given a system state S̀ with each player’s utility U(S̀ ) = (Ù1 , Ù2 , . . . , Ù N ), we have the weighted social
optimum U(S̄ ) = (Ū1 , Ū2 , . . . , Ū N ) such that O(U(S̄ ), U(S̀ )) = maxS ∈S O(U(S ), U(S̀ )). Assume that we can arrange
such that Ūi /Ùi = Ū/Ù, i ∈ n. The magnitude of Pareto ineﬃciency, MoI(S̀ ), of S̀ is obtained such that MoI(S̀ ) =Ū/Ù. In this case, MoI(S̀ ) = 1 and > 1, respectively, if S̀ is Pareto optimal and ineﬃcient. Thus, the magnitude of
Pareto ineﬃciency, MoI(S̀ ), of S̀ determines the Pareto optimality of state S̀ .
[Proof] Note that O(U((S̄ ), U(S̀ )) = maxS ∈S O(U(S ), U(S̀ )), and that we arrange such that Ūi /Ùi = Ū/Ù, i ∈ n.
Consider another state S ′ ∈ S. Since S̄ is the weighted social optimum, then O(U(S ′ )) ≤ O(U(S̄ )). Therefore,
there must exist some i (i ∈ n) such that Ui′ /Ùi ≤ Ūi /Ùi = Ū/Ù. Then, Q(S̀ , S ′ ) = min p U ′p /Ù p ≤ Ū/Ù. ThenMoI(S̀ ) = max[{maxS ∈S Q(S̀ , S )}, Ū/Ù] = Ū/Ù. Thus, the magnitude of Pareto ineﬃciency MoI(S̀ ) of Ù is given by
Ù/Ū. The last two statements are clear from the relation between U(S̀ ) and U(S̄ ).

As to the existence of such a weighted social optimum Ū that Ũi /Ūi = Ũ/Ū, i ∈ n, for a Nash equilibrium, Ũ, we
refer to the Nash equilibrium based fair allocation (Kameda, Altman, Touti and Legrand, 2012).
Furthermore, we have the following:3

Corollary 1 Assume that we have a Nash equilibrium S̃ with each player’s utility U(S̃ ) = (Ũ1 , Ũ2 , . . . , Ũ N ), that issymmetric, Ũi = Ũ, i ∈ n. Let the social optimum U(S̄ ) = (Ū1 , Ū2 , . . . , Ū N ) such that O(U(S̄ ), 1) = maxS ∈S O(U(S ), 1),
where 1 = (1, 1, · · · , 1). Assume that we can arrange such that Ūi = Ū, i ∈ n (the symmetric social optimum). Then,the magnitude of Pareto ineﬃciency MoI(S̃ ) of S̃ is obtained such as Ū/Ũ. MoI(S̃ ) = 1 and > 1, respectively, if S̃
is Pareto optimal and ineﬃcient. That is, the magnitude of Pareto ineﬃciency, MoI(S̃ ), of S̃ determines the Pareto
optimality of state S̀ .
In subsections 3.1 and 3.2, we see examples of social optimum S̄ , that is (arranged to be) symmetric, Ūi = Ū, i ∈ n.
By using the above corollary 1, we have MoI(S̃ ) = Ū/Ũ for the utility base scheme and MoI(S̃ ) = C̃/C̄ for the costbase scheme.
The price of anarchy, PoA, for the case of unique Nash equilibrium S̃ (the ratio of the social cost of the Nash∑∑equilibrium to that of the social optimum) is PoA , p C̃ p / p C̄ p . If both of U(S̃ ) and U(S̄ ) are symmetric, then
PoA = C̃/C̄, which is the same as MoI(S̃ ).
Corollary 2 The price of anarchy presents the magnitude of Pareto ineﬃciency of the unique Nash equilibrium if
the utility of each player is the same (symmetric) within the Nash equilibrium and if that of each player is the same
(symmetric) within the social optimum, although the utilities of feasible states may not necessarily be symmetric.
The price of anarchy and the magnitude of Pareto ineﬃciency of the unique Nash equilibrium determines the Pareto
optimality of the Nash equilibrium.
Consider the following congestion game: The network consists of an origin, a destination and paths (series of links)
connecting the origin and the destination (simple examples are the Braess and Pigou networks (Braess, 1968; Pigou,
1920). Packets are forwarded from the origin to the destination. The cost for each packet is the sojourn (passage) timethrough the origin and the destination. By suitably assigning packets to the atomic and non-atomic players, we canobtain symmetric costs for players in the unique Nash equilibrium and in the social optimum. Then, we can apply theabove corollary 2, and we see that the price of anarchy presents the magnitude of Pareto ineﬃciency of the congestion
game. In the examples given in the subsections 3.1 and 3.2, we see the social optimum and the Nash equilibria aresymmetric, and then we can apply the corollary 1 to the examples.
[Pareto ineﬃciency of atomic and non-atomic Nash equilibria]: It is evident that the social optima are Pareto
optimal. Both atomic and non-atomic Nash equilibria may be Pareto ineﬃcient, as exemplified in the Braess paradox
on transportation and communication networks (Braess, 1968; Murchland, 1970; Frank, 1981; Cohen and Kelly, 1990;
Cohen and Jeﬀries, 1997; Korilis, Lazar and Orda, 1995; Korilis, Lazar and Orda, 1999; Kameda, 2002; Kameda,
2009)), and in the Braess-like paradox on distributed computer systems (Kameda, Altman, Kozawa and Hosokawa,
2000; Kameda and Pourtallier, 2002), and in the well-known prisoners’ dilemma, etc.
[Atomic Nash equilibria] It has been shown that, if the utility function of each player is twice continuously
diﬀerentiable, Nash equilibria are generally Pareto ineﬃcient in smooth games with the finite number of players(Smale, 1973; Dubey, 1986). In addition, the magnitude of Pareto ineﬃciency of some atomic Nash equilibria canincrease without bound as seen in the congestion game given in subsection 3.2. Thus, one may think that atomic Nashequilibria are more likely Pareto ineﬃcient.
[Non-atomic Nash equilibria] In contrast, there have been studies that seek the bounds of the magnitude of Pareto
ineﬃciency of non-atomic Nash equilibria for congestion games as in (Roughgarden and Tardos, 2004a; Roughgarden
and Tardos, 2004b). Furthermore, we have not seen the cases where the magnitude of Pareto ineﬃciency of non-atomic
Nash equilibria can increase without bound. Moreover, we note that there exist a class of schemes given in general
economic theory called Walrasian equilibria (under perfect competition) that have been shown to be Pareto optimal(well known as the first fundamental theorem of welfare economics) (Arrow, 1951; Debreu, 1951). The Walrasian
schemes depend on the pricing mechanism with perfect competition where each of consumers and producers behaves
as a price-taker and can have only infinitesimal eﬀects on the prices by changing his/her decision. These schemes are
regarded as examples of Pareto-optimal non-atomic Nash equilibria.
The above mentioned situations around atomic vs. non-atomic Nash equilibria may bring us such a conjecturethat the magnitudes of Pareto ineﬃciency in atomic Nash equilibria may, on the whole, be greater than those of nonatomic Nash equilibria. This conjecture is betrayed as follows. We can see the cases where the magnitudes of Pareto
ineﬃciency of atomic Nash equilibria, respectively, decreases and increases as the number of player N increases in thegames given in the examples in the subsections 3.1 and 3.2. In addition, we see in the subsection 3.1 that the magnitudeof Pareto ineﬃciency of non-atomic Nash equilibria for some economic games can increase without bound.
4

3 Examples
We present case studies on two games, economic and congestion.

3.1 Monopoly, Oligopoly and Perfect Competition — An Economic Model
Herein we investigates a system consisting of a market and multiple producers that produce a commodity of thesingle kind, i.e., a Cournot oligopoly game wherein the players that make decisions are producers. Each producer
optimizes his/her profit in producing the amount of commodity demanded in the market. In this game, consumers are
not regarded as separate players. Their behaviors are reflected in the demand function that determines the price of thecommodity.
3.1.1 The Model and Assumptions
The system considered here consists of n producers and a market. Producers are numbered 1, 2, · · · , n. Denote by n
the set {1, 2, · · · , n}. All producers produce the homogeneous commodity, and in each market, the consumers demand
it. Consider the three cases as to the market.
1) Monopoly: Each producer follows the decision by only one decision maker.
2) Oligopoly: Each producer makes unilaterally his/her own decision. His/her decision may have non-negligible
impact on the price.
3) Perfect competition: Each producer makes decision given the price to which he/she can exercise only infinitesimal influence. Each producer behaves as the price-taker, and the price is determined by the total amountof the commodity demanded and produced.
Let qi (qi ≥ 0) denote the quantity that producer i produces, i ∈ n. Define vector q such that q , (q1 , q2 , · · · , qn ). qi is∑the variable determined by producer i. i ∈ n. Then, we assume an inverse demand function such as p = a(1 − j q j /b)(a, b > 0,), where a is the upper bound of the price in the market and b is the upper bound of the( demand for) the∑commodity in the market. For the market, if the price is p, the quantity demanded is given by p = a 1 − j q j /b .
Assume that the cost that producer i produces the amount qi of the commodity is cqi . c represents the marginalcost.
∑1) Monopoly: The profit Pi0 of producer i is the following: Pi0 = a{1 − ( j q j )/b}qi − cqi .
∑∑Then the total sum of the profits of producers is P0 (q) = j P0j = a(1 − q/b)q − cq, where q = j q j .
Therefore, the optimal decision by the monopolized producers is expressed as: max q P0 .
Denote by q̄ = (q̄1 , q̄2 , · · · , q̄n ), the set of values of q1 , q2 , · · · , qn that satisfy P0 ( q̄) = max q P0 (q).
2) Oligopoly: The above case 2) can be regarded as a game where the producers are players and where
the profit() of each∑ii
producer i is the utility of the player i, i ∈ n. The profit P of producer i is the following: P = a 1 − j q j /b qi − cqi .
Therefore, the optimal decision by producer i is expressed as follows: maxqi Pi .
Denote by q̃ = (q̃1 , q̃2 , · · · , q̃n ) such values of q1 , q2 , · · · , qn that satisfy, for i ∈ n,
Pi ( q̃) = max Pi (q̃1 , · · · , q̃i−1 , qi , q̃i+1 , · · · , q̃n ), given q̃1 , · · · , q̃i−1 , q̃i+1 , · · · , q̃n .
qi(5)

If the system has such a solution q̃ of q that satisfies (5) for all i at the same time, it is an atomic Nash equilibrium.
∑3) Perfect competition: Denote by Q be p q p . The profit Pi0 of producer i is the following: Pic = a(1 − Q/b)qi − cqi .
Each producer increases qi as far as a(1 − Q/b) > c, which finally results in Q = Q̂ = b(a − c)/a.
Then, the profit of each producer i is Pic (q) = 0.
∑
Denote by q̂ = (q̂1 , q̂2 , · · · , q̂n ), the set of values of q1 , q2 , · · · , qn that satisfy p q̂ p = Q̂.
Pic ( q̂) = 0, i ∈ n, which is unique irrespectively of the variety of q̂.
Consider a group of systems for which the values of parameters, a, b and c, satisfy the following constraints:a ≥ c > 0, b > 0, so that the market can be established.
Denote the set of parameter values that satisfy the above constraints by C.
Producer profit and consumer surplus: Define the following. R̃i = Pi ( q̃), R̄i = Pi0 (q̄i ) and R̂i = Pic (q̂i ) = 0.
R̄i , R̃i , and R̂i , respectively, denote the values of the profit for producer i in monopoly, in oligopoly and in perfect5competition. R̄i = R̄, R̃i = R̃, and R̂i = R̂ because of the symmetry. C̄, C̃ and Ĉ, respectively, denote the values of
the consumer surplus for the market in monopoly, in oligopoly and in perfect competition. kiR and kC , respectively,
denote the ratios, of the profits for producer i and of the consumer surplus, of monopoly to those of oligopoly. That is,kiR = R̄i /R̃i = R̄/R̃ = kR and kC = C̄/C̃.
3.1.2 The Resultsi
The profit optimization
The partial∑ ) of P0 and P are:()( derivatives
i
∂P0
2q
∂P
aqi
j qj
=a 1−
− c,
=a 1−
−
− c, i ∈ n.
∂q
b
∂qi
b
b
Therefore, the optimal decisions and the price, of monopoly and oligopoly, respectively, satisfy the following.
a (1q̄/b) − c = 0 }and p̄ = a (1 − q̄/b), whereq̄i = q̄/n, )i ∈ n,
{ − 2∑(∑
a 1 − ( j q̃ j + q̃i )/b − c = 0, i ∈ n, p̃ = a 1 − ( j q̃ j )/b .
Then,

a−c
a+c
≥ 0, p̄ =, i ∈ n,
2na/b
2
a−c
q̃i =
≥ 0, i ∈ n,(n + 1)a/b∑n(a − c)a + ncq̃ j => 0, p̃ =,(n+1)a/(b)
n+1
j
q̄i =

(6)
(7)
(8)

The inequalities in the above relations come from the constraints C. In particular, that of (6) comes from the assumptionthat the market can be established in monopoly, that of (7) comes from the assumption that producer i may play somerole in oligopoly, and that of (8) comes from the assumption that at least one producer may produce non-zero amountof products in oligopoly.
Profits of producers The profits of producer i, in monopoly, in oligopoly and in perfect competition, are, respectively,aq̃2(a − c)2 bb(a − c)2R̄i = R̄ = P0 (q̄i )/n =(i ∈ n) and R̂i = R̂ = 0.
(i ∈ n), R̃i = R̃ = Pi ( q̃) = i =4naba(n + 1)2
Since the producer profits of the social optimum (monopoly), the atomic Nash equilibrium (oligopoly), and the
non-atomic Nash equilibrium (perfect competition) are symmetric and unique, we can use the corollary 1. Therefore,
the magnitude of, kR , of Pareto ineﬃciency of the oligopoly is as follows: kR = R̄/R̃ = (n + 1)2 /(4n).
Remark 1 Thus the magnitude of Pareto ineﬃciency of the atomic Nash equilibrium kR decreases as the number ofplayers n decreases and finally it reaches the Pareto optimality of the social optimum (n = 1). kR increases as thenumber of players n increases and finally up to that, ∞, of the non-atomic Nash equilibrium (n → ∞).
Note that, in the Nash equilibria and the social optimum of this game, the profit of every player (producer) is
unique and symmetric within each equilibrium and optimum. Thus, we can apply the corollaries 1 and 2 to this model.
Theorem 2 There exist economic games where the magnitudes of Pareto ineﬃciency of atomic and non-atomic Nashequilibria (and the price of anarchy) can increase without bound.
Consumer surpluses The consumer surplus in each market is as follows. Define Z = 1 − c/a.
In monopoly, the consumer surplus for the market is C̄ = (1/2)q̄(a − p̄) = abZ 2 /8.
In oligopoly, the quantity, q̃(c) of the commodity that the consumers in the market consume is to be b(1 − p̃/a). Then,(∑ )2
the consumer surplus for the market is C̃ = (1/2)q̃(c) (a − p̃) = {a/(2b)} j q̃ j = [abn2 /{2(n + 1)2 }]Z 2 .
In perfect competition, the consumer surplus for the market is Ĉ = (1/2)Q(a − p̂) = abZ 2 /2.
Therefore, the ratio, kC , of consumer surplus improvement for the market from that of monopoly to that ofoligopoly is: kC = C̄/C̃ = (n + 1)2 /(4n2 ).
Remark 2 (n + 1)2 /(4n2 ) decreases slowly in n, and (n + 1)2 /(4n2 ) → 1/4 as n → ∞. Therefore, as the numberof producer n increases, the ratio of consumer surplus improvement 1/kC from that of monopoly to that of oligopoly
increases, and finally the system approaches the situation where the consumers enjoy the consumer surplus in perfectcompetition, that is, 4 times of that in monopoly.
6

3.2 Load Balancing in a Two Symmetric Node Model — A Congestion Game
3.2.1 The Model and Assumptions
We consider a model consisting of two identical servers (nodes) and a communication means that connects bothservers. Servers are numbered 1 and 2 (Fig. 1). Jobs (or customers) are classified into 2n classes Rik , i = 1, 2, k =1, 2, · · · , n. Jobs of class Rik arrive only at server i with identical rate 1/n, Out of each class arrival, the rate xik ofjobs are forwarded upon arrival through the communication means to the other server j (i , j) to be processed there.
Therefore the remaining rate 1/n − xik of class Rik jobs are processed at server i. We have 0 ≤ xik ≤ 1/n, i = 1, 2.
We denote the vector (x11 , x12 , · · · , x1n , x21 , x22 , · · · , x2n ) by x. We denote the set of x’s that satisfy the constraints
by C . Within these constraints, a set of values of xik (i = 1, 2, k = 1, 2, · · · , n) are chosen to achieve optimization.
∑∑
Thus the load βi on server i is given by βi = 1 − l xil + l x jl , (i , j). Then, the expected processing (including
queueing) time Di (βi ) of a job that is processed at server i (or the cost function at server i) is Di (βi ) = 1/(µ − βi ) forβi < µ (otherwise it is infinite) (We have a simple assumption of the external time-invariant Poisson arrival for eachclass, and the exponentially distributed service times for each class jobs with identical service rate µ at both servers.)
As to the communication means, we consider two communication lines 1 and 2 separately for each server. One
line i is used for forwarding of a job that arrives at server i. The expected communication time of a job arriving atserver i and being processed at server j (, i) is expressed simply as t, i.e., independent of the traﬃc and the job classand with no queueing delay.
β1

β2

1
µ−β1

1
µ−β2

server 1

server 2tt

Figure 1: The system model.
We refer to the length of time between the instant when a job arrives at a server and the instant when a job leaves
one of the servers after all processing and communication, if any, are over as the sojourn time for the job.
Thus the expected sojourn time of a class Rik job that arrives at server i is1
T ik (x) = n{( − xik )T iik (x) + xik T i jk (x)},n(9)

where T iik (x) = Di (βi ) and T i jk (x) = D j (β j ) + t, for j , i. (The above expressions hold, again, only for positive valuesof denominators, and are otherwise infinite.)
Then, the overall expected sojourn time of a job that arrives at the system is
1 ∑T (x) =
T ik (x).
(10)
2n i,k
3.2.2 The Results
We have three optima, the social optimum, the non-atomic Nash equilibrium, and the atomic Nash equilibrium, as in
the following.
(1) [Completely centralized optimization — social optimum] The social optimum is given by such x̄ as satisfies thefollowing: T ( x̄) = min T (x) with respect to x ∈ C .
The solution x̄ is unique and simply given as follows: x̄ = 0, i.e., x1k = x2k = 0 for all k and T ( x̄) = T ik ( x̄) =1/(µ − 1), i = 1, 2, k = 1, 2, · · · , n.
This is intuitively clear. Or, this can be easily seen if we note that, since the overall mean sojourn time T (x) is expressed as follows from (9) and (10): 2T (x) = 2µ(µ − 1)/{(µ − 1)2 − d2 } + st − 2,7

where d =∑l (x1l − x2l ) and s =∑l (x1l + x2l ), T (x) is minimum if and only if x1k = x2k = 0 for k = 1, 2, · · · , n.

(2) [Completely distributed optimization — non-atomic Nash equilibrium] The non-atomic Nash equilibrium (orWardrop equilibrium) is given by such x̂ as satisfies the following for all i, k
T ik ( x̂) = min{T iik ( x̂), T i jk ( x̂)} (i , j) such that
The solution x̂ is unique and given as follows: x̂ = 0, i.e., x̂1k = x̂2k = 0,
And, again, T ( x̂) = T ik ( x̂) = 1/(µ − 1), for all i, k,x̂ ∈ C .

(11)

for all k,[Proof] The solution x̂ for (11) is characterized as follows:
D1 (β̂1 ) > D2 (β̂2 ) + t,
D1 (β̂1 ) = D2 (β̂2 ) + t,x̂1k = 1/n
0 ≤ x̂1k ≤ 1/n

(12)
(13)

D1 (β̂1 ) < D2 (β̂2 ) + t,
D2 (β̂2 ) > D1 (β̂1 ) + t,
D2 (β̂2 ) = D1 (β̂1 ) + t,x̂1k = 0x̂2k = 1/n
0 ≤ x̂2k ≤ 1/n

(14)
(15)
(16)

D2 (β̂2 ) < D1 (β̂1 ) + t,x̂2k = 0(17)

for all k. We can easily see that these are satisfied if and only if x̂1k = x̂2k = 0 for all k, by noting that, for example,(12) and (13) contradict with any of (15), (16), and (17), and thus that only (14) and (17) can hold together.
(3) [Intermediately distributed optimization — atomic Nash equilibrium] The atomic Nash equilibrium is given bysuch x̃ as satisfies the following for all i, k, T ik ( x̃) = min xik T ik ( x̃−(ik) ; xik ), such that ( x̃−(ik) ; xik ) ∈ C .
where ( x̃−(ik) ; xik ) denotes the 2n vector in which the element corresponding to x̃ik has been replaced by xik .
(A) The case where t > 1/{n(µ − 1)2 }: The solution x̃ is unique and given as follows: x̃ = 0, i.e., x̃1k = x̃2k =0, for all k.
And, again, T ( x̃) = T ik ( x̃) = 1/(µ − 1), i = 1, 2, k = 1, 2, · · · , n.
(B) The case where t ≤ 1/{n(µ − 1)2 }: The solution x̃ is unique and given as follows:x̃1k = x̃2k =1 1{ − t(µ − 1)2 }, for all k.
2 n

(18)

And in that case, we haveT ( x̃) = T 1k ( x̃) = T 2k ( x̃)1t=+ {1 − nt(µ − 1)2 }, for all k.
µ−1 2

(19)

[Proof] From the definition (9) we have
∑
n−1 ∑
+
xil −
x jl
n
∂T ik
l,k
l
∑
∑
=−
(1/n)
∂xik
x jl )2xil −(µ − 1 +
µ−

l

l

µ−1−
+

∑

xil +

∑

x jl

l

l,k

(µ − 1 −

∑

xil +

∑

x jl )2+t(i , j).

(20)

l

l

∂T ik
is monotonically increasing with the increase in xik with feasible x ∈ C .
∂xikThus if we can find a set of such values of x̃ that satisfies

By simple inspection of (20), we see that∂T ik( x̃) = 0, for all i, k,
∂xik
8

(21)

then the set of values is a solution of the atomic Nash equilibrium. We have from (20) and defining d =∑l (x1l − x2l )∑∂T 1l ∂T 2l(1/n){
−
}
∂x1l
∂x2l
l
2nµ − (2n − 1)(1 + d) 2nµ − (2n − 1)(1 − d)−(µ − 1 − d)2(µ − 1 + d)22d2µ(µ − 1)=()(+ 2n − 1),(µ − 1)2 − d2 (µ − 1)2 − d2=

(22)

If condition (21) holds, then from (22), we have d = 0. Then from (20) we have
(1/n)

∂T ik 2xik − 1/n=+ t = 0, (i , j) for all i, k.
∂xik(µ − 1)2(23)

Therefore xik = (1/2)(1/n − t(µ − 1)2 ) for all i, k if t ≤ 1/{n(µ − 1)2 }.
From the above derivation, it is clear that this is a unique solution (in case (B)).

1 ∂T ik1
If t > 1/{n(µ − 1)2 } (in case (A)), we have from (23) when xik = 0, for all i, k, ( )= t−>n ∂xikn(µ − 1)2
0, for all i, k.
∂T ik
is monotonically increasing with xik , we have that x̃ik = 0, for every i, k, is an atomic Nash
Considering that∂xik
equilibrium solution.
We can easily see the uniqueness as in the following. Suppose x̃1k > 0 for some k. From definitions on d and by(20) we have thenn−1µ−
+ d − x̃1k µ − 1 − d + x̃
∂T 1k
1k
n
(1/n)
=−
+
+ t = 0.
∂x1k(µ − 1 + d)2(µ − 1 − d)2(24)

Then from the above and condition on t we have{11+)} x̃1k2(µ − 1 + d)(µ − 1 − d)22d1= −t −+(µ − 1)2 − d2 n(µ − 1 + d)2
1
1
2d
<
−
−
.
n(µ − 1 + d)2 n(µ − 1)2 (µ − 1)2 − d2(25)This implies d < 0 for which there must exist some nonzeo x2k′ . Then by using the argument similar to the above on
x2k′ we have d > 0, which is a contradiction. Thus x̃ = 0 is the unique atomic Nash equilibrium solution.
For the proofs of the existence and uniqueness of those optima for more general setting, see (Altman and Kameda,
2005; Altman, Kameda and Hosokawa, 2002; Orda, Rom and Shimkin, 1993).

A proof for the model more general than the one presented here has been given, but it covers more than 5 journal
pages and will take much time to follow (Kameda and Pourtallier, 2002). Then, herein, we show a proof specific tothis special model and much simpler than the general proof.
Remark 3 Consider the case (B) in the atomic Nash equilibrium. In this case, the atomic Nash equilibrium is Pareto
ineﬃcient. In contrast, the solutions of the social optimum, the non-atomic Nash equilibrium and the atomic Nashequilibrium in case (A) are identical and all Pareto optimal. As n increases in the atomic Nash equilibrium with case(B) (see eq. (19)), T ( x̃) decreases as far as t ≤ 1/{n(µ − 1)2 } holds. Then, as n increases further, t > 1/{n(µ − 1)2 } (case(A)) holds and T ( x̃) becomes the same as those of the social optimum and the non-atomic Nash equilibrium. Since
the solutions of the social optimum and the Nash equilibrium are symmetric, we can use the corollary 1. Thus themagnitude of Pareto ineﬃciency of the atomic Nash equilibrium decreases as the number of players 2n increases andfinally it reaches the non-atomic Nash equilibrium that is Pareto optimal. On the other hand, we cannot let the atomic
Nash equilibrium be down to the social optimum since we cannot reduce the number of atomic players 2n down to 1.

9Furthermore, we can easily see that T ik ( x̃)(= T ( x̃)), for every i, k, has its maximum T̃ (µ, n) (i.e., the worst-caseperformance) for given µ, n.
1
1T̃ (µ, n) =
{1 +
},
(26)
µ−1
8n(µ − 1)
when
t=

1
.
2n(µ − 1)2(27)

Thus if we add the communication lines with delay t (= 1/{2n(µ − 1)2 }) to the system that has had no communi1
cation means, the expected sojourn time of each class (player) T ik ( x̃) increases in the amount of(i.e., the8n(µ − 1)2
performance degrades).
The magnitude of Pareto ineﬃciency of the atomic Nash equilibrium for given µ, n is to be∆(µ, n) =T̃ (µ, n),
T 0 (µ)(28)

where T 0 (µ) = 1/(µ − 1) denotes the mean sojourn time of the social optimum for given µ. Then we have∆(µ, n) = 1 +1.
8n(µ − 1)(29)

Remark 4 Consider the atomic Nash equilibrium with the case (B). In this case, each player forwards a part ofhis/her jobs through the communication means to the other server for remote processing, and thereby has degradationin his/her mean sojourn time. The ratio of such degradation, and thus the magnitude of Pareto ineﬃciency can increase
without bound as the total arrival rate approaches the processing capacity of each server. Diﬀerently from the economic
game presented in subsection 3.1, herein the increase without bound of MoI may occur for all i > 1 but with theapproach of the job processing capacity µ of the nodes to the job arrival rate 1.
Note that, in the Nash equilibria and social optimum of this game, the cost of every player is unique and symmetricwithin each equilibrium and optimum. Thus, we can apply the corollaries 1 and 2 to this model.
Theorem 3 There exist congestion games where the degrees of Pareto ineﬃciency of atomic Nash equilibria (and theprice of anarchy) can increase without bound.
3.2.3 Numerical Examples
For example, we examine the following case: µ = 1.01. Then the mean sojourn time is T 0 (µ) = 1/(µ − 1) = 100 in
the social optimum, in the non-atomic Nash equilibrium (Wardrop equilibrium), and in the case of no communicationline and no forwarding of jobs.
1400

mean response time

1200
1000
800
600
400
200
0

0

2000

4000

6000

8000 10000 12000 14000

mean communication time

Figure 2: The mean response (sojourn) times for each class jobs (player) in the atomic Nash equilibria (or Nashequilibria) with µ = 1.01 and n = 1 for the various values of mean communication time t. We see that, in theparadoxically worst case, adding the communication means with t = 5000 to the system increases the mean response(sojourn) time up to 1350 from 100, that of no communication means.

10mean response time

120
100
80
60
40
20
0

0

200

400

600

800

1000

1200

1400

mean communication time

Figure 3: The mean response (sojourn) times for each class jobs (player) in the atomic Nash equilibria (or Nashequilibria) with µ = 1.01 and n = 100 for the various values of mean communication time t. We see that, in theparadoxically worst case, adding the communication means with t = 50 to the system increases the mean response(sojourn) time up to only 112.5 from 100, that of no communication means.

Firstly, we consider the case where n = 1, i.e., the number of classes is 2. The mean sojourn time of the atomic
Nash equilibria (Nash equilibrium) for various values of t is shown in Fig. 2.
As we can see from the figure, T = T ik takes its maximum valueT̃ (µ, n) = 1350 (see(26))
and the magnitude of Pareto ineﬃciency (the worst-case ratio of the performance degradation) ∆(µ, n) is∆(µ, n) = 13.50 (i.e., 1350% degradation) (see (28))
when t = 1/{2(µ − 1)2 } = 5000 (see (27)). Thenx̃1k = x̃2k = (1/2){1 − t(µ − 1)2 } = 1/4 (k = 1) (see (18)). In this case, x̃1k = x̃2k decrease from 1/2 down to 0 as tincreases from 0 to 10000 (= 1/(µ − 1)2 ), and for t > 10000, no forwarding of jobs occurs.
It is amazing that, in the Nash equilibrium, each class (player) keeps to forward a part of his/her jobs to the otherserver even though the communication delay for forwarding is much greater than the processing delay at the server atwhich his/her jobs arrive.
Then we consider the case where n = 100, i.e., the number of classes is 200.
The mean sojourn time of the atomic Nash equilibria (Nash equilibrium) for various values of t is shown in Fig. 3.
As we can see from the figure, T = T ik takes its maximum value T̃ (µ, n) = 112.5 (see(26)) and the magnitude of
Pareto ineﬃciency ∆(µ, n) is ∆(µ, n) = 1.125 (i.e., 12.50% degradation) (see (28)) when t = 1/{2n(µ − 1)2 } = 50
(see (27)). Thenx̃1k = x̃2k = (1/2){1/n − t(µ − 1)2 } = 1/400 for all k (see (18)).
In this case, x̃1k = x̃2k decrease from 1/200 down to 0 as t increases from 0 to 100 (= 1/(µ − 1)2 ), and for t > 100,
no forwarding of jobs occurs.
Thus we see that the magnitude of Pareto ineﬃciency is greatly reduced from the case of n = 1.
Furthermore we consider other values of µ with n = 1.
For µ = 1.001, ∆(µ, n) = 126 (i.e., 12600% degradation), andfor µ = 1.00001, ∆(µ, n) = 12501 (i.e., 1250100% degradation), etc.
In this way, we see that the magnitude of Pareto ineﬃciency ∆(µ, n) can increase without bound as µ approaches 1
with n = 1.

4 Concluding Remarks
We have tried to make clear the definition of the magnitude of Pareto ineﬃciency of Nash equilibria. We have proventhat the price of anarchy (PoA) presents the magnitude of Pareto ineﬃciency of the unique Nash equilibrium in the11case where the Nash equilibrium and the social optimum are both symmetric although utilities of players may beasymmetric in other feasible states. Then we have observed the way how the magnitude of Pareto ineﬃciency depends
on the degree of dispersion of decision making, i.e., the number of non-cooperative players in Nash equilibria. We haveexamined a simple economic game and a simple congestion game for examining the trends on the magnitude of Pareto
ineﬃciency of atomic and non-atomic Nash equilibria. We have shown, respectively, in the economic and congestion
games, the magnitude of Pareto ineﬃciency of the Nash and atomic Nash equilibrium (and also PoA therein) can
increase without bound.

Acknowledgment
This study is supported in part by the Grant-in-Aid for Scientific Research of Japan Society for the Promotion of
Science.

References
Altman, E. and Kameda, H.: 2005, Equilibria for multiclass routing in multi-agent networks, in A. Nowak andK. Szajowski (eds), Advances in Dynamic Games: Annals of International Society of Dynamic Games Vol.
7, Birkhäuser, Boston, pp. 343–367. (An extended version of the paper that appeared in Proc. 40th IEEE Conference on Decision and Control (IEEE CDC’01), Orlando, U.S.A., pp. 604–609, Dec. 2001).
Altman, E., Kameda, H. and Hosokawa, Y.: 2002, Nash equilibria in load balancing in distributed computer systems,
International Game Theory Review 4(2), 91–100.
Arrow, K. J.: 1951, An extension of the basic theorems of classical welfare economics, in J. Neyman (ed.), Proc.
the Second Berkeley Symposium on Mathematical Statistics and Probability, University of California Press,
Berkeley, Calif., pp. 507–532.
Braess, D.: 1968, Über ein Paradoxon aus der Verkehrsplanung, Unternehmensforschung 12, 258–268.
Cohen, J. E. and Jeﬀries, C.: 1997, Congestion resulting from increased capacity in single-server queueing networks,
IEEE/ACM Trans. Networking 5(2), 305–310.
Cohen, J. E. and Kelly, F. P.: 1990, A paradox of congestion in a queuing network, J. Appl. Prob. 27, 730–734.
Debreu, G.: 1951, The coeﬃcient of resource utilization, Econometrica 19(3), 273–292.
Dubey, P.: 1986, Ineﬃciency of Nash equilibria, Mathematics of Operations Research 11(1), 1–8.
Frank, M.: 1981, The Braess paradox, Mathematical Programming 20, 283–302.
Haurie, A. and Marcotte, P.: 1985, On the relationship between Nash-Cournot and Wardrop equilibria, Networks
15, 295–308.
Kameda, H.: 2002, How harmful the paradox can be in the Braess/Cohen-Kelly-Jeﬀries networks, Proc. IEEE INFOCOM 2002, New York, pp. 437–445.
Kameda, H.: 2009, Coincident cost improvement vs. degradation by adding connections to noncooperative networks
and distributed systems, Networks and Spatial Economics 9(2), 269–287.
Kameda, H.: 2013, Models of paradoxical coincident cost degradation in noncooperative networks, Hardy Hanappi,ed., Game Theory Relauched, Intech, pp. 191–214. DOI: 10.5772/54377.
Kameda, H., Altman, E., Kozawa, T. and Hosokawa, Y.: 2000, Braess-like paradoxes in distributed computer systems,
IEEE Trans. Automatic Control 45(9), 1687–1691.
Kameda, H., Altman, E., Touti, C. and Legrand, A.: 2012, Nash equilibrium based fairness, Mathematical Methods ofOperations Research 76, 43–65. DOI:10.1007/s00186-012-0389-2.
Kameda, H. and Pourtallier, O.: 2002, Paradoxes in distributed decisions on optimal load balancing for networks ofhomogeneous computers, J. ACM 49(3), 407–433.
12

Korilis, Y. A., Lazar, A. A. and Orda, A.: 1995, Architecting noncooperative networks, IEEE J. Selected Areas inCommunications 13, 1241–1251.
Korilis, Y. A., Lazar, A. A. and Orda, A.: 1999, Avoiding the Braess paradox in noncooperative networks, J. Appl.
Prob. 36, 211–222.
Koutsoupias, E. and Papadimitriou, C.: 1999, Worst-case equilibria, Proceedings of the 16th Annual Symposium on
Theoretical Aspects of Computer Science, pp. 404–413.
Legrand, A. and Touati, C.: 2007, How to measure eﬃciency?, Proceedings of the 1st International Workshop on
Game theory for Communication networks (Game-Comm’07).
Murchland, J. D.: 1970, Braess’s paradox of traﬃc flow, Transpn. Res. 4, 391–394.
Orda, A., Rom, R. and Shimkin, N.: 1993, Competitive routing in multiuser communication networks, IEEE/ACM
Trans. Networking 1, 614–627.
Patriksson, M.: 1994, The Traﬃc Assignment Problem – Models and Methods, VSP, Utrecht.
Pigou, A. C.: 1920, The Economics of Welfare, Macmillan.
Roughgarden, T. and Tardos, É.: 2004a, Bounding the ineﬃciency of equilibria in nonatomic congestion games,
Games and Economic Behavior 47(2), 389–403.
Roughgarden, T. and Tardos, É.: 2004b, A stronger bound on Braess’s paradox, Proceedings of the 15th Annual
ACM-SIAM Symposium on Discrete Algorithm, pp. 333–334.
Smale, S.: 1973, Optimizing several functions, Proc. of the Int. Conf. on Manifolds and Related Topics in Topology(Manifolds Tokyo 1973), Univ. Tokyo Press, Tokyo, Japan, pp. 69–75.
Wardrop, J. G.: 1952, Some theoretic aspects of road traﬃc research, Proc. Inst. Civ. Eng., Part 2 1, 325–378.

13