∎

11institutetext: V. Bilò 22institutetext: Department of Mathematics and
Physics “Ennio De Giorgi”, University of Salento, 73100 Lecce, Italy. 22email:
<EMAIL_ADDRESS>33institutetext: C. Vinci44institutetext:
Department of Computer Engineering, Electrical Engineering and Applied
Mathematics, University of Salerno, 84084 Fisciano, Italy. 55institutetext:
Gran Sasso Science Institute, 67100 L’Aquila, Italy.
55email<EMAIL_ADDRESS>
# The Impact of Selfish Behavior
in Load Balancing Games ††thanks:  This work was partially supported by the
Italian MIUR PRIN 2017 Project ALGADIMAR “Algorithms, Games, and Digital
Markets”. ††thanks: The current affiliation of Cosimo Vinci is the University
of Salerno. A substantial part of this work was done when he was affiliated
with the Gran Sasso Science Institute (that is his previous
affiliation).††thanks: A preliminary version of this paper appeared in
Proceedings of the 25th Annual European Symposium on Algorithms (ESA 2017)
[12].

Vittorio Bilò  Cosimo Vinci

(Received: date / Accepted: date)

###### Abstract

To what extent does the structure of the players’ strategy space influence the
efficiency of decentralized solutions in congestion games? In this work, we
investigate whether better performance are possible when restricting to load
balancing games in which players can only choose among single resources. We
consider three different solutions concepts, namely, approximate pure Nash
equilibria, approximate one-round walks generated by selfish players aiming at
minimizing their personal cost and approximate one-round walks generated by
cooperative players aiming at minimizing the marginal increase in the sum of
the players’ personal costs. The last two concepts can be interpreted as
solutions of greedy online algorithms for the related resource selection
problem. We show that, under fairly general latency functions on the
resources, better bounds cannot be achieved if players are either weighted or
asymmetric. On the positive side, we prove that, under mild assumptions on the
latency functions, improvements on the performance of approximate pure Nash
equilibria are possible for load balancing games with weighted and symmetric
players in the case of identical resources. We also design lower bounds on the
performance of one-round walks in load balancing games with unweighted players
and identical resources.

###### Keywords:

Congestion Games Nash Equilibrium Price of Anarchy Load Balancing Greedy
Algorithms Online Algorithms.

###### MSC:

91A99 68W27 90C05

††journal: Pre-print

##  1 Introduction

Congestion games [43] are non-cooperative games in which there is a set of
selfish players competing for a set of resources, and each resource incurs a
certain latency, expressed by a congestion-dependent function, to the players
using it. Each player has a certain weight and an available set of strategies,
where each strategy is a non-empty subset of resources, and aims at choosing a
strategy minimizing her personal cost, which is defined as the sum of the
latencies experienced on all the selected resources. We speak of weighted
games/players when players have arbitrary non-negative weights and of
unweighted games/players when all players have unitary weight.

Stable outcomes in this setting are pure Nash equilibria [41]: strategy
profiles in which no player can lower her cost by unilaterally deviating to
another strategy. However, they are demanding solution concepts, as they might
not exist in weighted games [29] and, even when their existence is guaranteed,
as, for instance, in unweighted games [43] or in weighted games with affine
latency functions [29, 34], their computation might be an intractable problem
[1, 26]. For such a reason, more relaxed solution concepts, such as
$\epsilon$-approximate pure Nash equilibria or $\epsilon$-approximate one-
round walks, are also considered in the literature. An $\epsilon$-approximate
pure Nash equilibrium is the relaxation of the concept of pure Nash
equilibrium in which no player can lower her cost of a factor more than
$1+\epsilon$ by unilaterally deviating to another strategy. Efficient
algorithms computing approximate pure Nash equilibria in weighted congestion
games with polynomial latency functions are known, see [18, 19, 27, 33]. An
$\epsilon$-approximate one-round walk is defined as a myopic process in which
players arrive in an arbitrary order and, upon arrival, each of them has to
make an irrevocably strategic choice aiming at approximatively minimizing a
certain cost function. In this work, we shall consider two variants of this
process: in the first, players choose a strategy approximatively minimizing,
up to a factor of $1+\epsilon$, their personal cost (selfish players), while,
in the second, players choose the strategy approximatively minimizing, up to a
factor of $1+\epsilon$, the marginal increase in the social cost (cooperative
players) which is defined as the sum of the players’ personal costs (for the
case of $\epsilon=0$, we use the term exact one-round walk). Approximate one-
round walks can be interpreted as simple greedy online algorithms for the
equivalent resource selection problem associated with a given congestion game,
and, in most of the cases, these algorithms are optimal in the context of
online optimization of load balancing problems [17]. The worst-case efficiency
of these solution concepts with respect to the optimal social cost is termed
as the $\epsilon$-approximate price of anarchy (for the case of pure Nash
equilibria, the term price of anarchy [39] is adopted) and as the competitive
ratio of $\epsilon$-approximate one-round walks, respectively.

Interesting special cases of congestion games are obtained by restricting the
combinatorics of the players’ strategy space. In symmetric congestion games,
all players share the same set of strategies; in network congestion games the
players’ strategies are defined as paths in a given network; in matroid
congestion games [1, 2], the strategy set of every player is given by the set
of bases of a matroid defined over the set of available resources; in
$k$-uniform matroid congestion games [35], each player can select any subset
of cardinality $k$ from a prescribed player-specific set of resources; in
polytopal congestion games [36, 37], the strategies of every player correspond
to binary vectors of a player-specific polytope; finally, in load balancing
games, players can only choose single resources.

To what extent does the structure of the players’ strategy space influence the
efficiency of decentralized solutions in congestion games? In this work, we
investigate whether better performance are possible when restricting to load
balancing games. Previous work established that the price of anarchy does not
improve when restricting to unweighted load balancing games with polynomial
latency functions [20, 32], while better bounds are possible in unweighted
symmetric load balancing games with fairly general latency functions [28].
Under the assumption of identical resources, improvements are also possible in
the following cases: unweighted load balancing games with affine latencies
[20, 45], unweighted games with polynomial or general latencies [42, 46],
weighted symmetric load balancing games with affine latencies [40] or monomial
latencies [30]. Finally, [7] proves that the price of anarchy does not improve
when restricting to weighted symmetric load balancing games under polynomial
latency functions. A summary of these known results is shown in Figure 1.

| LB | SYM | IDE | AFF or MONO | POLY | GEN | Improve? | Reference
---|---|---|---|---|---|---|---|---
UNW | ✓ |  |  |  | ✓ |  | NO | [20, 32]
UNW | ✓ | ✓ |  |  |  | ✓ | YES | [28]
UNW | ✓ |  | ✓ | ✓ |  |  | YES | [20, 45]
UNW | ✓ |  | ✓ |  | ✓ |  | YES | [42, 46]
UNW | ✓ |  | ✓ |  |  | ✓ | YES | [42, 46]
WEI | ✓ | ✓ |  |  | ✓ |  | NO | [7]
WEI | ✓ | ✓ | ✓ | ✓ |  |  | YES | [30, 40]
Figure 1: Previously known results concerning the price of anarchy. The
following acronyms are used: UNW for unweighted games, WEI for weighted games,
LB for load balancing games, SYM for symmetric games, IDE for identical
resources, AFF for affine latency functions, MONO for monomial latency
functions, POLY for polynomial latency functions, GEN for general latency
functions (obeying mild assumptions). A check-mark on a column means that the
game enjoys the related property. Question Improve? asks whether better
performance are possible with respect to games not enjoying property LB.

For the competitive ratio of exact one-round walks generated by cooperative
players, no improvements are possible in unweighted load balancing games with
affine latency functions [20, 45], while improved performance can be obtained
under the additional assumption of identical resources [20] (we observe that,
in this case, solutions generated by both types of players coincide); however,
for weighted players, no improvements are possible even under the assumption
of identical resources [17, 20]. A summary of these known results is shown in
Figure 2. For one-round walks generated by selfish players, instead, no
specialized limitations are currently known (except for those inherited by the
case of cooperative players in games with identical resources).

| LB | IDE | AFF | Type of Players | Improve? | Reference
---|---|---|---|---|---|---
UNW | ✓ |  | ✓ | cooperative | NO | [20, 45]
UNW | ✓ | ✓ | ✓ | both | YES | [20]
WEI | ✓ | ✓ | ✓ | both | NO | [17, 20]
Figure 2: Previously known results concerning the competitive ratio of exact
one-round walks. Symbology is the same as that used in Figure 1.

###  1.1 Our Contribution

We obtain an almost precise picture of the cases in which improved performance
can be obtained in load balancing congestion games. This is done by either
solving open problems or extending previously known results to both
approximate solution concepts and more general latency functions encompassed
within the following definitions.

A class of latency functions $\mathcal{C}$ is closed under ordinate scaling
(resp. abscissa scaling) if, for any function $f\in\mathcal{C}$ and
$\alpha\geq 0$, the function $g$ such that $g(x)=\alpha f(x)$ (resp.
$g(x)=f(\alpha x)$) belongs to $\mathcal{C}$. A function $f$ is semi-convex if
$xf(x)$ is convex, it is unbounded if $\lim_{x\rightarrow\infty}f(x)=\infty$.
We observe that the class of polynomial latency functions obeys the following
properties:

  * $\bullet$

it is both abscissa and ordinate scaling,

  * $\bullet$

all of its functions are semi-convex,

  * $\bullet$

all of its non-constant functions are unbounded.

For the approximate price of anarchy, we prove the following results, which
are summarized in Figure 3. For unweighted players: if $\mathcal{C}$ is closed
under ordinate scaling, the approximate price of anarchy does not improve when
restricting to load balancing games (Theorem 4.1). For weighted players: if
$\mathcal{C}$ is closed under abscissa and ordinate scaling, the approximate
price of anarchy does not improve when restricting to load balancing games
(Theorem 3.1). Furthermore, if $\mathcal{C}$ contains unbounded functions only
(except for the eventual constant latency functions), the approximate price of
anarchy does not improve even for symmetric load balancing games. However,
under the additional hypothesis of identical resources, better performance are
still possible. Let $f$ be an increasing, continuous and semi-convex function.
We prove that the approximate price of anarchy of weighted symmetric load
balancing games with identical resources having latency function $f$ is at
most equal to

$\sup_{x>0}\max_{\lambda\in(0,1)}\frac{\lambda
xf(x)+(1-\lambda)[x]_{\epsilon,f}f([x]_{\epsilon,f})}{(\lambda
x+(1-\lambda)[x]_{\epsilon,f})f(\lambda x+(1-\lambda)[x]_{\epsilon,f})},$

where

$[x]_{\epsilon,f}:=\textrm{inf}\\{t\geq 0:f(x)\leq(1+\epsilon)f(x/2+t)\\},$

and we show that such upper bound is tight under some mild assumptions.

| LB | SYM | IDE | CUAS | CUOS | UNB | SEMI-CONV | Improve?
---|---|---|---|---|---|---|---|---
UNW | ✓ |  |  |  | ✓ |  |  | NO
WEI | ✓ |  |  | ✓ | ✓ |  |  | NO
WEI | ✓ | ✓ |  | ✓ | ✓ | ✓ |  | NO
WEI | ✓ | ✓ | ✓ |  |  |  | ✓ | YES
Figure 3: Our results concerning the approximate price of anarchy. The
following additional acronyms are used with respect to those adopted in Figure
1: CUAS for games whose latency functions are closed under abscissa scaling,
CUOS for games whose latency functions are closed under ordinate scaling, UNB
for games whose all non-constant latency functions are unbounded, SEMI-CONV
for games whose latency functions are semi-convex.

For the competitive ratio of approximate one-round walks, we prove the
following results which are summarized in Figure 4. For unweighted players: if
$\mathcal{C}$ is closed under ordinate scaling, the competitive ratio of
approximate one-round walks generated by selfish players does not improve when
restricting to load balancing games. The same negative result holds with
respect to cooperative players under the additional hypothesis that all
functions in $\mathcal{C}$ are semi-convex (Theorem 4.2). For weighted
players: if $\mathcal{C}$ is closed under abscissa and ordinate scaling, the
competitive ratio of approximate one-round walks generated by selfish players
does not improve when restricting to load balancing games. Also in this case,
to extend the result to cooperative players, we need that all functions in
$\mathcal{C}$ are semi-convex (Theorem 3.2). Finally, for the case of
identical resources, we design lower bounds on the performance of exact one-
round walks in load balancing games with unweighted players.

| LB | CUAS | CUOS | SEMI-CONV | Type of Players | Improve?
---|---|---|---|---|---|---
UNW | ✓ |  | ✓ |  | selfish | NO
UNW | ✓ |  | ✓ | ✓ | cooperative | NO
WEI | ✓ | ✓ | ✓ |  | selfish | NO
WEI | ✓ | ✓ | ✓ | ✓ | cooperative | NO
Figure 4: Our results concerning the competitive ratio of approximate one-
round walks. Symbology is the same as that used in Figure 3.

From a technical point of view, our results are obtained by designing some
general load balancing instances parametrized by at most four numbers and two
latency functions belonging to $\mathcal{C}$. We show that there exists a
choice of these parameters such that the performance of the considered load
balancing instances, which thus get measured by some parametrized formulas,
match that of general congestion games with latency functions in
$\mathcal{C}$. We also show how to quantitatively evaluate these formulas when
$\mathcal{C}$ is the set of polynomial of maximum degree $d$.

Independently from our existential results, the load balancing instances we
introduce may be useful to get good lower bounds on the performance of load
balancing games with latency functions in $\mathcal{C}$, even if we are not
able to quantify the exact value of the metric adopted to measure the
performance (see Remarks 3 and 5).

###  1.2 Significance

With respect to the (approximate) price of anarchy, it can be appreciated how
row $1$ in Figure 3 generalizes to approximate equilibria and to more general
latency functions row $1$ in Figure 1. Similarly, rows $2$ and $3$ in Figure 3
generalize to approximate equilibria and to more general latency functions row
$4$ in Figure 1 (these issues were posed as open problems in [7]). Finally,
row $4$ in Figure 3 generalizes to approximate equilibria and to more general
latency functions row $5$ in Figure 1. Our negative results, together with the
positive ones achieved by [28] (see row 2 of Figure 1), imply that, whenever
resources are not identical, better bounds on the approximate price of anarchy
are possible only when dealing with unweighted symmetric load balancing games.

We would like to stress the following observation here. Row 2 in Figure 3 may
look redundant, as row 1 tells us that no improvement is possible in
unweighted games if the latency functions are ordinate scaling, while,
according to row 2, to have the same negative result in weighted games, we
additionally need the abscissa scaling property. But, as unweighted games are
also weighted ones, we have a representative subclass of weighted games for
which no improvement is possible even under the mere assumption of the
ordinate scaling property! This is true, but row 2 tells indeed something more
than row 1. Everything gets clearer when thinking to what we mean when we say
that no improvement is possible in weighted games: we mean that, for any game
with $n$ many players having weights defined by a vector
$(w_{1},\ldots,w_{n})$, there exists a load balancing game with the same
number of players and the same vector of weights with a non-smaller price of
anarchy. So, the fact that this is true when considering a unitary vector of
weights does not imply that this remains true for any vector, and in fact, to
achieve such a stronger result, we have to assume the additionally hypothesis
of abscissa scaling on the latency functions. Determining whether the same
impossibility result can be obtained in weighted games by relying on the
ordinate scaling property only is an interesting open problem. If this were
not possible, it would follow that, in certain situations, restricting to
singleton strategies is more effective in weighted games than it can be in
unweighted ones.

For the competitive ratio of (approximate) one-round walks, we have that row 1
of Figure 4 provides the first known results for the case of selfish players.
This has a number of applications. For instance, [9] showed that the upper
bound on the competitive ratio of exact one-round walks involving selfish
players provided in [24] for the case of affine latencies is tight. However,
the lower bounding instance provided by [9] is a general congestion game, and
the authors left as open problem of determining whether a load balancing games
with the same performance could be achieved. Our findings show that this is
possible and also tells us how to directly used to construct a load balancing
instance whose performance matches that of general congestion games, thus
solving this open question. Row 2 of Figure 4 generalizes row 1 of Figure 2,
which holds only with respect to exact one-round walks generated by
cooperative players in games with affine latency functions. Row 3 of Figure 4
implies that the upper bounds provided in [24] and [38] for the competitive
ratio of exact one-round walks in general congestion games with affine and
polynomial latency functions, respectively, are tight even for load balancing
games. We stress out that, even for general congestion games, no lower bound
for the competitive ratio of exact one-round walks involving selfish players
was known prior to this work, except for the case of unweighted games with
affine latencies [9].

Finally, row 4 of Figure 4 generalizes results in [5, 17, 20] which hold only
with respect to exact one-round walks for games with polynomial latency
functions. Finally, the lower bounds that we obtain on the performance of
exact one-round walks in load balancing games with unweighted players and
identical resources improves and generalizes the previously known lower bound
given in [20] which holds only for affine latency functions.

###  1.3 Related Work

The price of anarchy in congestion games was first considered in [4] and [22]
and shown to be equal to $5/2$ in unweighted games with affine latency
functions. In [22], it is also proved that no improved bounds are possible in
both symmetric unweighted games and unweighted network games; these results
were improved by [25] which shows that the price of anarchy stays the same
even in symmetric unweighted network games. Furthermore, in [4], it is shown
that the price of anarchy of weighted congestion games with affine latency
functions is $(3+\sqrt{5})/2$.

In [20], it is shown that the previous bounds are tight also for load
balancing games. For the special case of load balancing games on identical
resources, the works of [45] and [20] show that the price of anarchy is
$2.012067$ for unweighted games and at least $5/2$ for weighted ones. The
works of [42, 46] generalize the above results on affine unweighted games with
identical resources, and provide tight bounds on the price of anarchy even for
polynomial and more general latencies. In [40], it is proved that, for
symmetric load balancing games, the price of anarchy drops to $4/3$ if the
games are unweighted, and to $9/8$ if the games are weighted with identical
resources. This last result has been generalised by [30], who provide tight
bounds on the price of anarchy of symmetric weighted load balancing games with
identical resources and monomial latency functions. For symmetric unweighted
$k$-uniform matroid congestion games with affine latency functions, [35]
proves that the price of anarchy is at most $28/13$ and at least $1.343$ for a
sufficiently large value of $k$ (for $k=5$, it is roughly $1.3428$). Tight
bounds on the price of anarchy of either weighted and unweighted congestion
games with polynomial latency functions have been given by [3]. Under fairly
general latency functions, [28] shows that the price of anarchy of unweighted
symmetric load balancing games coincides with that of non-atomic congestion
games, while [7] proves that assuming symmetric strategies does not lead to
improved bounds in unweighted games and gives exact bounds for the case of
weighted players. It also shows that, for the case of weighted players, no
improvements are possible even in symmetric load balancing games with monomial
and polynomial latency functions. Upper and lower bounds on the pure and mixed
price of anarchy for several classes of load balancing games with polynomial
latency functions are provided in [30, 32, 31]. Finally, [23] (resp. [8])
provides tight bounds (resp. almost tight upper bounds) on the approximate
price of anarchy of unweighted (resp. weighted) congestion games under affine
latency functions. [33] obtain tight bounds on the approximate price of
anarchy of congestion games with polynomial latency functions, holding even
for load balancing games; prior to [33], analogue results have been obtained
in the preliminary version of our work.

The competitive ratio of exact one-round walks generated by cooperative
players in load balancing games with polynomial latency functions has been
first considered in [5], where, for the special case of affine functions, an
upper bound of $3+2\sqrt{2}$ is provided for weighted players. For unweighted
players, this result has been improved to $17/3$ in [45], where it is also
shown that, for identical resources, the upper bound drops to $2+\sqrt{5}$ in
spite of a lower bound of $3.0833$. Finally, [20] show matching lower bounds
of $3+2\sqrt{2}$ and $17/3$ for, respectively, weighted and unweighted
players. For weighted games with polynomial latency functions, tight bounds
have been given in [17]; the lower bounds, in particular, hold even for
identical resources, thus improving previous results from [5]. In [20] it is
also shown that, for unweighted players and identical resources, the
competitive ratio lies between $4$ and $\frac{2}{3}\sqrt{21}+1$ if latency
functions are affine.

For the case of selfish players and still under affine latency functions, [9,
24] show that the competitive ratio is $2+\sqrt{5}$ for unweighted congestion
games, while, for weighted players, [24] gives an upper bound of
$4+2\sqrt{3}$. For the more general case of polynomial latency functions, [38]
determines explicit and good upper bounds on the competitive ratio in
unweighted and weighted congestion games; prior to [38], analogue results for
weighted games with polynomial latency functions have been obtained in the
preliminary version of our work [12].

In [13], it is shown that, if latency functions are polynomials of degree $d$
and players are selfish, the $(d+1)$-th ordered Bell number is a lower-bound
on the competitive ratio, even for unweighted games with identical resources.
The concept of one-round walks starting from the empty state in non-atomic
congestion games is analysed in [47].

##  2 Definitions and Notation

For two integers $0\leq k_{1}\leq k_{2}$, let
$[k_{1}]_{k_{2}}:=\\{k_{1},k_{1}+1,\ldots,k_{2}-1,k_{2}\\}$ and
$[k_{1}]:=[k_{1}]_{1}$. For a real function
$F:{\mathbb{N}}\rightarrow{\mathbb{R}}$, $[<]_{s}\left(F(s)\right)$ (resp.
$[\leq]_{s}\left(F(s)\right)$) denotes an arbitrary function
$G:{\mathbb{N}}\rightarrow{\mathbb{R}}$ such that
$\lim_{s\rightarrow\infty}\frac{|G(s)|}{|F(s)|}=0$ (resp.
$\limsup_{s\rightarrow\infty}\frac{|G(s)|}{|F(s)|}\leq c$ for some
$c>0$).111We have not adopted the classical notation used in asymptotic
analysis for two main reasons: (i) to explicate that we evaluate the
asymptotic behaviour with respect to a certain variable $s$ only, while other
variables/parameters are keep fixed; (ii) to avoid ambiguity with the symbol
“o”, that will be often used to denote other quantities.

#### Congestion Games.

A congestion game is a tuple

${\sf CG}=\left(N,E,(\ell_{e})_{e\in E},(w_{i})_{i\in
N},({\sf\Sigma}_{i})_{i\in N}\right),$

where $N$ is a set of $n\geq 2$ players, $E$ is a set of resources,
$\ell_{e}:{\mathbb{R}}_{>0}\rightarrow{\mathbb{R}}_{>0}$ is the (non-
decreasing) latency function of resource $e\in R$, and, for each $i\in N$,
$w_{i}\geq 0$ is the weight of player $i$ and ${\sf\Sigma}_{i}\subseteq
2^{R}\setminus\emptyset$ is her set of strategies. Conventionally, we set
$\ell_{e}(0)=\lim_{x\rightarrow 0^{+}}\ell_{e}(x)$ for any latency function
$\ell_{e}$.222All the results obtained in this paper can be easily generalized
to the case in which some latency function $\ell_{e}$ verifies $\ell_{e}(x)=0$
for some $x>0$, but this requires further (tedious) case analysis to cope with
undefined ratios of type $c/0$. We speak of weighted games/players when
players have arbitrary weights and of unweighted games/players when $w_{i}=1$
for each $i\in N$. A congestion game is symmetric if
${\sf\Sigma}_{i}={\sf\Sigma}$ for each $i\in N$, i.e., if all players share
the same strategy space. A load balancing game is a congestion game in which
for each $i\in N$ and $S\in{\sf\Sigma}_{i}$, $|S|=1$, that is, all players’
strategies are singleton sets. Given a class $\mathcal{C}$ of latency
functions, let ${\sf W}(\mathcal{C})$ be the class of weighted congestion
games, ${\sf U}(\mathcal{C})$ be the class of unweighted congestion games,
${\sf ULB}(\mathcal{C})$ be the class of unweighted load balancing games,
${\sf WLB}(\mathcal{C})$ be the class of weighted load balancing games, and
${\sf WSLB}(\mathcal{C})$ be the class of weighted symmetric load balancing
games, all having latency functions in class $\mathcal{C}$.

#### Latency Functions.

A congestion game has polynomial latencies of maximum degree $d$ when, for
each $e\in E$, $\ell_{e}(x)=\sum_{h\in[d]_{0}}\alpha_{e,h}x^{h}$, with
$\alpha_{e,h}\geq 0$ for each $h\in[d]_{0}$. When $d=0$ we speak of constant
latencies and when $d=1$, we speak of affine latencies. If
$\ell_{e}(x)=\alpha_{e,d}x^{d}$, we speak of monomial latencies of degree $d$,
and if $d=1$, we speak of linear latencies. Let $\mathcal{P}(d)$ denote the
class of polynomial latencies of maximum degree $d$. A latency function $f$ is
semi-convex if $xf(x)$ is convex, and it is unbounded if
$\lim_{x\rightarrow\infty}f(x)=\infty$. A congestion game has identical
resources when all resources have the same latency. Given a class
$\mathcal{G}$ of congestion games, let $\mathcal{C}(\mathcal{G})$ denote the
class of latency functions of congestion games belonging to $\mathcal{G}$. A
class $\mathcal{C}$ of latency functions is closed under ordinate scaling
(resp. abscissa scaling) if, for any function $f\in\mathcal{C}$ and
$\alpha>0$, the function $g$ such that $g(x)=\alpha f(x)$ (resp.
$g(x)=f(\alpha x)$) belongs to $\mathcal{C}$.

#### Strategy Profiles and Cost Functions.

A strategy profile is an $n$-tuple of strategies
${\bm{\sigma}}=(\sigma_{1},\ldots,\sigma_{n})$, that is, a state of the game
in which each player $i\in N$ is adopting strategy
$\sigma_{i}\in{\sf\Sigma}_{i}$, so that ${\sf\Sigma}:=\times_{i\in
N}{\sf\Sigma}_{i}$ denotes the set of strategy profiles which can be realized
in ${\sf CG}$. For a strategy profile $\bm{\sigma}$, the congestion of
resource $e\in E$ in $\bm{\sigma}$, denoted as
$k_{e}({\bm{\sigma}}):=\sum_{i\in N:e\in\sigma_{i}}w_{i}$, is the total weight
of the players using resource $e$ in $\bm{\sigma}$ (observe that, in
unweighted games, $k_{e}({\bm{\sigma}})$ coincides with the number of users of
$e$ in $\bm{\sigma}$). The personal cost of player $i$ in $\bm{\sigma}$ is
defined as
$cost_{i}({\bm{\sigma}})=\sum_{e\in\sigma_{i}}\ell_{e}(k_{e}({\bm{\sigma}}))$
and each player aims at minimizing it. For the sake of conciseness, when the
strategy profile $\bm{\sigma}$ is clear from the context, we write $k_{e}$ in
place of $k_{e}({\bm{\sigma}})$. Fix a strategy profile $\bm{\sigma}$ and a
player $i\in N$. We denote with ${\bm{\sigma}}_{-i}$ the restriction of
$\bm{\sigma}$ to all players other than $i$; moreover, for a strategy
$S\in{\sf\Sigma}_{i}$, we denote with $({\bm{\sigma}}_{-i},S)$ the strategy
profile obtained from $\bm{\sigma}$ when player $i$ changes her strategy from
$\sigma_{i}$ to $S$, while the strategies of all the other players are kept
fixed. The quality of a strategy profile in congestion games is measured by
using the social function ${\sf SUM}({\bm{\sigma}})=\sum_{i\in
N}w_{i}cost_{i}({\bm{\sigma}})=\sum_{e\in
E}k_{e}({\bm{\sigma}})\ell_{e}(k_{e}({\bm{\sigma}}))$, that is, the sum of the
players’ personal costs. A social optimum is a strategy profile
${\bm{\sigma}}^{*}$ minimizing $\sf SUM$. For the sake of conciseness, once a
particular social optimum has been fixed, we write $o_{e}$ to denote the value
$k_{e}({\bm{\sigma}}^{*})$.

#### Solution Concepts.

For any $\epsilon\geq 0$, an $\epsilon$-approximate pure Nash equilibrium is a
strategy profile $\bm{\sigma}$ such that, for any player $i\in N$ and strategy
$S\in{\sf\Sigma}_{i}$,
$cost_{i}({\bm{\sigma}})\leq(1+\epsilon)cost_{i}({\bm{\sigma}}_{-i},S)$. For
$\epsilon=0$, we speak of an (exact) pure Nash equilibrium. We denote by ${\sf
NE}_{\epsilon}({\sf CG})$ the set of $\epsilon$-approximate pure Nash
equilibria of a congestion game $\sf CG$.

For any $\epsilon\geq 0$, an $\epsilon$-approximate one-round walk is an
online process in which players appear sequentially according to an arbitrary
order and, upon arrival, each player irrevocably chooses a strategy
approximatively minimizing a certain cost function. Formally, an
$\epsilon$-approximate one-round walk involving selfish (or cooperative)
players is an $n+1$-tuple
$\bm{\tau}=(\bm{\sigma}^{0},\bm{\sigma}^{1},\bm{\sigma}^{2},\ldots,\bm{\sigma}^{n})$
defined as follows:

  * $\bullet$

assuming without loss of generality that players enter sequentially according
to their indices,
${\bm{\sigma}}^{i}=(\sigma_{1}^{i},\sigma_{2}^{i},\ldots,\sigma_{i}^{i},\underbrace{\emptyset,\emptyset,\ldots,\emptyset}_{n-i})$
is the strategy profile obtained when the first $i$ players have performed
their strategic choice, while the remaining ones have not entered the game yet
(so, we assume that each of them is playing the empty strategy);

  * $\bullet$

if players are selfish, the $i$-th player aims at minimizing her personal
cost, so that
$cost_{i}({\bm{\sigma}}^{i})\leq(1+\epsilon)\min_{S\in{\sf\Sigma}_{i}}cost_{i}({\bm{\sigma}}^{i-1},S)$;
otherwise, if players are cooperative, the $i$-th player aims at minimizing
the marginal increase in the social function $\sf SUM$, so that ${\sf
SUM}({\bm{\sigma}}^{i})-{\sf
SUM}({\bm{\sigma}}^{i-1})\leq(1+\epsilon)\min_{S\in{\sf\Sigma}_{i}}({\sf
SUM}({\bm{\sigma}}^{i-1},S)-{\sf SUM}({\bm{\sigma}}^{i-1}))$333An alternative
definition for the concept of $\epsilon$-approximate one-round walk involving
cooperative players can be obtained by assuming that the $i$-th player aims at
minimizing the value of the social function, i.e., ${\sf
SUM}({\bm{\sigma}}^{i})\leq(1+\epsilon)\min_{S\in{\sf\Sigma}_{i}}{\sf
SUM}({\bm{\sigma}}^{i-1},S)$. For $\epsilon=0$ the two definitions are
equivalent; for $\epsilon>0$, the proof arguments that we will consider in
this paper can be easily adapted/modified to get similar results holding under
this alternative definition..

For $\epsilon=0$, we speak of a(n) (exact) one-round walk. We denote by ${\sf
ORW}^{s}_{\epsilon}({\sf CG})$ (resp. ${\sf ORW}^{c}_{\epsilon}({\sf CG})$)
the set of strategy profiles ${\bm{\sigma}}=\bm{\sigma}^{n}$ which can be
constructed by an $\epsilon$-approximate one-round walk involving selfish
(resp. cooperative) players in a congestion game $\sf CG$.

#### Quality Metrics.

The $\epsilon$-approximate price of anarchy of a congestion game $\sf CG$ is
defined as ${\sf PoA}_{\epsilon}({\sf CG})=\max_{{\bm{\sigma}}\in{\sf
NE}_{\epsilon}({\sf CG})}\frac{{\sf SUM}({\bm{\sigma}})}{{\sf
SUM}({\bm{\sigma}}^{*})}$, where ${\bm{\sigma}}^{*}$ is a social optimum for
${\sf CG}$. Similarly, the competitive ratio of $\epsilon$-approximate one-
round walks generated by selfish (resp. cooperative) players, is defined as
${\sf CR}^{s}_{\epsilon}({\sf CG})=\max_{{\bm{\sigma}}\in{\sf
ORW}^{s}_{\epsilon}({\sf CG})}\frac{{\sf SUM}({\bm{\sigma}})}{{\sf
SUM}({\bm{\sigma}}^{*})}$ (resp. ${\sf CR}^{c}_{\epsilon}({\sf
CG})=\max_{{\bm{\sigma}}\in{\sf ORW}^{c}_{\epsilon}({\sf CG})}\frac{{\sf
SUM}({\bm{\sigma}})}{{\sf SUM}({\bm{\sigma}}^{*})}$). Given a class of
congestion games $\mathcal{G}$, the $\epsilon$-approximate price of anarchy of
$\mathcal{G}$ is defined as ${\sf
PoA}_{\epsilon}({\mathcal{G}})=\textrm{sup}_{{\sf CG}\in{\mathcal{G}}}{\sf
PoA}_{\epsilon}({\sf CG})$. For the case of $\epsilon=0$, we refer to this
metric simply as to the price of anarchy. The competitive ratio of
$\epsilon$-approximate one-round walks of $\mathcal{G}$ generated by both
selfish and cooperative players is defined accordingly. Throughout the paper,
we shall assume that, in any considered class of latency functions, there
always exists a non-constant latency function.444We observe that, if all the
latency functions are constant, the value of all quality metrics is at most
$1+\epsilon$, and such upper bound is tight.

##  3 Weighted Load Balancing Games

In this section, we show that, under mild assumptions on the latency
functions, the $\epsilon$-approximate price of anarchy and the competitive
ratio of $\epsilon$-approximate selfish/cooperative one-round walks of
weighted congestion games cannot improve even when restricting to load
balancing games.

###  3.1 Preliminary Definitions and Technical Lemmas

We first give some definitions and two technical lemmas, whose proofs are
based on the primal-dual method [8], and are deferred to Section B of the
appendix (since they are quite technical and do not constitute the primary
focus of this work). Lemma 1 gives quasi-explicit formulas to compute upper
bounds for the considered efficiency metrics, and such bounds are obtained by
fixing an arbitrary congestion game, and by exploiting the dual linear program
of a parametric primal linear program whose objective function returns the
value of the considered efficiency metric. Then, Lemma 2 provides some
parameters that will be used in the main theorems of this section to design
ad-hoc load balancing instances whose performance match the upper bounds of
Lemma 1.

We point out that, the upper bounds provided in Lemma 1 can be equivalently
derived by resorting to the smoothness framework [44] (further details are
given in Section A of the appendix). Prior to this work, similar results as in
Lemma 2 have been given in [44, 7, 47], with the aim of designing parametric
load balancing instances whose performance match the known upper bounds.

Given $x\geq 1$, $k>0$, $o>0$, and a latency function $f$, let

$\beta_{\sf W}({\sf
EM},k,o,f):=\begin{cases}-kf(k)+(1+\epsilon)of(k+o)&\text{if }{\sf EM}={\sf
PoA}_{\epsilon},\\\ -\int_{0}^{k}f(t)\text{dt}+(1+\epsilon)of(k+o)&\text{if
}{\sf EM}={\sf CR}_{\epsilon}^{s},\\\
-kf(k)+(1+\epsilon)((k+o)f(k+o)-kf(k))&\text{if }{\sf EM}={\sf
CR}_{\epsilon}^{c}.\end{cases}$ (1)

Given ${\sf EM}\in\\{{\sf PoA}_{\epsilon},{\sf CR}^{s}_{\epsilon},{\sf
CR}^{c}_{\epsilon}\\}$, let

$\gamma_{\sf W}({\sf EM},x,k,o,f):=\frac{kf(k)+x\cdot\beta_{\sf W}({\sf
EM},k,o,f)}{of(o)};$ (2)

furthermore, given a class of weighted congestion games $\mathcal{G}$, let

$\gamma_{\sf W}({\sf EM},\mathcal{G}):=\inf_{x\geq
1}\sup_{f\in\mathcal{C}(\mathcal{G}),k>0,o>0}\gamma_{\sf W}({\sf
EM},x,k,o,f).$ (3)

###### Lemma 1

Let $\mathcal{G}$ be a class of weighted congestion games. For any ${\sf
EM}\in\\{{\sf PoA}_{\epsilon},{\sf CR}^{s}_{\epsilon}\\}$ we have that ${\sf
EM}(\mathcal{G})\leq\gamma_{\sf W}({\sf EM},\mathcal{G})$. This fact holds for
${\sf EM}={\sf CR}^{c}_{\epsilon}$ if the latency functions of
$\mathcal{C}(\mathcal{G})$ are semi-convex.

The proof of Lemma 1 is deferred to Section B of the appendix, and we give a
brief overview of the case ${\sf EM}={\sf PoA}_{\epsilon}$.

######  Proof (Sketch of the proof of Lemma 1)

The maximum value of the following linear program in the variables
$\alpha_{e}$’s is an upper bound on ${\sf PoA}_{\epsilon}({\sf CG})$ (recall
that $w_{i}$ is the weight of player $i$, $k_{e}$ and $o_{e}$ are the
equilibrium and optimal congestions of resource $e$, respectively):

$\displaystyle{\sf LP1:}\quad\max\quad$ $\displaystyle\overbrace{\sum_{e\in
E}\alpha_{e}k_{e}\ell_{e}(k_{e})}^{{\sf SUM}(\bm{\sigma})}$ $\displaystyle
s.t.\quad$
$\displaystyle\sum_{e\in\sigma_{i}}\alpha_{e}\ell_{e}(k_{e})\leq(1+\epsilon)\sum_{e\in\sigma_{i}^{*}}\alpha_{e}\ell_{e}(k_{e}+w_{i}),\quad\forall
i\in N$ (4) $\displaystyle\overbrace{\sum_{e\in
E}\alpha_{e}o_{e}\ell_{e}(o_{e})}^{{\sf SUM}(\bm{\sigma}^{*})}=1$ (5)
$\displaystyle\alpha_{e}\geq 0,\quad\forall e\in E,$

Indeed, by setting $\alpha_{e}=1$ for any $e\in E$, we have that: (i) the
objective function is the social cost at the equilibrium; (ii) the constraints
in (4) impose some relaxed $\epsilon$-approximate pure Nash equilibrium
conditions (ensuring that each agent, at the equilibrium, does not get any
benefit when deviating in favour of strategy $\sigma^{*}_{i}$); (iii) (5) is
the normalized optimal social cost (normalization is possible since there is
some $o_{e}>0$, that implies $o_{e}\ell_{e}(o_{e})>0$). We introduce further
relaxations on LP1 (by replacing all the constraints in (4) with their
weighted sum) and we get the following linear program:

$\displaystyle{\sf LP2:}\quad\max\quad$ $\displaystyle\sum_{e\in
E}\alpha_{e}k_{e}\ell_{e}(k_{e})$ $\displaystyle s.t.\quad$
$\displaystyle\sum_{e\in E}\alpha_{e}\beta_{\sf W}({\sf
PoA}_{\epsilon},k_{e},o_{e},\ell_{e})\geq 0$ $\displaystyle\sum_{e\in
E}\alpha_{e}o_{e}\ell_{e}(o_{e})=1$ $\displaystyle\alpha_{e}\geq
0,\quad\forall e\in E,$

where $\beta_{\sf W}({\sf PoA}_{\epsilon},k_{e},o_{e},\ell_{e})$ is defined in
(1). By taking the dual of LP2, we get the following linear program:

$\displaystyle{\sf DLP:}\quad\min\quad$ $\displaystyle\gamma$ $\displaystyle
s.t.\quad$ $\displaystyle\gamma\cdot o_{e}\ell_{e}(o_{e})\geq
k_{e}\ell_{e}(k_{e})+x\cdot\beta_{\sf W}({\sf
PoA}_{\epsilon},k_{e},o_{e},\ell_{e}),\quad\forall e\in E$ $\displaystyle
x\geq 0,\gamma\in{\mathbb{R}}$

Finally, we show that there exists a feasible solution $(x,\gamma)$ of the
dual that guarantees a value of at most $\gamma_{\sf W}({\sf
PoA}_{\epsilon},\mathcal{G})$; by weak duality, this is an upper bound on the
optimal value of LP, and then an upper bound on the $\epsilon$-approximate
price of anarchy.∎

###### Lemma 2

Let $\mathcal{G}$ be a class of weighted congestion games. For each
$M<\gamma_{\sf W}({\sf EM},\mathcal{G})$, with ${\sf EM}\in\\{{\sf
PoA}_{\epsilon},{\sf CR}^{s}_{\epsilon}\\}$, one of the following cases holds:

  * $\bullet$

Case 1: there exists a non-constant latency function
$f\in\mathcal{C}(\mathcal{G})$ and two real numbers $k,o>0$ such that
$M<\frac{kf(k)}{of(o)}$ and $\beta_{\sf W}({\sf EM},k,o,f)\geq 0$.

  * $\bullet$

Case 2: there exist two latency functions
$f_{1},f_{2}\in\mathcal{C}(\mathcal{G})$ and four real numbers
$k_{1},k_{2},o_{1},o_{2}>0$ such that
$M<\frac{\alpha_{1}k_{1}f_{1}(k_{1})+\alpha_{2}k_{2}f_{2}(k_{2})}{\alpha_{1}o_{1}f_{1}(o_{1})+\alpha_{2}o_{2}f_{2}(o_{2})}$,
where $\alpha_{1}:=\beta_{\sf W}({\sf EM},k_{2},o_{2},f_{2})>0$ and
$\alpha_{2}:=-\beta_{\sf W}({\sf EM},k_{1},o_{1},f_{1})>0$; furthermore, if
${\sf EM}={\sf PoA}_{\epsilon}$, $f_{1}$ and $f_{2}$ can be chosen as non-
constant latency functions.

This fact holds for ${\sf EM}={\sf CR}_{\epsilon}^{c}$ if the latency
functions of $\mathcal{C}(\mathcal{G})$ are semi-convex.

The proof of Lemma 2 is quite technical and does not represent a fundamental
result of such work, thus it is deferred to Section B of the appendix. Anyway,
we give a sketch of the proof clarifying the main steps.

######  Proof (Sketch of the proof of Lemma 2)

The claim of Lemma 2 is obtained by reversing the proof arguments of Lemma 1
as follows: (i) we start from the upper bound $\gamma_{\sf W}({\sf
EM},\mathcal{G})$ obtained in Lemma 1; (ii) we derive a linear program
$\overline{\sf DLP}$ similar as the dual program used in Lemma 1, but with two
constraints only (except those that impose the non-negativity of the
variables), and whose optimal value is higher than $M$; (iii) the dual of
$\overline{\sf DLP}$ is similar to the linear program LP2 used in Lemma 1, but
with two constraints and two variables, and has the same optimal value (higher
than $M$) as in $\overline{\sf DLP}$ (by strong duality); in particular, the
new linear program is explicitly defined as follows:

$\displaystyle\overline{\sf LP}:\quad\max\quad$
$\displaystyle\alpha_{1}k_{1}f_{1}(k_{1})+\alpha_{2}k_{2}f_{2}(k_{2})$
$\displaystyle s.t.\quad$ $\displaystyle\alpha_{1}\beta_{\sf W}({\sf
EM},k_{1},k_{1},f_{1})+\alpha_{2}\beta_{\sf W}({\sf EM},k_{2},o_{2},f_{2})\geq
0$ $\displaystyle\alpha_{1}o_{1}f_{1}(o_{1})+\alpha_{2}o_{2}f_{2}(o_{2})=1$
$\displaystyle\alpha_{1},\alpha_{2}\geq 0;$

(iv) finally, the claim of Lemma 2 is obtained by characterizing the optimal
solution of $\overline{\sf LP}$. ∎

###### Remark 1

By exploiting Lemma 2, given an arbitrary choice of the input parameters
$k,o,f$ (resp. $k_{1},k_{2},o_{1},o_{2},f_{1},f_{2}$) such that $\beta_{\sf
W}({\sf EM},k,o,f)\geq 0$ (resp. $\beta_{\sf W}({\sf EM},k_{2},o_{2},f_{2})>0$
and $-\beta_{\sf W}({\sf EM},k_{1},o_{1},f_{1})>0$), we have that
$\frac{kf(k)}{of(o)}$ (resp.
$\frac{\alpha_{1}k_{1}f_{1}(k_{1})+\alpha_{2}k_{2}f_{2}(k_{2})}{\alpha_{1}o_{1}f_{1}(o_{1})+\alpha_{2}o_{2}f_{2}(o_{2})}$)
is a lower bound on $\gamma_{\sf W}({\sf EM},\mathcal{G})$; furthermore, by
definition of $\gamma_{\sf W}({\sf EM},\mathcal{G})$, we have that
$\sup_{f\in\mathcal{C}(\mathcal{G}),k,o>0}\gamma_{\sf W}({\sf EM},x,k,o,f)$ is
an upper bound on $\gamma_{\sf W}({\sf EM},\mathcal{G})$ for any $x\geq 1$.
Thus, if such upper bound (for a suitable choice of $x$) is equal to the
former lower bound (for a suitable choice of the input parameters), we
necessarily have that they are both equal to $\gamma_{\sf W}({\sf
EM},\mathcal{G})$.

###### Remark 2

In Lemma 2, if $\mathcal{C}(\mathcal{G})$ is closed under abscissa and
ordinate scaling, we can assume without loss of generality that $o_{j}=1$ for
each $j\in[2]$ (remove index $j$ if the first case of Lemma 2 is verified).
Indeed, if it is not the case, let $\hat{f}_{j}\in\mathcal{C}(\mathcal{G})$ be
the latency function such that $\hat{f}_{j}(k):=o_{j}f_{j}(o_{j}k)$ for any
$k\geq 0$. If we consider tuple $(k_{j}/o_{j},1,\hat{f}_{j})$ in place of
tuple $(k_{j},o_{j},f_{j})$ for each $j\in[2]$, the claim of Lemma 2 follows
as well. Analogously, if $\mathcal{C}(\mathcal{G})$ is closed under abscissa
and ordinate scaling, the supremum appearing in the definition of $\gamma_{\sf
W}({\sf EM},\mathcal{C})$ does not decrease when assuming $o=1$; thus, also
Lemma 1 holds under this assumption.

###### Example 1

To illustrate the claims of Theorem 1 and Lemma 2 with a concrete example, we
consider the problem of evaluating the competitive ratio of exact one-round
walks involving selfish players for affine weighted congestion games. Because
of Theorem 1 and Remark 2, we get that:

$\displaystyle\gamma_{\sf W}({\sf CR}^{s}_{0},\mathcal{P}(1))$
$\displaystyle=\inf_{x\geq 1}\sup_{f\in\mathcal{P}(1),k\geq
0}\left(kf(k)+x\left(f(k+1)-\int_{0}^{k}f(t)\text{dt}\right)\right)$
$\displaystyle=\inf_{x\geq
1}\sup_{\begin{subarray}{c}\alpha_{0},\alpha_{1}\geq 0\\\
k>0\end{subarray}}\left(\sum_{d\in\\{0,1\\}}\alpha_{d}k^{d+1}+x\left(\sum_{d\in\\{0,1\\}}\alpha_{d}(k+1)^{d}-\sum_{d\in\\{0,1\\}}\alpha_{d}\frac{k^{d+1}}{d+1}\right)\right)$
$\displaystyle=\inf_{x\geq
1}\sup_{d\in\\{0,1\\},k>0}\left(k^{d+1}+x\left((k+1)^{d}-\frac{k^{d+1}}{d+1}\right)\right)$
$\displaystyle=\min_{x>2}\sup_{k>0}\left(k^{2}+x\left(k+1-\frac{k^{2}}{2}\right)\right)$
$\displaystyle\leq\gamma\left({\sf
CR}^{s}_{0},\overbrace{\frac{2\sqrt{3}+6}{3}}^{x},\overbrace{\frac{\sqrt{3}+3}{\sqrt{3}}}^{k},\overbrace{1}^{o},f:f(t)=t\right)$
(6) $\displaystyle=2\sqrt{3}+4$

thus obtaining the same upper bound of [24]. Relatively to Lemma 2, we have
that the first case is verified. In particular, by setting
$k=\frac{\sqrt{3}+3}{\sqrt{3}}$, $o=1$ and $f$ in such a way that $f(t)=t$ for
any $t\geq 0$ (i.e. the parameters $k,o,f$ used in (6)), we get that the
second inequality of the first case of Lemma 2 is tight (i.e., $\beta_{\sf
W}({\sf CR}_{\epsilon}^{s},k,o,f)=0$), and $\frac{kf(k)}{of(o)}$ is equal to
$2\sqrt{3}+4$. Thus, by Remark 1, we necessarily have that $\gamma_{\sf
W}({\sf CR}^{s}_{0},\mathcal{P}(1))=2\sqrt{3}+4$.

###  3.2 Main Theorems

In the following theorem, we prove that, under mild assumptions on the latency
functions, no improvements are possible for $\epsilon$-approximate pure Nash
equilibria even when restricting to load balancing games.

###### Theorem 3.1

Let $\mathcal{C}$ be a class of latency functions that is closed under
ordinate and abscissa scaling. Then, $\gamma_{\sf W}({\sf PoA}_{\epsilon},{\sf
W}(\mathcal{C}))={\sf PoA}_{\epsilon}({\sf W}(\mathcal{C}))={\sf
PoA}_{\epsilon}({\sf WLB}(\mathcal{C})).$ If all latency functions of
$\mathcal{C}$ (except for the constant ones) are unbounded, we get
$\gamma_{\sf W}({\sf PoA}_{\epsilon},{\sf W}(\mathcal{C}))={\sf
PoA}_{\epsilon}({\sf W}(\mathcal{C}))={\sf PoA}_{\epsilon}({\sf
WSLB}(\mathcal{C}))$.

###### Proof

First of all, we consider the case in which all latency functions, except for
the constant ones, are unbounded. Fix $M<\gamma_{\sf W}({\sf
PoA}_{\epsilon},{\sf W}(\mathcal{C}))$. In the proof, we will show that there
exists a load balancing instance ${\sf LB}\in{\sf WSLB}(\mathcal{C})$ such
that ${\sf PoA}_{\epsilon}({\sf LB})>M$. By Lemma 1, this will imply that
$M<{\sf PoA}_{\epsilon}({\sf LB})\leq{\sf PoA}_{\epsilon}({\sf
W}(\mathcal{C}))\leq\gamma_{\sf W}({\sf PoA}_{\epsilon},{\sf
W}(\mathcal{C}))$, and by the arbitrariness of $M<\gamma_{\sf W}({\sf
PoA}_{\epsilon},{\sf W}(\mathcal{C}))$, this fact will show the claim. We make
use of a multi-graph, to represent a load balancing game together with two
special strategy profiles. This multi-graph is denoted as load balancing
graph, and is defined as follows: the nodes are all the resources in $E$, and
each player is associated to a weighted edge $(e_{1},e_{2},w)$, where
$\\{e_{1}\\}$ is denoted as her first strategy, $\\{e_{2}\\}$ is her second
strategy, and $w$ is her weight. With a little abuse of notation, any load
balancing graph will be also used to denote the corresponding load balancing
game.

If Case 2 of Lemma 2 holds (with respect to $\mathcal{C}$), let
$k_{1},k_{2},o_{1},o_{2},f_{1},f_{2},\alpha_{1}=\beta_{\sf W}({\sf
PoA}_{\epsilon},k_{2},o_{2},f_{2}),\alpha_{2}=-\beta_{\sf W}({\sf
PoA}_{\epsilon},k_{1},o_{1},f_{1})$ be the parameters considered in the claim
of Lemma 2. By Lemma 2, $f_{1}$ and $f_{2}$ can be chosen among the non-
constant latencies of $\mathcal{C}$, thus, by hypothesis, they are unbounded.
Furthermore, by Remark 2, we can assume without loss of generality that
$o_{1}=o_{2}=1$.

Let $s,n\in\mathbb{N}$ be two arbitrary positive integers. Consider a load
balancing graph ${\sf LB}_{s,n}(k_{1},k_{2},f_{1},f_{2})$ yielded by a
directed $n$-ary tree555With a little abuse of notation, the value of $n$
considered in such load-balancing instance does not represent the total number
of players, but the number of players selecting each resource when playing
their first strategy., organized in $2s$ levels, numbered from $1$ to $2s$,
and whose edges are oriented from the root to the leaves, with the addition of
$n$ self-loops on the nodes of level $2s$. The weight $w_{i}$ of a player
associated to an edge outgoing from a node at level $i\in[s]$ (resp.
$i\in[2s]_{s+1}$) is equal to $(k_{1}/n)^{i}$ (resp.
$(k_{1}/n)^{s}(k_{2}/n)^{i-s}$). For $i,j\in[2]$, define

$\theta_{i,j}:=\frac{f_{i}(k_{i})}{(1+\epsilon)f_{j}(k_{j}+1)}$

and $\theta_{i}:=\theta_{i,i}$. Each resource at level $i$ has latency

$g_{i}(x):=\begin{cases}\theta_{1}^{i-1}f_{1}\left(\left(\frac{n}{k_{1}}\right)^{i-1}x\right)&\text{
if }i\in[s],\\\
\theta_{1}^{s-1}\theta_{1,2}\theta_{2}^{i-s-1}f_{2}\left(\left(\frac{n}{k_{1}}\right)^{s}\left(\frac{n}{k_{2}}\right)^{i-s-1}x\right)&\text{
otherwise.}\end{cases}$

See Figure 5 for an example.

Figure 5: Figure 5 depicts a node/resource at some level $i\in[2s-2]_{2}$ of
the load balancing graph ${\sf LB}_{s,n}(k_{1},k_{2},f_{1},f_{2})$ with $n=5$,
and all the nodes/resources at level $i+1$ connected to the considered node at
level $i$. Each non-dashed (resp. dashed) rectangle on some node/resource
represents a player selecting that resource in ${\bm{\sigma}}_{s,n}$ (resp.
${\bm{\sigma}}^{*}_{s,n}$). The congestion of each resource in
${\bm{\sigma}}_{s,n}$ or ${\bm{\sigma}}^{*}_{s,n}$ is represented accordingly.
Let $K$ be the congestion of the resources at level $i$ in
${\bm{\sigma}}^{*}_{s,n}$. Then $K\cdot k_{j}$ is the congestion of the
resources at level $i$ in ${\bm{\sigma}}_{s,n}$, $K\cdot k_{j}/n$ is the
congestion of the resources at level $i+1$ in ${\bm{\sigma}}^{*}_{s,n}$, and
$K\cdot k_{j}\cdot k_{h}/n$ is the congestion of the resources at level $i+1$
in ${\bm{\sigma}}_{s,n}$, where $j=h=1$ if $i\in[s-1]$, $j=1$ and $h=2$ if
$i=s$, $j=h=2$ otherwise.

Let $\bm{\sigma}_{s,n}$ be the strategy profile in which all players select
their first strategy. We have the following lemma:

###### Lemma 3

For any integer $s\geq 2$, there exists $n(s)\in\mathbb{N}$, such that
$\bm{\sigma}_{s,n}$ is an $\epsilon$-approximate pure Nash equilibrium of
${\sf LB}_{s,n}(k_{1},k_{2},f_{1},f_{2})$ for any $n\geq n(s)$.

The proof of the above lemma is deferred to Section B of the appendix, and we
only give a sketch of the proof. We consider an arbitrary player whose first
strategy is a resource from a generic level $i$. Since the game is symmetric,
we have to check deviations to all possible strategies. We have that: (i) if
$i\in[2s-1]$ and the player deviates in favour of a resource from level
$j=i+1$, her cost decreases exactly of a factor $1+\epsilon$; (ii) if
$i\in[2s]$ and the player deviates in favour of a resource from level $j\leq
i$, her cost does not decrease; (iii) if $i\in[2s-2]$ and the player deviates
in favour of a resource from level $j>i+1$, for any sufficiently large $n$,
her cost does not decrease. In any case, the cost of the considered player,
when she deviates, cannot decrease of a factor higher than $1+\epsilon$, thus
${\bm{\sigma}}_{s,n}$ is a pure Nash equilibrium. In the appendix, we prove
separately all the three cases.

In the remainder of the proof, with the aim of estimating the approximate
price of anarchy of ${\sf LB}_{s,n}(k_{1},k_{2},f_{1},f_{2})$, we compare the
social value of the $\epsilon$-pure Nash equilibrium $\bm{\sigma}_{s,n}$, with
that of the strategy profile $\bm{\sigma}^{*}_{s,n}$ in which all players
select their second strategy. By exploiting the definition of
$\alpha_{1},\alpha_{2}$ given in Lemma 2, we necessarily get
$k_{1}\theta_{1}>1$ (from $\alpha_{2}>0$) and $k_{2}\theta_{2}<1$ (from
$\alpha_{1}>0$). We have that

$\displaystyle{\sf SUM}(\bm{\sigma}_{s,n})$
$\displaystyle=\sum_{i=1}^{2s}n^{i-1}w_{i}\cdot n\cdot g_{i}(n\cdot w_{i})$
$\displaystyle=\sum_{i=1}^{s}n^{i}\left(\frac{k_{1}}{n}\right)^{i}g_{i}\left(n\left(\frac{k_{1}}{n}\right)^{i}\right)$
$\displaystyle\ \ \ \ \ \ \
+\sum_{i=s+1}^{2s}n^{i}\left(\frac{k_{1}}{n}\right)^{s}\left(\frac{k_{2}}{n}\right)^{i-s}g_{i}\left(n\left(\frac{k_{1}}{n}\right)^{s}\left(\frac{k_{2}}{n}\right)^{i-s}\right)$
$\displaystyle=\sum_{i=1}^{s}k_{1}^{i}\theta_{1}^{i-1}f_{1}(k_{1})+\sum_{i=s+1}^{2s}k_{1}^{s}k_{2}^{i-s}\theta_{1}^{s-1}\theta_{1,2}\theta_{2}^{i-s-1}f_{2}(k_{2})$
$\displaystyle=\sum_{i=1}^{s}(k_{1}\theta_{1})^{i-1}k_{1}f_{1}(k_{1})+\sum_{i=s+1}^{2s}(k_{1}\theta_{1})^{s-1}k_{1}\theta_{1,2}(k_{2}\theta_{2})^{i-s-1}k_{2}f_{2}(k_{2})$
$\displaystyle=\sum_{i=0}^{s-1}(k_{1}\theta_{1})^{i}k_{1}f_{1}(k_{1})+(k_{1}\theta_{1})^{s-1}k_{1}\theta_{1,2}\sum_{i=0}^{s-1}(k_{2}\theta_{2})^{i}k_{2}f_{2}(k_{2})$
(7)
$\displaystyle=\left(\frac{(k_{1}\theta_{1})^{s}-1}{k_{1}\theta_{1}-1}\right)k_{1}f_{1}(k_{1})+(k_{1}\theta_{1})^{s-1}k_{1}\theta_{1,2}\left(\frac{1-(k_{2}\theta_{2})^{s}}{1-k_{2}\theta_{2}}\right)k_{2}f_{2}(k_{2}).$
(8)

Now, observe that in $\bm{\sigma}^{*}_{s,n}$ there are no players at level 1,
there is exactly one player of weight $(k_{1}/n)^{i-1}$ (resp.
$(k_{1}/n)^{s}(k_{2}/n)^{i-s-1})$) on each resource at level $i\in[s+1]_{2}$
(resp. $i\in[2s-1]_{s+2}$), and there are $n+1$ players on each resource at
level $2s$. We get666The definition of $[<]_{s}(F(s))$ has been given in the
preliminaries, and substitutes the usual asymptotic notation.

$\displaystyle{\sf SUM}(\bm{\sigma}^{*}_{s,n})$
$\displaystyle=\sum_{i=2}^{2s-1}n^{i-1}w_{i-1}\cdot
g_{i}(w_{i-1})+n^{2s-1}(n\cdot w_{2s}+w_{2s-1})g_{2s}(n\cdot w_{2s}+w_{2s-1})$
$\displaystyle=\sum_{i=2}^{s+1}\left(n^{i-1}\left(\frac{k_{1}}{n}\right)^{i-1}\right)g_{i}\left(\left(\frac{k_{1}}{n}\right)^{i-1}\right)$
$\displaystyle\ \ \ \ \ \ \
+\sum_{i=s+2}^{2s-1}n^{i-1}\left(\frac{k_{1}}{n}\right)^{s}\left(\frac{k_{2}}{n}\right)^{i-s-1}g_{i}\left(\left(\frac{k_{1}}{n}\right)^{s}\left(\frac{k_{2}}{n}\right)^{i-s-1}\right)$
$\displaystyle\ \ \ \ \ \ \ +n^{2s-1}(n\cdot w_{2s}+w_{2s-1})g_{2s}(n\cdot
w_{2s}+w_{2s-1})$
$\displaystyle=\sum_{i=2}^{s}k_{1}^{i-1}\theta_{1}^{i-1}f_{1}(1)+\sum_{i=s+1}^{2s-1}k_{1}^{s}k_{2}^{i-s-1}\theta_{1}^{s-1}\theta_{1,2}\theta_{2}^{i-s-1}f_{2}(1)$
$\displaystyle\ \ \ \ \ \ \
+k_{1}^{s}k_{2}^{s-1}(k_{2}+1)\theta_{1}^{s-1}\theta_{1,2}\theta_{2}^{s-1}f_{2}(k_{2}+1)$
(9)
$\displaystyle=\sum_{i=1}^{s}k_{1}^{i-1}\theta_{1}^{i-1}f_{1}(1)+\sum_{i=s+1}^{2s-1}k_{1}^{s}k_{2}^{i-s-1}\theta_{1}^{s-1}\theta_{1,2}\theta_{2}^{i-s-1}f_{2}(1)$
$\displaystyle\ \ \ \ \ \ \
\overbrace{-f_{1}(1)+k_{1}^{s}k_{2}^{s-1}(k_{2}+1)\theta_{1}^{s-1}\theta_{1,2}\theta_{2}^{s-1}f_{2}(k_{2}+1)}^{[<]_{s}\left((k_{1}\theta_{1})^{s-1}\right)}$
$\displaystyle=\sum_{i=0}^{s-1}(k_{1}\theta_{1})^{i}f_{1}(1)+(k_{1}\theta_{1})^{s-1}k_{1}\theta_{1,2}\sum_{i=0}^{s-1}(k_{2}\theta_{2})^{i}f_{2}(1)+[<]_{s}\left((k_{1}\theta_{1})^{s-1}\right)$
$\displaystyle=\frac{(k_{1}\theta_{1})^{s}-1}{k_{1}\theta_{1}-1}f_{1}(1)+(k_{1}\theta_{1})^{s-1}k_{1}\theta_{1,2}\frac{1-(k_{2}\theta_{2})^{s}}{1-k_{2}\theta_{2}}f_{2}(1)+[<]_{s}\left((k_{1}\theta_{1})^{s-1}\right).$
(10)

By using (8) and (10), inequalities $k_{1}\theta_{1}>1$ and
$k_{2}\theta_{2}<1$, and the fact that ${\bm{\sigma}}_{s,n}$ is a pure Nash
equilibrium of ${\sf LB}_{s,n}(k_{1},k_{2},f_{1},f_{2})$ for any $s$ and any
sufficiently large $n$ (by Lemma 3), we get

$\displaystyle\sup_{s,n\in\mathbb{N}}{\sf PoA}_{\epsilon}({\sf
LB}_{s,n}(k_{1},k_{2},f_{1},f_{2}))$
$\displaystyle\geq\lim_{s\rightarrow\infty}\lim_{n\rightarrow\infty}\frac{{\sf
SUM}(\bm{\sigma}_{s,n})}{{\sf SUM}(\bm{\sigma}^{*}_{s,n})}$
$\displaystyle=\lim_{s\rightarrow\infty}\lim_{n\rightarrow\infty}\frac{{\sf
SUM}(\bm{\sigma}_{s,n})/(k_{1}\theta_{1})^{s-1}}{{\sf
SUM}(\bm{\sigma}^{*}_{s,n})/(k_{1}\theta_{1})^{s-1}}$
$\displaystyle=\frac{\frac{k_{1}\theta_{1}}{k_{1}\theta_{1}-1}k_{1}f_{1}(k_{1})+k_{1}\theta_{1,2}\left(\frac{1}{1-k_{2}\theta_{2}}\right)k_{2}f_{2}(k_{2})}{\frac{k_{1}\theta_{1}}{k_{1}\theta_{1}-1}f_{1}(1)+k_{1}\theta_{1,2}\left(\frac{1}{1-k_{2}\theta_{2}}\right)f_{2}(1)}$
$\displaystyle=\frac{\left(\frac{k_{1}f_{1}(k_{1})}{k_{1}f_{1}(k_{1})-(1+\epsilon)f_{1}(k_{1}+1)}\right)k_{1}f_{1}(k_{1})+\left(\frac{k_{1}f_{1}(k_{1})}{(1+\epsilon)f_{2}(k_{2}+1)-k_{2}f_{2}(k_{2})}\right)k_{2}f_{2}(k_{2})}{\left(\frac{k_{1}f_{1}(k_{1})}{k_{1}f_{1}(k_{1})-(1+\epsilon)f_{1}(k_{1}+1)}\right)f_{1}(1)+\left(\frac{k_{1}f_{1}(k_{1})}{(1+\epsilon)f_{2}(k_{2}+1)-k_{2}f_{2}(k_{2})}\right)f_{2}(1)}$
$\displaystyle=\frac{\left(\frac{k_{1}f_{1}(k_{1})}{\alpha_{2}}\right)k_{1}f_{1}(k_{1})+\left(\frac{k_{1}f_{1}(k_{1})}{\alpha_{1}}\right)k_{2}f_{2}(k_{2})}{\left(\frac{k_{1}f_{1}(k_{1})}{\alpha_{2}}\right)f_{1}(1)+\left(\frac{k_{1}f_{1}(k_{1})}{\alpha_{1}}\right)f_{2}(1)}$
$\displaystyle=\frac{\alpha_{1}k_{1}f_{1}(k_{1})+\alpha_{2}k_{2}f_{2}(k_{2})}{\alpha_{1}f_{1}(1)+\alpha_{2}f_{2}(1)}$
$\displaystyle>M,$ (11)

where (11) comes from Lemma 2. Thus, by (11), we can choose $s$ and $n$ in
such a way that ${\sf PoA}_{\epsilon}({\sf
LB}_{s,n}(k_{1},k_{2},f_{1},f_{2}))>M$, and this shows the claim when Case 2
of Lemma 2 holds.

Now, suppose that Case 1 of Lemma 2 holds, and let $k,o,f$ be the parameters
considered in that case; as done previously, by Remark 2, we can assume
without loss of generality that $o=1$. The load balancing instance we consider
here is ${\sf LB}_{s,n}(k,k,f,f)$, and the strategy profile
${\bm{\sigma}}_{s,n}$ and ${\bm{\sigma}}^{*}_{s,n}$ are defined as in the
previous part of the proof. To evaluate ${\sf SUM}({\bm{\sigma}}_{s,n})$,
observe that all equalities up to (7) hold. Therefore, by continuing from (7),
we get

${\sf SUM}({\bm{\sigma}}_{s,n})=2skf(k)$

if $\beta_{\sf W}({\sf PoA}_{\epsilon},k,o,f)=0$ (since, in such case, we have
$k\theta_{1}=k\theta_{2}=1$) and

${\sf
SUM}(\bm{\sigma}_{s,n})=\frac{1-\left(\frac{kf(k)}{(1+\epsilon)f(k+1)}\right)^{2s}}{1-\frac{kf(k)}{(1+\epsilon)f(k+1)}}kf(k)$

if $\beta_{\sf W}({\sf PoA}_{\epsilon},k,o,f)>0$ (since now we have
$k\theta_{1}=k\theta_{2}<1$). Analogously, to evaluate ${\sf
SUM}(\bm{\sigma}^{*}_{s,n})$, observe that all equalities up to (9) hold.
Therefore, by continuing from (9) we get

${\sf SUM}(\bm{\sigma}^{*}_{s,n})=2sf(1)+[\leq]_{s}(1)$

if $\beta_{\sf W}({\sf PoA}_{\epsilon},k,o,f)=0$, and

${\sf
SUM}(\bm{\sigma}^{*}_{s,n})=\frac{1-\left(\frac{kf(k)}{(1+\epsilon)f(k+1)}\right)^{2s}}{1-\frac{kf(k)}{(1+\epsilon)f(k+1)}}f(1)-f(1)+[<]_{s}(1)$

if $\beta_{\sf W}({\sf PoA}_{\epsilon},k,o,f)>0$. Thus, again, we get

$\sup_{s,n\in\mathbb{N}}{\sf PoA}_{\epsilon}({\sf
LB}_{s,n}(k,k,f,f))\geq\lim_{s\rightarrow\infty}\lim_{n\rightarrow\infty}\frac{{\sf
SUM}(\bm{\sigma}_{s,n})}{{\sf
SUM}(\bm{\sigma}^{*}_{s,n})}\geq\frac{kf(k)}{f(1)}>M,$

where the last inequality follows from Case 1 of Lemma 2.

By exploiting the above inequality, we can choose $s$ and $n$ in such a way
that ${\sf PoA}_{\epsilon}({\sf LB}_{s,n}(k,k,f,f))>M$, and this shows the
claim when Case 1 of Lemma 2 holds. We conclude that the approximate price of
anarchy does not improve when restricting to symmetric load balancing games,
if all non-constant latency functions are unbounded.

If there is some non-constant latency function in $\mathcal{C}(\mathcal{G})$
that is not unbounded, we can consider a general (asymmetric) load balancing
game based on the load balancing graph ${\sf
LB}_{s,n}(k_{1},k_{2},f_{1},f_{2})$ defined above with $n=1$ (i.e., the load
balancing graph is a directed path), but where each player can select among
her first and second strategy only, and based on the parameters
$k_{1},k_{2},f_{1},f_{2}$ or $k,f$ derived according to Lemma 2. Let
${\bm{\sigma}}_{s,1}$ and ${\bm{\sigma}}_{s,1}^{*}$ be the strategy profiles
defined above (with $n=1$). By using a similar proof as in Lemma 3, we have
that ${\bm{\sigma}}_{s,1}$ is an $\epsilon$-approximate pure Nash equilibrium.
Indeed, the unique deviation that must be analysed is when each player located
at level $i$ in ${\bm{\sigma}}_{s,1}$ deviates in favour of a resource at
level $i+1$ (case (i) in the proof of the lemma), and showing that such
deviation does not give any benefit to that player does not require the
unboundedness of the latency functions. Finally, we can reuse the last part of
the above proof to show that, for sufficiently large $s$, ${\sf
PoA}_{\epsilon}({\sf LB}_{s,1}(k_{1},k_{2},f_{1},f_{2}))>M$. Thus, by the
arbitrariness of $M$, we have $\gamma_{\sf W}({\sf PoA}_{\epsilon},{\sf
W}(\mathcal{C}))={\sf PoA}_{\epsilon}({\sf W}(\mathcal{C}))={\sf
PoA}_{\epsilon}({\sf WLB}(\mathcal{C}))$ which shows the claim.∎

Now, we prove that no improvements are possible for approximate one-round
walks when restricting to load balancing games.

###### Theorem 3.2

Let $\mathcal{C}$ be a class of latency functions that is closed under
ordinate and abscissa scaling. Then, $\gamma_{\sf W}({\sf
CR}^{s}_{\epsilon},{\sf W}(\mathcal{C}))={\sf CR}^{s}_{\epsilon}({\sf
W}(\mathcal{C}))={\sf CR}^{s}_{\epsilon}({\sf WLB}(\mathcal{C}))$. If all
functions in $\mathcal{C}$ are also semi-convex, we have that $\gamma_{\sf
W}({\sf CR}^{c}_{\epsilon},{\sf W}(\mathcal{C}))={\sf CR}^{c}_{\epsilon}({\sf
W}(\mathcal{C}))={\sf CR}^{c}_{\epsilon}({\sf WLB}(\mathcal{C})).$

###### Proof

Fix $M<\gamma_{\sf W}({\sf EM},{\sf W}(\mathcal{C}))$, where ${\sf
EM}\in\\{{\sf CR}^{s}_{\epsilon},{\sf CR}^{c}_{\epsilon}\\}$ is the considered
efficiency metric. As in Theorem 3.1, by Lemma 1, it is sufficient showing
that there exists a load balancing game ${\sf LB}\in{\sf WLB}(\mathcal{C})$
such its competitive ratio is at least $M$.

We start with the case of selfish players. Let
$k_{1},k_{2},f_{1},f_{2},\alpha_{1},\alpha_{2}$ (resp. $k,o,f$) be the
parameters considered in Case 2 (resp. Case 1) of Lemma 2, but related to
${{\sf EM}}={\sf CR}_{\epsilon}^{s}$. For simplicity, in the following we set
$k_{1}=k_{2}=k$, $o_{1}=o_{2}=o$, and $f_{1}=f_{2}=f$, if Case 1 of Lemma 2
holds. By Remark 2, we can assume without loss of generality that
$o_{1}=o_{2}=1$.

As in Theorem 3.1, we resort to a load-graph representation. In particular, we
extend the load balancing graph ${\sf LB}_{s,n}(k_{1},k_{2},f_{1},f_{2})$
defined in the proof of Theorem 3.1 as follows. Denote as $i(v)$ the level of
resource $v$. For each node $u$ in the load balancing graph, consider an
arbitrary enumeration of all the $n$ outgoing edges of $u$. Since each node
has a unique incoming edge, we denote by $h(v)\in[n]$ the label/position
associated to the unique edge entering $v$ in the given ordering, so that, for
any node $u$, all the $n$ edges of type $(u,v)$ are associated to a label
$h(v)\in[n]$.

For $i,j\in[2]$ and $h\in[n]$, define

$\theta_{i,j}(h):=\frac{f_{i}\left(\frac{hk_{i}}{n}\right)}{(1+\epsilon)f_{j}(k_{j}+1)}$

and $\theta_{i}(h):=\theta_{i,i}(h)$. Resource $v$ has latency function

$g_{v}(x):=\begin{cases}f_{1}(x)&\text{ if }i(v)=1,\\\
\underbrace{\theta_{1}(h(v))A_{u}}_{A_{v}}f_{1}\left(\left(\frac{n}{k_{1}}\right)^{i(v)-1}x\right)&\text{
if }i(v)\in[s]_{2},\\\
\underbrace{\theta_{1,2}(h(v))A_{u}}_{A_{v}}f_{2}\left(\left(\frac{n}{k_{1}}\right)^{s}x\right)&\text{
if }i(v)=s+1,\\\
\underbrace{\theta_{2}(h(v))A_{u}}_{A_{v}}f_{2}\left(\left(\frac{n}{k_{1}}\right)^{s}\left(\frac{n}{k_{2}}\right)^{i(v)-s-1}x\right)&\text{
if }i(v)\in[2s]_{s+2},\end{cases}$

where $(u,v)$ denotes the unique incoming edge of $v$ and $A_{v}$ is
recursively defined on the basis of $A_{u}$ by setting $A_{v}=1$ for $i(v)=1$,
i.e., for $v$ being the root of the tree. The weights of all players are
defined as in Theorem 3.1.

Consider the online process $\bm{\tau}_{s,n}$ in which players enter the game
in non-increasing order of level (with respect to their first strategy) and,
within the same level, players are processed in non-decreasing order of
position; equivalently, if two players $i_{u}$ and $i_{v}$ have, as their
first strategies, some resources $u$ and $v$ respectively, such that either
$i(u)>i(v)$, or $i(u)=i(v)\wedge h(u)<h(v)$, then player $i_{u}$ is processed
before player $i_{v}$ in the online process $\bm{\tau}_{s,n}$. Let
${\bm{\sigma}}_{s,n}$ be strategy profile obtained at the end of the process,
i.e., the strategy profile in which each player selects her first strategy. We
have the following lemma:

###### Lemma 4

The online process $\bm{\tau}_{s,n}$ is an $\epsilon$-approximate one-round
walk.

The above lemma can be shown as follows. Let $z$ be an arbitrary player whose
first strategy is at level $i\in[2s-1]$; let $u,v$ be the first and second
strategy of $z$, respectively, and let $h:=h(v)$ be the position/label
associated to resource $v$. By construction of the online process
$\bm{\tau}_{s,n}$, we have that, when $z$ enters the game, there are $h-1$
players of weight $w_{i}$ already assigned to resource $u$, and $n$ players of
weight $w_{i+1}$ assigned to resource $v$. Let ${\bm{\sigma}}^{u}_{s,n}$ be
the partial strategy profile obtained when $z$ is processed according to
$\bm{\tau}_{s,n}$ (i.e., only players preceding $z$ have been already
assigned), and $z$ is assigned to her first strategy $u$; let
${\bm{\sigma}}^{v}_{s,n}$ be the partial strategy profile in which $z$,
instead, is assigned to her second strategy $v$. As our choice of player $z$
has been arbitrary, it is sufficient proving that
$cost_{z}({\bm{\sigma}}^{u}_{s,n})\leq(1+\epsilon)cost_{z}({\bm{\sigma}}^{v}_{s,n})$
to show that $\bm{\tau}_{s,n}$ is an $\epsilon$-approximate one-round walk. By
using the recursive definitions of the latency functions $g_{i}$ and $g_{i+1}$
(involving the quantities $A_{u}$ and $A_{v}$, respectively), and by using a
similar approach as in case (i) of Lemma 3, one can easily show that
$cost_{z}({\bm{\sigma}}^{u}_{s,n})=g_{u}(h\cdot
w_{i})=(1+\epsilon)g_{v}(n\cdot
w_{i+1}+w_{i})=(1+\epsilon)cost_{z}({\bm{\sigma}}^{v}_{s,n})$, thus showing
the claim of Lemma 4.

Now, let ${\bm{\sigma}}^{*}_{s,n}$ be the strategy profile in which all
players select their second strategy. In the remainder of the proof, with the
aim of estimating the competitive ratio of ${\sf
LB}_{s,n}(k_{1},k_{2},f_{1},f_{2})$, we compare the social value of the
strategy profile ${\bm{\sigma}}_{s,n}$ resulting from the
$\epsilon$-approximate one-round walk $\bm{\tau}_{s,n}$ with that of strategy
profile $\bm{\sigma}^{*}_{s,n}$. For $i,j\in[2]$, let $\xi_{i,j}$ denote
quantity $\frac{\int_{t=0}^{k}f_{i}(t)\text{dt}}{(1+\epsilon)f_{j}(k_{j}+1)}$,
let $\xi_{i}:=\xi_{i,i}$, and let ${\sf SUM}_{i}({\bm{\sigma}_{s,n}})$ denote
the weighted total latency in ${\bm{\sigma}}_{s,n}$ of all the resources at
level $i\in[2s]$. We have that

$\displaystyle{\sf SUM}_{i}({\bm{\sigma}_{s,n}})$ $\displaystyle=\sum_{v\text{
in level
}i}k_{v}({\bm{\sigma}}_{s,n})g_{v}\left(k_{v}(\bm{\sigma}_{s,n})\right)$
$\displaystyle=\sum_{(h_{1},h_{2},\ldots,h_{i-1})\in[n]^{i-1}}n\cdot\overbrace{\left(\frac{k_{1}}{n}\right)^{i}}^{w_{i}}\left(\prod_{t=1}^{i-1}\theta_{1}(h_{t})\right)f_{1}(k_{1})$
$\displaystyle=\frac{k_{1}^{i}}{n^{i-1}}\left(\sum_{h=1}^{n}\theta_{1}(h)\right)^{i-1}f_{1}(k_{1})$
$\displaystyle=\left(\sum_{h=1}^{n}\theta_{1}(h)\frac{k_{1}}{n}\right)^{i-1}k_{1}f_{1}(k_{1})$
$\displaystyle=\left(\sum_{h=1}^{n}\frac{f_{i}\left(\frac{hk_{1}}{n}\right)}{(1+\epsilon)f_{j}(k_{1}+1)}\left(\frac{k_{1}}{n}\right)\right)^{i-1}k_{1}f_{1}(k_{1})$
$\displaystyle\overrightarrow{n\rightarrow\infty}\left(\frac{\int_{t=0}^{k}f_{1}(t)\text{dt}}{(1+\epsilon)f_{1}(k_{1}+1)}\right)^{i-1}k_{1}f_{1}(k_{1})$
$\displaystyle=\xi_{1}^{i-1}k_{1}f_{1}(k_{1})$ (12)

if $i\in[s]$, and (by using similar arguments)

$\displaystyle{\sf SUM}_{i}({\bm{\sigma}_{s,n}})$
$\displaystyle=\left(\sum_{h=1}^{n}\theta_{1}(h)\frac{k_{1}}{n}\right)^{s-1}\left(\sum_{h=1}^{n}\theta_{1,2}(h)\frac{k_{1}}{n}\right)\left(\sum_{h=1}^{n}\theta_{2}(h)\frac{k_{2}}{n}\right)^{i-1-s}k_{2}f_{2}(k_{2})$
$\displaystyle\overrightarrow{n\rightarrow\infty}\ \ \
\xi_{1}^{s-1}\cdot\xi_{1,2}\cdot\xi_{2}^{i-1-s}k_{2}f_{2}(k_{2}),$ (13)

if $i\in[2s]_{s+1}$. Now, for any fixed $s\geq 2$, we can compute
$\lim_{n\rightarrow\infty}{\sf SUM}({\bm{\sigma}_{s,n}})$. If Case 2 of Lemma
2 holds, we have that $\xi_{1}>0$ and $\xi_{2}<0$. Thus, by using similar
arguments as in Theorem 3.1 (in particular, as in equality (8)), and by using
(12) and (13), we get

$\displaystyle\lim_{n\rightarrow\infty}{\sf SUM}({\bm{\sigma}_{s,n}})$
$\displaystyle=\lim_{n\rightarrow\infty}\sum_{i=1}^{2s}{\sf
SUM}_{i}({\bm{\sigma}_{s,n}})$
$\displaystyle=\sum_{i=0}^{s-1}\xi_{1}^{i}k_{1}f_{1}(k_{1})+\xi_{1}^{s-1}\cdot\xi_{1,2}\sum_{i=0}^{s-1}\xi_{2}^{i}k_{2}f_{2}(k_{2})$
$\displaystyle=\left(\frac{\xi_{1}^{s}-1}{\xi_{1}-1}\right)k_{1}f_{1}(k_{1})+\xi_{1}^{s-1}\xi_{1,2}\left(\frac{1-\xi_{2}^{s}}{1-\xi_{2}}\right)k_{2}f_{2}(k_{2});$

analogously, if Case 1 of Lemma 2 holds, we have that
$\lim_{n\rightarrow\infty}{\sf SUM}({\bm{\sigma}_{s,n}})=2skf(k)$ if
$\beta_{\sf W}({\sf CR}_{\epsilon}^{s},k,o,f)=0$ (as $\xi_{1}=\xi_{2}=1$), and
$\lim_{n\rightarrow\infty}{\sf
SUM}({\bm{\sigma}_{s,n}})=\frac{1-\xi_{1}^{s}}{1-\xi_{1}}kf(k)$ if $\beta_{\sf
W}({\sf CR}_{\epsilon}^{s},k,o,f)>0$ (as $\xi_{1}=\xi_{2}<1$).

By using analogous steps as in (12) and (13), one can show that the weighted
total latency ${\sf SUM}_{i}({\bm{\sigma}}_{s,n}^{*})$ in
${\bm{\sigma}}^{*}_{s,n}$ of resources at level $i\in[2s-1]_{2}$ can be
obtained by replacing each $k_{j}f_{j}(k_{j})$ with $f_{j}(1)$ in (12) and
(13) and, analogously to Theorem 3.1, one can also compute ${\sf
SUM}({\bm{\sigma}}_{s,n}^{*})$, that is equal to $\sum_{i=2}^{2s-1}{\sf
SUM}_{i}({\bm{\sigma}}_{s,n}^{*})+[<]_{s}\left(\sum_{i=2}^{2s-1}{\sf
SUM}_{i}({\bm{\sigma}}_{s,n}^{*})\right)$ (as in Theorem 3.1, the contribution
of resources at level $1$ and $2s$ to the social cost is not significant). At
this point, by using the same proof arguments of Theorem 3.1 (in particular,
as in (11)), we get

$\displaystyle\lim_{s\rightarrow\infty}\lim_{n\rightarrow\infty}{\sf
CR}_{\epsilon}^{s}({\sf LB}_{s,n}(k_{1},k_{2},f_{1},f_{2}))$
$\displaystyle\geq\lim_{s\rightarrow\infty}\lim_{n\rightarrow\infty}\frac{{\sf
SUM}({\bm{\sigma}_{s,n}})}{{\sf SUM}({\bm{\sigma}}_{s,n}^{*})}$
$\displaystyle\geq\frac{\alpha_{1}k_{1}f_{1}(k_{1})+\alpha_{2}k_{2}f_{2}(k_{2})}{\alpha_{1}f_{1}(1)+\alpha_{2}f_{2}(1)}$
$\displaystyle>M,$

where the last inequality comes from Lemma 2. Thus, the claim holds for the
case of selfish players.

For cooperative players, let
$k_{1},k_{2},o_{1},o_{2},f_{1},f_{2},\alpha_{1},\alpha_{2}$ as in Lemma 2
(remove index $j\in[2]$ and set $\alpha=1$ if Case 1 of Lemma 2 is verified).
By Remark 2, we assume without loss of generality that $o_{1}=o_{2}=1$.
Consider a load balancing graph ${\sf LB}_{s,n}(k_{1},k_{2},f_{1},f_{2})$ as
that defined above, but with $n=1$ and
$\theta_{i,j}(1):=\frac{f_{i}(k_{i})}{(1+\epsilon)((k_{j}+1)f_{j}(k_{j}+1)-k_{j}f_{j}(k_{j}))}$.
Let ${\bm{\sigma}}_{s,1}$, $\bm{\tau}_{s,1}$, and ${\bm{\sigma}}^{*}_{s,1}$ be
defined as in the case of selfish players (with $n=1$). Similarly as in the
case of selfish players, one can show that $\bm{\tau}_{s,1}$ is an
$\epsilon$-approximate one-round walk (involving cooperative players) that
generates strategy profile ${\bm{\sigma}}_{s,1}$, and we can show again that

$\displaystyle\lim_{s\rightarrow\infty}\lim_{n\rightarrow\infty}{\sf
CR}_{\epsilon}^{c}({\sf LB}_{s,n}(k_{1},k_{2},f_{1},f_{2}))$
$\displaystyle\geq\lim_{s\rightarrow\infty}\lim_{n\rightarrow\infty}\frac{{\sf
SUM}({\bm{\sigma}_{s,n}})}{{\sf SUM}({\bm{\sigma}}_{s,n}^{*})}$
$\displaystyle\geq\frac{\alpha_{1}k_{1}f_{1}(k_{1})+\alpha_{2}k_{2}f_{2}(k_{2})}{\alpha_{1}f_{1}(1)+\alpha_{2}f_{2}(1)}$
$\displaystyle>M;$

this shows that ${\sf CR}_{\epsilon}^{c}({\sf
LB}_{s,1}(k_{1},k_{2},f_{1},f_{2}))>M$ for a sufficiently large $s$, and the
claim follows. ∎

###### Remark 3

Fix a metric ${\sf EM}\in\\{{\sf PoA}_{\epsilon},{\sf CR}^{s}_{\epsilon},{\sf
CR}^{c}_{\epsilon}\\}$, a class of latency functions $\mathcal{C}$, and let
$(k_{1},k_{2},o_{1},o_{2},f_{1},f_{2})$ (resp. $(k,o,f)$) be a tuple such that
values $\alpha_{1},\alpha_{2}$ considered in Case 2 of Lemma 2 are positive
(resp. such that the inequality of Case 1 corresponding to the considered
metric EM is satisfied, i.e., $\beta_{\sf W}({\sf EM},k,o,f)\geq 0$). By
Remark 2, we assume without loss of generality that $o_{1}=o_{2}=1$ (resp.
$o=1$). By inspecting the proofs of Theorem 3.1 and 3.2, we observe that the
set of load balancing instances of type ${\sf
LB}_{s,n}(k_{1},k_{2},f_{1},f_{2})$ (resp. ${\sf LB}_{s,n}(k,k,f,f)$)
guarantees a performance of at least
$\frac{\alpha_{1}k_{1}f_{1}(k_{1})+\alpha_{2}k_{2}f_{2}(k_{2})}{\alpha_{1}f(1)+\alpha_{2}f(2)}$
(resp. $\frac{kf(k)}{f(1)}$) under the considered metric ${\sf EM}$. Thus, in
the case we are not able to quantify the exact value of $\gamma_{\sf W}({\sf
EM},{\sf W}(\mathcal{C}))$, we can still find a tuple
$(k_{1},k_{2},f_{1},f_{2})$ (resp. $(k,f)$) that leads to good (and possibly
tight) lower bounds; furthermore, the tightness can be shown by resorting to
the characterization provided in Remark 1.

###  3.3 Application to Polynomial Latency Functions

Consider the class $\mathcal{P}(d)$ of polynomials with non-negative
coefficients and maximum degree $d$. By Lemma 1, $\gamma_{\sf W}({\sf EM},{\sf
W}(\mathcal{P}(d)))$ is an upper bound on the efficiency metrics ${\sf
EM}\in\\{{\sf PoA}_{\epsilon},{\sf CR}^{s}_{\epsilon},{\sf
CR}^{c}_{\epsilon}\\}$ for weighted congestion games and load balancing games
with polynomial latency functions of maximum degree $d$.

By exploiting the definition of $\gamma_{\sf W}({\sf EM},{\sf
W}(\mathcal{P}(d)))$ given at the beginning of this section, and by applying
to these definitions similar arguments as those used in [3, 24] we can compute
the exact value of $\gamma_{\sf W}({\sf EM},{\sf W}(\mathcal{P}(d)))$ for any
${\sf EM}\in\\{{\sf PoA}_{\epsilon},{\sf CR}^{s}_{\epsilon},{\sf
CR}^{c}_{\epsilon}\\}$777In [3, 24], the upper bounds on the performance of
congestion games have been represented in terms of smoothness inequalities
(see Section A of the appendix), but can be easily rewritten in terms of the
upper bound $\gamma_{\sf W}({\sf EM},{\sf W}(\mathcal{P}(d)))$. Thus, since
the exact quantification of $\gamma_{\sf W}({\sf EM},{\sf W}(\mathcal{P}(d)))$
relies on results and/or proof arguments already appeared, we omit the
mathematical analysis and we give the final numerical values. Furthermore, we
point out that the main focus of this subsection is not computing $\gamma_{\sf
W}({\sf EM},{\sf W}(\mathcal{P}(d)))$, but applying Theorem 3.1 and 3.2 to
provide tight bounds on the performance of load balancing games with
polynomial latency functions. . In particular, we have that $\gamma_{\sf
W}({\sf EM},{\sf W}(\mathcal{P}(d)))$ is equal to
$\left(\varphi_{\epsilon,d}\right)^{d}$, where $\varphi_{\epsilon,d}$ is
defined as the unique solution $k\geq 0$ of equation
$-k^{d+1}+(1+\epsilon)(k+1)^{d}=0$ if ${\sf EM}={\sf PoA}_{\epsilon}$, of
equation $-\frac{k^{d+1}}{d+1}+(1+\epsilon)(k+1)^{d}=0$ if ${\sf EM}={\sf
CR}^{s}_{\epsilon}$, and of equation
$-(2+\epsilon)k^{d+1}+(1+\epsilon)(k+1)^{d+1}=0$ if ${\sf EM}={\sf
CR}^{c}_{\epsilon}$.

Some of the above upper bounds have already appeared in works based on the
study of congestion games. $\gamma_{\sf W}({\sf PoA}_{\epsilon},{\sf
W}(\mathcal{P}(d)))$ has been already evaluated in [3, 23]. The bounds related
to the $\epsilon$-approximate one-walks generated by selfish players
generalize the results obtained in [24], in which the same bounds have been
shown for affine latency functions and $\epsilon=0$, only; for more general
polynomial latency functions and $\epsilon=0$, the bounds related to the
$\epsilon$-approximate one-walks have been re-obtained and shown in more
detail in [38], subsequently to the preliminary version of our work.

Finally, for $\epsilon=0$ and general polynomial latencies, the bounds related
to cooperative players can be equivalently derived from the analysis provided
in [16], in which the greedy algorithm has been applied to minimize the
$L_{p}$ norm in load balancing problems.

A way to interpret the above tight bounds is provided by Remark 1. In
particular, one can show that the exact value of $\gamma_{\sf W}({\sf EM},{\sf
W}(\mathcal{P}(d)))$ is attained by $\frac{kf(k)}{f(1)}$, where $f$ is the
monomial function defined as $f(t)=t^{d}$ for any $t\geq 0$, and $k$ is the
unique value satisfying constraint $\beta_{\sf W}({\sf EM},k,1,f)\geq 0$ at
equality.

Since the class of polynomial latency functions $\mathcal{P}(d)$ satisfies the
hypothesis of Theorem 3.1 and 3.2, as a corollary we have that the values
$\gamma_{\sf W}({\sf EM},{\sf W}(\mathcal{P}(d)))$ considered above are tight
bounds on the performance of load balancing instances, and even of symmetric
load balancing instances if the efficiency metric is the $\epsilon$-price of
anarchy. Thus, for polynomial latency functions, the performance does not
improve when assuming singleton strategies. Furthermore, our findings can be
used to close the gap between upper and lower bounds on the competitive ratio
of exact one-round walks generated by selfish players, for congestion games
with affine latency functions. Indeed, [24] showed that $\gamma_{\sf W}({\sf
CR}^{s}_{0},{\sf W}(\mathcal{P}(1)))=2\sqrt{3}+4\approx 7.464$ is an upper
bound, and [9] provided a lower bound of $2+\sqrt{5}\approx 4.236$ (holding
even for unweighted congestion games); closing the above gap has been left as
an open question. Our results directly imply that the upper bound $\approx
7.464$ provided by [24] is tight, even for load balancing games. See Table 6
for some numerical comparisons.

$d$ |  ${\sf PoA}_{0}({\sf W}(\mathcal{P}(d)))$ [3, 7] | ${\sf CR}_{0}^{s}({\sf W}(\mathcal{P}(d)))$ |  ${\sf CR}_{0}^{c}({\sf W}(\mathcal{P}(d)))$ [16]
---|---|---|---
1 | 2.618 [4, 20] | 7.464 [24] | 5.828 [20]
2 | 9.909 | 90.3 | 56.94
3 | 47.82 | 1,521 | 780.2
4 | 277 | 32,896 | 13,755
5 | 1,858 | 868,567 | 296,476
6 | 14,099 | 27,089,557 | 7,553,550
7 | 118,926 | 974,588,649 | 222,082,591
8 | 1,101,126 | 39,729,739,895 | 7,400,694,480
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$
$\infty$ | $(\Theta(d/\log(d)))^{d+1}$ | $(\Theta(d))^{d+1}$ | $(\Theta(d))^{d+1}$
Figure 6: The price of anarchy and the competitive ratio of exact one-round
walks (generated by selfish or cooperative players) in weighted congestion
games or load balancing games with polynomial latency functions of maximum
degree $d$. Our findings provide tight lower bounds for the competitive ratio
under selfish players, holding even for load balancing games.

##  4 Unweighted Load Balancing Games

In this section, we show that, under mild assumptions on the latency
functions, the $\epsilon$-approximate price of anarchy and the competitive
ratio of selfish or cooperative $\epsilon$-approximate one-round walks in
unweighted congestion games cannot improve even when restricting to load
balancing games.

###  4.1 Preliminary Definitions and Technical Lemmas

Similarly as in Section 3, we start by providing some definitions and two
technical lemmas (Lemmas 5 and 6), which are variants of Lemmas 1 and 2, but
applied to unweighted games. We omit the proofs of such lemmas, since they can
be obtained by using the same proof arguments as in Lemmas 1 and 2, with the
only difference that the weights are unitary and the congestions are integers.
For completeness, we give a sketch of the proofs in the appendix.

Given $x\geq 1$, $k\in\mathbb{Z}_{\geq 0}$, $o\in\mathbb{N}$, and a latency
function $f$, let

$\beta_{\sf U}({\sf
EM},k,o,f):=\begin{cases}-kf(k)+(1+\epsilon)of(k+1)&\text{if }{\sf EM}={\sf
PoA}_{\epsilon},\\\ -\sum_{h=1}^{k}f(h)+(1+\epsilon)of(k+1)&\text{if }{\sf
EM}={\sf CR}_{\epsilon}^{s},\\\
-kf(k)+(1+\epsilon)((k+1)f(k+1)-kf(k))&\text{if }{\sf EM}={\sf
CR}_{\epsilon}^{c}.\end{cases}$ (14)

Given ${\sf EM}\in\\{{\sf PoA}_{\epsilon},{\sf CR}^{s}_{\epsilon},{\sf
CR}^{c}_{\epsilon}\\}$, let

$\gamma_{\sf U}({\sf EM},x,k,o,f):=\frac{kf(k)+x\cdot\beta_{\sf U}({\sf
EM},k,o,f)}{of(o)};$ (15)

furthermore, given a class of unweighted congestion games $\mathcal{G}$, let

$\gamma_{\sf U}({\sf EM},\mathcal{G}):=\inf_{x\geq
1}\sup_{f\in\mathcal{C}(\mathcal{G}),k\in\mathbb{Z}_{\geq
0},o\in\mathbb{N}}\gamma_{\sf U}({\sf EM},x,k,o,f).$ (16)

###### Lemma 5

Let $\mathcal{G}$ be a class of unweighted congestion games. For any ${\sf
EM}\in\\{{\sf PoA}_{\epsilon},{\sf CR}^{s}_{\epsilon}\\}$, we have that ${\sf
EM}(\mathcal{G})\leq\gamma_{\sf U}({\sf EM},\mathcal{G})$. This fact holds for
${\sf EM}={\sf CR}^{c}_{\epsilon}$ if the latency functions of
$\mathcal{C}(\mathcal{G})$ are semi-convex.

###### Lemma 6

Let $\mathcal{G}$ be a class of unweighted congestion games. For each
$M<\gamma_{\sf U}({\sf EM},\mathcal{G})$, with ${\sf EM}\in\\{{\sf
PoA}_{\epsilon},{\sf CR}^{s}_{\epsilon}\\}$, one of the following cases holds:

  * $\bullet$

Case 1: there exist a latency function $f\in\mathcal{C}(\mathcal{G})$ and two
integers $k,o>0$ such that $M<\frac{kf(k)}{of(o)}$ and $\beta_{\sf U}({\sf
EM},k,o,f)\geq 0$.

  * $\bullet$

Case 2: there exist two latency functions
$f_{1},f_{2}\in\mathcal{C}(\mathcal{G})$ and four integers $k_{1}>0,k_{2}\geq
0,o_{1}>0,o_{2}>0$ such that
$M<\frac{\alpha_{1}k_{1}f_{1}(k_{1})+\alpha_{2}k_{2}f_{2}(k_{2})}{\alpha_{1}o_{1}f_{1}(o_{1})+\alpha_{2}o_{2}f_{2}(o_{2})}$,
where $\alpha_{1}:=\beta_{\sf U}({\sf EM},k_{2},o_{2},f_{2})>0$ and
$\alpha_{2}:=-\beta_{\sf U}({\sf EM},k_{1},o_{1},f_{1})>0$.

This fact holds for ${\sf EM}={\sf CR}_{\epsilon}^{c}$ if the latency
functions of $\mathcal{C}(\mathcal{G})$ are semi-convex.

###### Remark 4

By exploiting Lemma 5, given an arbitrary choice of the input parameters
$k,o,f$ (resp. $k_{1},k_{2},o_{1},o_{2},f_{1},f_{2}$) such that $\beta_{\sf
U}({\sf EM},k,o,f)\geq 0$ (resp. $\beta_{\sf U}({\sf EM},k_{2},o_{2},f_{2})>0$
and $-\beta_{\sf U}({\sf EM},k_{1},o_{1},f_{1})>0$), we have that
$\frac{kf(k)}{of(o)}$ (resp.
$\frac{\alpha_{1}k_{1}f_{1}(k_{1})+\alpha_{2}k_{2}f_{2}(k_{2})}{\alpha_{1}o_{1}f_{1}(o_{1})+\alpha_{2}o_{2}f_{2}(o_{2})}$)
is a lower bound on $\gamma_{\sf U}({\sf EM},\mathcal{G})$; furthermore, by
definition of $\gamma_{\sf U}({\sf EM},\mathcal{G})$, we have that
$\sup_{f\in\mathcal{C}(\mathcal{G}),k\in\mathbb{Z}_{\geq
0},o\in\mathbb{N}}\gamma_{\sf U}({\sf EM},x,k,o,f)$ is an upper bound on
$\gamma_{\sf U}({\sf EM},\mathcal{G})$ for any $x\geq 1$. Thus, if such upper
bound (for a suitable choice of $x$) is equal to the former lower bound (for a
suitable choice of the input parameters), we necessarily have that they are
both equal to $\gamma_{\sf U}({\sf EM},\mathcal{G})$.

###  4.2 Main Theorems

In the following theorem, we prove that, under mild assumptions on the latency
functions, no improvements are possible for $\epsilon$-approximate pure Nash
equilibria when restricting to load balancing games.

###### Theorem 4.1

Let $\mathcal{C}$ be a class of latency functions that is closed under
ordinate scaling. Then $\gamma_{\sf U}({\sf PoA}_{\epsilon},{\sf
U}(\mathcal{C}))={\sf PoA}_{\epsilon}({\sf U}(\mathcal{C}))={\sf
PoA}_{\epsilon}({\sf ULB}(\mathcal{C}))$.

###### Proof

Fix $M<\gamma_{\sf U}({\sf PoA}_{\epsilon},{\sf U}(\mathcal{C}))$. Similarly
as in Theorem 3.1, we will show that there exists a load balancing instance
${\sf LB}\in{\sf ULB}(\mathcal{C})$ such that ${\sf PoA}_{\epsilon}({\sf
LB})>M$. By Lemma 5, this will imply that $M<{\sf PoA}_{\epsilon}({\sf
LB})\leq{\sf PoA}_{\epsilon}({\sf U}(\mathcal{C}))\leq\gamma_{\sf U}({\sf
PoA}_{\epsilon},{\sf U}(\mathcal{C}))$, and by the arbitrariness of
$M<\gamma_{\sf U}({\sf PoA}_{\epsilon},{\sf U}(\mathcal{C}))$, this fact will
show the claim.

Suppose that Case 2 of Lemma 6 is verified, and let $k_{1},k_{2},o_{1},o_{2},$
$f_{1},f_{2},\alpha_{1},\alpha_{2}$ be defined as in Lemma 6. As in Theorem
3.1, we resort to a load balancing graph representation. Consider a load
balancing game defined by a multi-partite directed graph ${\sf
LB}_{s}(k_{1},k_{2},o_{1},o_{2},f_{1},f_{2})$ as load balancing graph,
organized in $2s$ levels, numbered from $1$ to $2s$, and defined as follows.
For each $i\in[s]$ (resp. $i\in[2s]_{s+1}$), there are
$o_{1}^{s-i}k_{1}^{i-1}o_{2}^{s}$ (resp. $o_{2}^{2s-i}k_{2}^{i-s-1}k_{1}^{s}$)
nodes/resources. Edges can only connect nodes of consecutive levels, except
for nodes at level $2s$, each of which has $k_{2}$ self-loops. The out-degree
of each node at level $i\in[s]$ (resp. $i\in[2s]_{s+1}$) is $k_{1}$ (resp.
$k_{2}$), and the in-degree of each node at level $i\in[s]_{2}$ (resp.
$i\in[2s]_{s+1}$ without considering self-loops) is $o_{1}$ (resp. $o_{2}$);
observe that this configuration can be realized since the total number of
nodes at level $i\in[s-1]$ (resp. $i=s$, resp. $i\in[2s-1]_{s+1}$) multiplied
by $k_{1}$ (resp. $k_{1}$, resp. $k_{2}$) is equal to the number of nodes at
level $i+1$ multiplied by $o_{1}$ (resp. $o_{2}$, resp. $o_{2}$). See the
example depicted in Figure 7. For $i,j\in[2]$, define
$\theta_{i,j}:=\frac{f_{i}(k_{i})}{(1+\epsilon)f_{j}(k_{j}+1)}$ and
$\theta_{i}:=\theta_{i,i}$. Each resource at level $i$ has latency function
$g_{i}(x):=\theta_{1}^{i-1}f_{1}\left(x\right)$ if $i\in[s]$, and
$g_{i}(x):=\theta_{1}^{s-1}\theta_{1,2}\theta_{2}^{i-s-1}f_{2}\left(x\right)$
otherwise. We assume that each player can only choose among her first and her
second strategy, and let $\bm{\sigma}_{s}$ and $\bm{\sigma}^{*}_{s}$ be the
strategy profiles in which all players select their first and second strategy,
respectively. Analogously to Theorem 3.1, one can show that $\bm{\sigma}_{s}$
is an $\epsilon$-approximate pure Nash equilibrium.

In the remainder of the proof, with the aim at estimating the approximate
price of anarchy of ${\sf LB}_{s}(k_{1},k_{2},o_{1},o_{2},f_{1},f_{2})$, we
compare the social value of the $\epsilon$-pure Nash equilibrium
$\bm{\sigma}_{s}$, with that of the strategy profile $\bm{\sigma}^{*}_{s}$ in
which all players select their second strategy. By exploiting similar
arguments as in Theorem 3.1, we get

$\displaystyle{\sf SUM}(\bm{\sigma}_{s})$
$\displaystyle=\sum_{i=1}^{s}\left(o_{1}^{s-i}k_{1}^{i-1}o_{2}^{s}\right)k_{1}g_{i}(k_{1})+\sum_{i=s+1}^{2s}\left(o_{2}^{2s-i}k_{2}^{i-s-1}k_{1}^{s}\right)k_{2}g_{i}(k_{2})$
$\displaystyle=\sum_{i=1}^{s}\left(o_{1}^{s-i}k_{1}^{i-1}o_{2}^{s}\right)k_{1}\theta_{1}^{i-1}f_{1}(k_{1})$
$\displaystyle\ \ \ \ \ \ \
+\sum_{i=s+1}^{2s}\left(o_{2}^{2s-i}k_{2}^{i-s-1}k_{1}^{s}\right)k_{2}\theta_{1}^{s-1}\theta_{1,2}\theta_{2}^{i-s-1}f_{2}(k_{2})$
$\displaystyle=\sum_{i=1}^{s}o_{1}^{s-1}o_{2}^{s}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{i-1}k_{1}f_{1}(k_{1})$
$\displaystyle\ \ \ \ \ \ \
+\sum_{i=s+1}^{2s}o_{1}^{s-1}o_{2}^{s}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{s-1}\frac{k_{1}\theta_{1,2}}{o_{2}}\left(\frac{k_{2}\theta_{2}}{o_{2}}\right)^{i-s-1}k_{2}f_{2}(k_{2})$
$\displaystyle=o_{1}^{s-1}o_{2}^{s}\sum_{i=0}^{s-1}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{i}k_{1}f_{1}(k_{1})$
$\displaystyle\ \ \ \ \ \ \
+o_{1}^{s-1}o_{2}^{s}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{s-1}\frac{k_{1}\theta_{1,2}}{o_{2}}\sum_{i=0}^{s-1}\left(\frac{k_{2}\theta_{2}}{o_{2}}\right)^{i}k_{2}f_{2}(k_{2})$
(17)
$\displaystyle=o_{1}^{s-1}o_{2}^{s}\left(\frac{\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{s}-1}{\frac{k_{1}\theta_{1}}{o_{1}}-1}\right)k_{1}f_{1}(k_{1})$
$\displaystyle\ \ \ \ \ \ \
+o_{1}^{s-1}o_{2}^{s}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{s-1}\frac{k_{1}\theta_{1,2}}{o_{2}}\left(\frac{1-\left(\frac{k_{2}\theta_{2}}{o_{2}}\right)^{s}}{1-\frac{k_{2}\theta_{2}}{o_{2}}}\right)k_{2}f_{2}(k_{2}),$
(18)

and

$\displaystyle{\sf SUM}(\bm{\sigma}^{*}_{s})$
$\displaystyle=\sum_{i=2}^{s}\left(o_{1}^{s-i}k_{1}^{i-1}o_{2}^{s}\right)o_{1}g_{i}(o_{1})+\sum_{i=s+1}^{2s-1}\left(o_{2}^{2s-i}k_{2}^{i-s-1}k_{1}^{s}\right)o_{2}g_{i}(o_{2})$
$\displaystyle\ \ \ \ \ \ \
+\left(k_{2}^{s-1}k_{1}^{s}\right)(k_{2}+o_{e})g_{2s}(k_{2}+o_{2})$
$\displaystyle=\sum_{i=2}^{s}\left(o_{1}^{s-i}k_{1}^{i-1}o_{2}^{s}\right)o_{1}\theta_{1}^{i-1}f_{1}(o_{1})$
$\displaystyle\ \ \ \ \ \ \
+\sum_{i=s+1}^{2s-1}\left(o_{2}^{2s-i}k_{2}^{i-s-1}k_{1}^{s}\right)o_{2}\theta_{1}^{s-1}\theta_{1,2}\theta_{2}^{i-s-1}f_{2}(o_{2})$
$\displaystyle\ \ \ \ \ \ \
+\left(k_{2}^{s-1}k_{1}^{s}\right)(k_{2}+o_{e})\theta_{1}^{s-1}\theta_{1,2}\theta_{2}^{s-1}f_{2}(k_{2}+o_{2})$
(19)
$\displaystyle=o_{1}^{s-1}o_{2}^{s}\sum_{i=1}^{s}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{i-1}o_{1}f_{1}(o_{1})-\overbrace{\left(o_{1}^{s-1}o_{2}^{s}\right)o_{1}f_{1}(o_{1})}^{[<]_{s}\left(o_{1}^{s-1}o_{2}^{s}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{s-1}\right)}$
$\displaystyle\ \ \ \ \ \ \
+o_{1}^{s-1}o_{2}^{s}\sum_{i=s+1}^{2s-1}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{s-1}\frac{k_{1}\theta_{1,2}}{o_{2}}\left(\frac{k_{2}\theta_{2}}{o_{2}}\right)^{i-s-1}o_{2}f_{2}(o_{2})$
$\displaystyle\ \ \ \ \ \ \
+\overbrace{o_{1}^{s-1}o_{2}^{s}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{s-1}\frac{k_{1}\theta_{1,2}}{o_{2}}\left(\frac{k_{2}\theta_{2}}{o_{2}}\right)^{s-1}(k_{2}+o_{e})f_{2}(k_{2}+o_{e})}^{[<]_{s}\left(o_{1}^{s-1}o_{2}^{s}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{s-1}\right)}$
$\displaystyle=o_{1}^{s-1}o_{2}^{s}\sum_{i=0}^{s-1}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{i}o_{1}f_{1}(o_{1})$
$\displaystyle\ \ \ \ \ \ \
+o_{1}^{s-1}o_{2}^{s}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{s-1}\frac{k_{1}\theta_{1,2}}{o_{2}}\sum_{i=0}^{s-1}\left(\frac{k_{2}\theta_{2}}{o_{2}}\right)^{i}o_{2}f_{2}(o_{2})$
$\displaystyle\ \ \ \ \ \ \
+[<]_{s}\left(o_{1}^{s-1}o_{2}^{s}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{s-1}\right)$
(20)
$\displaystyle=o_{1}^{s-1}o_{2}^{s}\left(\frac{\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{s}-1}{\frac{k_{1}\theta_{1}}{o_{1}}-1}\right)o_{1}f_{1}(o_{1})$
$\displaystyle\ \ \ \ \ \ \
+o_{1}^{s-1}o_{2}^{s}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{s-1}\frac{k_{1}\theta_{1,2}}{o_{2}}\left(\frac{1-\left(\frac{k_{2}\theta_{2}}{o_{2}}\right)^{s}}{1-\frac{k_{2}\theta_{2}}{o_{2}}}\right)o_{2}f_{2}(o_{2})$
$\displaystyle\ \ \ \ \ \ \
+[<]_{s}\left(o_{1}^{s-1}o_{2}^{s}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{s-1}\right).$
(21)

By using equalities (18) and (21), and the fact that
$\frac{k_{1}\theta_{1}}{o_{1}}>1$ and $\frac{k_{2}\theta_{2}}{o_{2}}<1$
(since, by Lemma 6, we have $\alpha_{1},\alpha_{2}>0$) we get

$\displaystyle\sup_{s\in\mathbb{N}}{\sf PoA}_{\epsilon}({\sf
LB}_{s}(k_{1},k_{2},o_{1},o_{2},f_{1},f_{2}))$
$\displaystyle\geq\lim_{s\rightarrow\infty}\frac{{\sf
SUM}(\bm{\sigma}_{s})}{{\sf SUM}(\bm{\sigma}^{*}_{s})}$
$\displaystyle=\lim_{s\rightarrow\infty}\frac{{\sf
SUM}(\bm{\sigma}_{s})\left(o_{1}^{s-1}o_{2}^{s}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{s-1}\right)}{{\sf
SUM}(\bm{\sigma}^{*}_{s})\left(o_{1}^{s-1}o_{2}^{s}\left(\frac{k_{1}\theta_{1}}{o_{1}}\right)^{s-1}\right)}$
$\displaystyle=\frac{\left(\frac{\frac{k_{1}\theta_{1}}{o_{1}}}{\frac{k_{1}\theta_{1}}{o_{1}}-1}\right)k_{1}f_{1}(k_{1})+\frac{k_{1}\theta_{1,2}}{o_{2}}\left(\frac{1}{1-\frac{k_{2}\theta_{2}}{o_{2}}}\right)k_{2}f_{2}(k_{2})}{\left(\frac{\frac{k_{1}\theta_{1}}{o_{1}}}{{\frac{k_{1}\theta_{1}}{o_{1}}-1}}\right)o_{1}f_{1}(o_{1})+\frac{k_{1}\theta_{1,2}}{o_{2}}\left(\frac{1}{1-\frac{k_{2}\theta_{2}}{o_{2}}}\right)o_{2}f_{2}(o_{2})}$
$\displaystyle=\frac{\left(\frac{k_{1}f_{1}(k_{1})}{\alpha_{2}}\right)k_{1}f_{1}(k_{1})+\left(\frac{k_{1}f_{1}(k_{1})}{\alpha_{1}}\right)k_{2}f_{2}(k_{2})}{\left(\frac{k_{1}f_{1}(k_{1})}{\alpha_{2}}\right)o_{1}f_{1}(o_{1})+\left(\frac{k_{1}f_{1}(k_{1})}{\alpha_{1}}\right)o_{2}f_{2}(o_{2})}$
$\displaystyle=\frac{\alpha_{1}k_{1}f_{1}(k_{1})+\alpha_{2}k_{2}f_{2}(k_{2})}{\alpha_{1}o_{1}f_{1}(o_{1})+\alpha_{2}o_{2}f_{2}(o_{2})}$
$\displaystyle>M$ (22)

where (22) comes from Lemma 6. Then, there exists an integer $s$ such that
${\sf PoA}_{\epsilon}({\sf LB}_{s}(k_{1},k_{2},o_{1},o_{2},f_{1},f_{2}))>M$,
and this shows the claim.

Finally, suppose that Case 1 of Lemma 6 holds and let $k,o,f$ be the
parameters defined for that case. Consider the load balancing graph ${\sf
LB}_{s}(k,k,o,o,f,f)$. Observe that, analogously to the previous cases,
$\bm{\sigma}_{s}$ is an $\epsilon$-approximate pure Nash equilibrium. Indeed,
it suffices considering the previous proofs with $k_{1}=k_{2}=k$. To evaluate
${\sf SUM}(\bm{\sigma}_{s})$, observe that all the equalities up to (17) hold.
Therefore, by continuing from (17) we get

${\sf SUM}(\bm{\sigma}_{s})=o_{1}^{s-1}o_{2}^{s}2skf(k)$

if $\beta_{\sf U}({\sf PoA}_{\epsilon},k,o,f)=0$ (as in such case we get
$\frac{k_{1}\theta_{1}}{o_{1}}=\frac{k_{2}\theta_{2}}{o_{2}}=1$), and

${\sf
SUM}(\bm{\sigma}_{s})=o_{1}^{s-1}o_{2}^{s}\left(\frac{1-\left(\frac{kf(k)}{(1+\epsilon)of(k+1)}\right)^{2s}}{1-\frac{kf(k)}{(1+\epsilon)of(k+1)}}\right)kf(k)$

if $\beta_{\sf U}({\sf PoA}_{\epsilon},k,o,f)>0$ (as in such case we get
$\frac{k_{1}\theta_{1}}{o_{1}}=\frac{k_{2}\theta_{2}}{o_{2}}<1$). To evaluate
${\sf SUM}(\bm{\sigma}^{*}_{s})$, observe that all the equalities up to (19)
hold. Therefore, by continuing from (19), we get

${\sf SUM}(\bm{\sigma}^{*}_{s})=o_{1}^{s-1}o_{2}^{s}(2sof(o)+[\leq]_{s}(1))$

if $\beta_{\sf U}({\sf PoA}_{\epsilon},k,o,f)=0$, and

${\sf
SUM}(\bm{\sigma}^{*}_{s})=o_{1}^{s-1}o_{2}^{s}\left(\left(\frac{1-\left(\frac{kf(k)}{(1+\epsilon)of(k+1)}\right)^{2s}}{1-\frac{kf(k)}{(1+\epsilon)of(k+1)}}\right)of(o)-of(o)+[<]_{s}(1)\right)$

if $\beta_{\sf U}({\sf PoA}_{\epsilon},k,o,f)>0.$ Then:

$\sup_{s\in\mathbb{N}}{\sf PoA}_{\epsilon}({\sf
LB}_{s}(k,k,o,o,f,f))\geq\lim_{s\rightarrow\infty}\frac{{\sf
SUM}(\bm{\sigma}_{s})}{{\sf
SUM}(\bm{\sigma}^{*}_{s})}\geq\frac{kf(k)}{of(o)}>M,$

where the last inequality follows from Lemma 6. Thus, there exists an integer
$s$ such that ${\sf PoA}_{\epsilon}({\sf
LB}_{s}(k_{1},k_{2},o_{1},o_{2},f_{1},f_{2}))>M$, and this shows the claim if
the first Case of Lemma 6 holds. ∎

Figure 7: The load balancing graph described in the proof of Theorems 4.1 and
4.2, with $s=3$, $k_{1}=3$, $o_{1}=2$, $k_{2}=4$ and $o_{2}=1$. We also
describe the partitioning and labeling structures used in the proof of Theorem
4.2.

Then, we prove a similar limitation for approximate one-round walks.

###### Theorem 4.2

Let $\mathcal{C}$ be a class of latency functions that is closed under
ordinate scaling. Then $\gamma_{\sf U}({\sf CR}^{s}_{\epsilon},{\sf
U}(\mathcal{C}))={\sf CR}^{s}_{\epsilon}({\sf U}(\mathcal{C}))={\sf
CR}^{s}_{\epsilon}({\sf ULB}(\mathcal{C}))$. If the functions of $\mathcal{C}$
are semi-convex, we have that $\gamma_{\sf U}({\sf CR}^{c}_{\epsilon},{\sf
U}(\mathcal{C}))={\sf CR}^{c}_{\epsilon}({\sf U}(\mathcal{C}))={\sf
CR}^{c}_{\epsilon}({\sf ULB}(\mathcal{C}))$.

###### Proof

Fix $M<\gamma_{\sf U}({\sf EM},{\sf U}(\mathcal{C}))$, where ${\sf
EM}\in\\{{\sf CR}^{s}_{\epsilon},{\sf CR}^{c}_{\epsilon}\\}$ is the considered
efficiency metric. As in Theorem 4.1, by Lemma 5, it is sufficient showing
that there exists a load balancing game ${\sf LB}\in{\sf ULB}(\mathcal{C})$
such that its competitive ratio is at least $M$.

Let us start with the case of selfish players. Let
$k_{1},k_{2},o_{1},o_{2},f_{1},f_{2},\alpha_{1},\alpha_{2}$ be the parameters
defined as in Lemma 6, for which we remove index $j\in[2]$ if the first case
of Lemma 6 is verified. Define $j(i)=1$ if $i\in[s]$ and $j(i)=2$ otherwise.
We extend the load balancing graph ${\sf
LB}(k_{1},k_{2},o_{1},o_{2},f_{1},f_{2})$ used in the proof of Theorem 4.1
according to the following recursive procedure.

  * $\bullet$

Base Case: partition the resources of the first level (resp. second level) of
the load balancing graph in $o_{j(2)}$ (resp. $k_{j(1)}$) groups of equal
size, and add edges from the first level to the second one in such a way that
each resource in the first level has exactly $k_{j(1)}$ outgoing edges, each
ending in a different group of the second level, and each resource in the
second level has exactly $o_{j(2)}$ incoming edges, each coming from a
different group of the first level; number the groups of the second level from
$1$ to $k_{j(1)}$ and label each resource with the number associated to the
group it belongs to. For an illustrating example see Figure 7, where resources
belonging to different groups at level $1$ are represented with different
colors, resources belonging to different groups at level $2$ belong to
different rectangles and they are labeled with the number of the rectangle
they belong to.

  * $\bullet$

Inductive Case: as inductive hypothesis, suppose that resources at level
$i\in[2s-1]$ have been partitioned into $m(i)$ groups of equal size and
labeled with values from $1$ to $k_{j(i-1)}$, where each label is assigned to
$m(i)/k_{j(i-1)}$ distinct groups, and that all the edges from level $i-1$ to
level $i$ have been added. Partition resources at level $i+1$ in a temporary
partition of $m(i)$ groups of equal size, and consider a bijective
correspondence between groups at level $i$ and groups at level $i+1$ (in
Figure 7, groups at levels $2$ and $3$ which are in bijective correspondence
have been depicted in the same dashed square). Partition each group at level
$i$ into $o_{j(i+1)}$ subgroups of equal size, and the corresponding group at
level $i+1$ (according to the bijective correspondence considered above) into
$k_{j(i)}$ subgroups of equal size, and add edges from each group at level $i$
to the corresponding group at level $i+1$ in the same way as described in the
base case, i.e., each resource in the group at level $i$ has exactly
$k_{j(i)}$ outgoing edges, each ending in a different subgroup of the
corresponding group at level $i+1$, and each resource in this group has
exactly $o_{j(i+1)}$ incoming edges, each coming from a different subgroup of
the considered group at level $i$. For each group at level $i+1$, number its
subgroups with values from $1$ to $k_{j(i)}$ and label each resource with the
number associated to the subgroup which the considered resource belongs to.
The final partitioning of nodes at level $i+1$ is made of all the
$m(i+1):=m(i)k_{j(i)}$ subgroups considered above, these groups have equal
size, they are labeled with values from $1$ to $k_{j(i)}$, each label is
assigned to $m(i+1)/k_{j(i-1)}=m(i)$ distinct groups, and all the edges from
level $i$ to level $i+1$ have been added. Thus the inductive step is well-
defined and allows to construct the structure of the load balancing graphs,
starting from the lowest levels, to the higher ones.

For instance, Figure 7 depicts the recursive procedure used to construct a
load balancing graph. In Figure 7, each arbitrary dashed square includes a
group at level $2$ and a group at level $3$ which are in bijective
correspondence. Analogously to the base case, resources belonging to different
subgroups of the considered group at level $2$ (resp. at level $3$) are
represented with different colors (resp. belong to different squares and are
labeled with the number of the square they belong to).

Again, all the players can select their first and second strategies, only. Let
$i(v)$ be the level of resource $v$ and $h(v)\in[k_{j(i(v))}]$ be the label
assigned to resource $v$ by the previous recursive procedure.

For $i,j\in[2]$ and $h\in k_{i}$, define
$\theta_{i,j}(h):=\frac{f_{i}(h)}{(1+\epsilon)f_{j}(k_{j}+1)}$ and
$\theta_{i}(h):=\theta_{i,i}(h)$. Resource $v$ has latency function
$g_{v}(x):=f_{1}(x)$ if $i(v)=1$,
$g_{v}(x):=\underbrace{\theta_{1}(h(v))A_{u}}_{A_{v}}f_{1}(x)$ if
$i(v)\in[s]_{2}$,
$g_{v}(x):=\underbrace{\theta_{1,2}(h(v))A_{u}}_{A_{v}}f_{2}(x)$ if
$i(v)=s+1$, and $g_{v}(x):=\underbrace{\theta_{2}(h(v))A_{u}}_{A_{v}}f_{2}(x)$
otherwise, where $(u,v)$ is an arbitrary incoming edge of $v$ and $A_{v}$ is
recursively defined on the basis of $A_{u}$ by setting $A_{v}=1$ for $i(v)=1$.
By using the recursive structure of the load balancing graph, one can prove
that $A_{u}=A_{u^{\prime}}$ if $(u,v)$ and $(u^{\prime},v)$ are both edges of
the load balancing graph, so that the definition of $A_{v}$ (and then $g_{v}$)
is independent of the particular incoming edge of $v$.

Consider the online process $\bm{\tau}_{s}$ in which: (i) players enter the
game in non-increasing order of level (with respect to their first strategy)
and, within the same level, players are processed in non-decreasing order of
position defined by labelling function $h$; (ii) each player selects her first
strategy. Similarly as in Lemma 4, one can show that $\bm{\tau}_{s}$ is an
$\epsilon$-approximate one-round walk generated by selfish players. To show
this, let $z$ be an arbitrary player entering the game according to
$\bm{\tau}_{s}$, and let $u$ and $v$ be her first and second strategy,
respectively. One can show that, when $z$ is entering the game, there are
$h(v)-1$ players already assigned to $u$, and $k_{j(i(v))}$ players assigned
to $v$; thus, similarly as in Lemma 4, and by using the recursive definition
of the latency functions, one can show that the individual cost of player $z$
is exactly $(1+\epsilon)$ times the cost resulting from a deviation in favour
of her second strategy.

Now, let ${\bm{\sigma}}$ and ${\bm{\sigma}}^{*}_{s}$ be the strategy profile
generated by the $\epsilon$-approximate one-round walk $\bm{\tau}_{s}$ and the
optimal strategy profile, respectively. In the remainder of the proof, with
the aim of estimating the competitive ratio of ${\sf
LB}_{s,n}(k_{1},k_{2},o_{1},o_{2},f_{1},f_{2})$, we compare the social value
of the strategy profile ${\bm{\sigma}}_{s}$ with that of
${\bm{\sigma}}^{*}_{s}$. Let ${\sf SUM}_{i}({\bm{\sigma}_{s}})$ denote the
total latency of resources under strategy profile ${\bm{\sigma}}$. By using
similar approaches as in Theorem 3.2 (since the metric is the competitive
ratio) and Theorem 4.1 (since the game is unweighted), one can prove that

$\displaystyle{\sf SUM}_{i}({\bm{\sigma}_{s}})$ $\displaystyle=\sum_{v\text{
in level }i}k_{v}(\bm{\sigma}_{s})g_{v}\left(k_{v}(\bm{\sigma}_{s})\right)$
$\displaystyle=\left(o_{1}^{s-i}o_{2}^{s}\right)\sum_{(h_{1},h_{2},\ldots,h_{i-1})\in[k_{1}]^{i-1}}\left(\prod_{t=1}^{i-1}\theta_{1}(h_{t})\right)k_{1}f_{1}(k_{1})$
$\displaystyle=\left(o_{1}^{s-1}o_{2}^{s}\right)\left(\frac{\sum_{h=1}^{k_{1}}\theta_{1}(h)}{o_{1}}\right)^{i-1}k_{1}f_{1}(k_{1})$
$\displaystyle=\left(o_{1}^{s-1}o_{2}^{s}\right)\left(\frac{\sum_{h=1}^{k_{1}}f_{1}(h)}{o_{1}f_{1}(k_{1}+1)}\right)^{i-1}k_{1}f_{1}(k_{1})$

for any $i\in[s]$, and

$\displaystyle{\sf SUM}_{i}({\bm{\sigma}_{s}})$
$\displaystyle=\left(o_{1}^{s-1}o_{2}^{s}\right)\left(\frac{\sum_{h=1}^{k_{1}}\theta_{1}(h)}{o_{1}}\right)^{s-1}\left(\frac{\sum_{h=1}^{k_{1}}\theta_{1,2}(h)}{o_{2}}\right)$
$\displaystyle\ \ \ \ \ \ \
\left(\frac{\sum_{h=1}^{k_{2}}\theta_{2}(h)}{o_{2}}\right)^{i-1-s}k_{2}f_{2}(k_{2})$
$\displaystyle=\left(o_{1}^{s-1}o_{2}^{s}\right)\left(\frac{\sum_{h=1}^{k_{1}}f_{1}(h)}{o_{1}f_{1}(k_{1}+1)}\right)^{s-1}\left(\frac{\sum_{h=1}^{k_{1}}f_{1}(h)}{o_{2}f_{2}(k_{2}+2)}\right)$
$\displaystyle\ \ \ \ \ \ \
\left(\frac{\sum_{h=1}^{k_{2}}f_{2}(h)}{o_{2}f_{2}(k_{2}+2)}\right)^{i-1-s}k_{2}f_{2}(k_{2})$

Thus, we can compute ${\sf SUM}({\bm{\sigma}_{s}})=\sum_{i=1}^{2s}{\sf
SUM}_{i}({\bm{\sigma}_{s}})$ and, analogously, we can compute ${\sf
SUM}({\bm{\sigma}}_{s}^{*})$. At this point, by using the same proof arguments
of Theorems 3.2 and 4.1, we can prove that

$\displaystyle\lim_{s\in\mathbb{N}}{\sf CR}_{\epsilon}^{s}({\sf
LB}_{s,n}(k_{1},k_{2},o_{1},o_{2},f_{1},f_{2}))$
$\displaystyle\geq\lim_{s\rightarrow\infty}\frac{{\sf
SUM}({\bm{\sigma}_{s}})}{{\sf SUM}({\bm{\sigma}_{s}}^{*})}$
$\displaystyle\geq\frac{\alpha_{1}k_{1}f_{1}(k_{1})+\alpha_{2}k_{2}f_{2}(k_{2})}{\alpha_{1}o_{1}f_{1}(o_{1})+\alpha_{2}o_{2}f_{2}(o_{2})}$
$\displaystyle>M,$ (23)

where the last inequality comes from Lemma 6, and this shows the claim in the
case of selfish players.

For the case of cooperative players, it suffices considering the same load
balancing graph with
$\theta_{i,j}(h)=\frac{h_{i}f_{i}\left(h_{i}\right)-(h_{i}-1)f_{i}(h_{i}-1)}{(1+\epsilon)((k_{j}+1)f_{j}(k_{j}+1)-k_{j}f_{j}(k_{j}))}$.
Let ${\bm{\sigma}}_{s}$ and ${\bm{\sigma}}^{*}_{s}$ be the strategy profiles
in which each player chooses her first and second strategy, respectively. By
using the same arguments as in the previous proof, one can show that
inequality (23) holds for the case of cooperative players, too.∎

###### Remark 5

Fix a metric ${\sf EM}\in\\{{\sf PoA}_{\epsilon},{\sf CR}^{s}_{\epsilon},{\sf
CR}^{c}_{\epsilon}\\}$, a class of latency functions $\mathcal{C}$, and let
$(k_{1},k_{2},o_{1},o_{2},f_{1},f_{2})$ (resp. $(k,o,f)$) be a tuple such that
values $\alpha_{1},\alpha_{2}$ considered in Case 2 of Lemma 6 are positive
(resp. such that the inequality of Case 1 corresponding to the considered
metric EM is satisfied, i.e., $\beta_{\sf U}({\sf EM},k,o,f)\geq 0$). As in
Remark 3, by inspecting the proofs of Theorems 4.1 and 4.2, we can construct a
load balancing instance parametrized by the above tuple whose performance is
at least
$\frac{\alpha_{1}k_{1}f_{1}(k_{1})+\alpha_{2}k_{2}f_{2}(k_{2})}{\alpha_{1}o_{1}f_{1}(o_{1})+\alpha_{2}o_{2}f_{2}(o_{2})}$
(resp. $\frac{kf(k)}{of(o)}$). Thus, in case we are not able to quantify the
exact value of $\gamma_{\sf U}({\sf EM},{\sf U}(\mathcal{C}))$, we can still
find a choice of the above parameters that leads to good (and possibly tight)
lower bounds; the tightness can be shown by resorting to the characterization
provided in Remark 4.

###  4.3 Application to Polynomial Latency Functions

Let $\gamma_{\sf U}({\sf EM},{\sf U}(\mathcal{P}(d)))$ with ${\sf
EM}\in\\{{\sf PoA}_{\epsilon},{\sf CR}^{s}_{\epsilon},{\sf
CR}^{c}_{\epsilon}\\}$ be the quantity defined at the beginning of the
section, where $\mathcal{P}(d)$ is the class of polynomial latency functions
of maximum degree $d$. By Lemma 5, $\gamma_{\sf U}({\sf EM},{\sf
U}(\mathcal{P}(d)))$ constitutes an upper bound on the efficiency metrics
${\sf EM}\in\\{{\sf PoA}_{\epsilon},{\sf CR}^{s}_{\epsilon},{\sf
CR}^{c}_{\epsilon}\\}$ for unweighted congestion games and load balancing
games with polynomial latency functions of maximum degree $d$.

$\gamma_{\sf U}({\sf PoA}_{\epsilon},{\sf U}(\mathcal{P}(d)))$ has been
already evaluated in [3, 23]. $\gamma_{\sf U}({\sf CR}^{c}_{\epsilon},{\sf
U}(\mathcal{P}(d)))$ has been evaluated in [20] for exact pure Nash equilibria
and affine functions;888As in Subsection 3.3, the value of $\gamma_{\sf
U}({\sf EM},{\sf U}(\mathcal{P}(d)))$ can be easily derived from equivalent
results appearing in the cited works, thus the analysis leading to such
quantification has been omitted. by using similar arguments as in [3], one can
easily compute the exact value of $\gamma_{\sf U}({\sf CR}^{c}_{\epsilon},{\sf
U}(\mathcal{P}(d)))$ for any $\epsilon>0$.

The above values of ${\sf EM}\in\\{{\sf PoA}_{\epsilon},{\sf
CR}^{c}_{\epsilon}\\}$ can be also represented by resorting to the
characterization provided by Remark 4. In particular, let $k$ be the unique
real solution of equation $\beta_{\sf U}({\sf EM},k,1,f)=0$, where $f$ is the
monomial function defined as $f(t)=t^{d}$. If $k$ is not integer we have that
$\gamma_{\sf U}({\sf EM},{\sf U}(\mathcal{P}(d)))$ is equal to
$\frac{\alpha_{1}k_{1}f_{1}(k_{1})+\alpha_{2}k_{2}f_{2}(k_{2})}{\alpha_{1}o_{1}f_{1}(o_{1})+\alpha_{2}o_{2}f_{2}(o_{2})}$,
where $(k_{1},k_{2},o_{1},o_{2}):=(\lfloor k\rfloor+1,\lfloor k\rfloor,1,1)$,
$f_{1}:=f_{2}:=f$, and $\alpha_{1}$ and $\alpha_{2}$ are defined as in Case 2
of Lemma 6 with respect to parameters $k_{1},k_{2},o_{1},o_{2},f_{1},f_{2}$.
Instead, if $k$ is integer, we have that $\gamma_{\sf U}({\sf EM},{\sf
U}(\mathcal{P}(d)))$ is equal to $\frac{kf(k)}{f(1)}$, i.e., Case 1 of Lemma 6
is satisfied by tuple $(k,1,f)$.

Since the class of polynomial latency functions $\mathcal{P}(d)$ satisfies the
hypothesis of Theorem 4.1 and 4.2, as a corollary we have that the values of
$\gamma_{\sf U}({\sf EM},{\sf U}(\mathcal{P}(d)))$ considered above are tight
upper bounds on the performance of load balancing games, thus matching the
performance of general congestion games; this generalizes/improves some
results of [20, 32], in which the considered lower bounds hold for load
balancing games under some restrictions (e.g., $d=1$ for the competitive
ratio, and $\epsilon=0$ for the price of anarchy).

Regarding the $\epsilon$-approximate one-round walks generated by selfish
players, we have that the exact value of $\gamma_{\sf U}({\sf
CR}^{s}_{\epsilon},{\sf U}(\mathcal{P}(d)))$ has been provided in [8] for
$d\in[3]$ and $\epsilon=0$, thus, by Theorem 4.2, such value is tight even for
load balancing games; even for the case of affine latencies (i.e., $d=1$),
this fact also improves a result of [9], in which a tight lower bound has been
provided for general congestion games only, and the case of singleton
strategies was left open.

For more general polynomial latency functions with maximum degree $d>3$ and
for any $\epsilon\geq 0$, an upper bound on $\gamma_{\sf U}({\sf
CR}^{s}_{\epsilon},{\sf U}(\mathcal{P}(d)))$ can be trivially obtained by
reusing the upper bound shown in Subsection 3.3, that holds for more general
weighted games; for exact one-round walks, a better upper bound has been
recently provided in [38]. By Remark 5, we can get good lower bounds on the
performance of $\epsilon$-approximate one-round walks, having a similar
representation as in the cases of ${\sf EM}\in\\{{\sf PoA}_{\epsilon},{\sf
CR}^{c}_{\epsilon}\\}$. In particular, let $k$ be the highest non-negative
integer such that $\beta_{\sf U}({\sf CR}_{\epsilon}^{s},k,1,f)\geq 0$, where
$f$ is the monomial function defined as $f(t)=t^{d}$; if $\beta_{\sf U}({\sf
CR}_{\epsilon}^{s},k,1,f)>0$ (resp. $\beta_{\sf U}({\sf
CR}_{\epsilon}^{s},k,1,f)=0$), we can consider the lower bounding instances
defined in Theorem 4.2, parametrized by $(k+1,k,1,1,f,f)$ (resp.
$(k,k,1,1,f,f)$); by Remark 5, the performance of such load balancing
instances is equal to
$\frac{\alpha_{1}k_{1}f_{1}(k_{1})+\alpha_{2}k_{2}f_{2}(k_{2})}{\alpha_{1}o_{1}f_{1}(o_{1})+\alpha_{2}o_{2}f_{2}(o_{2})}$
(resp. $\frac{kf(k)}{of(o)}$), where $\alpha_{1}$ and $\alpha$ are defined as
in Lemma 6. Such load balancing instances improve the lower bounds obtained in
[13], where it is showed that the $\epsilon$-approximate competitive ratio of
general unweighted congestion games is at least equal to the $(d+1)$-th
Geometric polynomial evaluated in $(1+\epsilon)$; furthermore, for $d>3$, we
conjecture that the performance of the obtained load balancing instances match
the exact value of $\gamma_{\sf U}({\sf CR}^{s}_{\epsilon},{\sf
U}(\mathcal{P}(d)))$, and in such case, they would match the competitive ratio
of general congestion games with polynomial latency functions of maximum
degree $d$. See Table 8 for some numerical comparisons.

$d$ |  ${\sf PoA}_{0}({\sf U}(\mathcal{P}(d)))$ [3, 32] | ${\sf CR}_{0}^{s}({\sf U}(\mathcal{P}(d)))$ | ${\sf CR}_{0}^{c}({\sf U}(\mathcal{P}(d)))$
---|---|---|---
1 | 2.5 [22, 4, 20] | 4.236 [24, 9] | 5.66 [20]
2 | 9.583 | 37.58 [8] | 55.46
3 | 41.54 | 527.3 [8] | 755.2
4 | 267.6 | 9,387 (L.B.) | 13,170
5 | 1,514 | 201,401 (L.B.) | 289,648
6 | 12,345 | 5,276,150 (L.B.) | 7,174,495
7 | 98,734 | 151,192,413 (L.B.) | 220,349,064
8 | 802,603 | 5,287,749,084 (L.B.) | 7,022,463,077
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$
$\infty$ | $(\Theta(d/\log(d)))^{d+1}$ | $(\Theta(d))^{d+1}$ | $(\Theta(d))^{d+1}$
Figure 8: The competitive ratio of exact one-round walks generated by
cooperative players in unweighted load balancing games with polynomial latency
functions of maximum degree $d$. For $d\geq 2$, our findings provide tight
lower bounds on the competitive ratio involving cooperative players, holding
even for load balancing games. For $d\in[3]$, we show that the existing upper
bounds on the competitive ratio involving selfish players are tight even for
load balancing games; instead, for $d>3$, we provide almost tight lower bounds
(see Table 6 for the upper bounds). We observe that, when considering the
solution concept of one-round walk, the selfish behaviour induce better
outcomes than the cooperative one (in contrast to what happens for weighted
games).

##  5 The Case of Identical Resources

###  5.1 The Approximate Price of Anarchy of Weighted Games

In this section, we characterize the approximate price of anarchy of weighted
symmetric load balancing games with identical resources having semi-convex
latency functions. Given $\epsilon\geq 0$, $\lambda\in(0,1)$, a latency
function $f$, and $x>0$, let

$\displaystyle[x]_{\epsilon,f}:=\inf\\{t\geq
0:f(x)\leq(1+\epsilon)f(x/2+t)\\},$
$\displaystyle\gamma_{\epsilon,f}(x,\lambda):=\frac{\lambda
xf(x)+(1-\lambda)[x]_{\epsilon,f}f([x]_{\epsilon,f})}{(\lambda
x+(1-\lambda)[x]_{\epsilon,f})f(\lambda x+(1-\lambda)[x]_{\epsilon,f})}.$

In Theorem 5.1 and 5.2, we provide respectively upper and lower bounds on the
$\epsilon$-approximate price of anarchy (which are tight, under mild
assumptions), and we generalize the results obtained in [40, 30], holding for
the restricted case of affine and monomial latency functions with
$\epsilon=0$. The high-level idea of the proofs, which are given in the
appendix, is showing that the price of anarchy of class ${\sf WSLB}(\\{f\\})$,
where $f$ is a semi-convex latency function, is given by instances verifying
the following conditions: (i) the number $m$ of resources and the total weight
$W$ of players tends to infinite, in such a way that the ratio $W/m$ tends to
$\lambda x+(1-\lambda)[x]_{\epsilon,f}$, for some $x>0$ and $\lambda\in(0,1)$;
(ii) there is an optimal strategy profile in which all the resource
congestions are equal (i.e., equal to $W/m$); (iii) at the worst-case
equilibrium there are two groups $A$ and $B$ of resources, such that $|A|/m$
and $|B|/m$ tend respectively to $\lambda$ and $1-\lambda$, as $m$ tends to
infinite; (iv) at the worst-case equilibrium, each resource of group $A$ has
congestion $x>0$, and each resource of group $B$ has congestion
$[x]_{\epsilon,f}\leq x$, that can be equivalently defined as the minimum
possible congestion guaranteeing the equilibrium conditions (while keeping the
congestions in $A$ equal to $x$). According to the above properties, the
equilibrium and the optimal cost increase (with respect to $m$) as $\lambda
mxf(x)+(1-\lambda)m[x]_{\epsilon,f}f([x]_{\epsilon,f})$ and $(\lambda
x+(1-\lambda)[x]_{\epsilon,f})m$, respectively. Thus, we get that the
approximate price of anarchy is equal to the the highest value of
$\frac{\lambda xf(x)+(1-\lambda)[x]_{\epsilon,f}f([x]_{\epsilon,f})}{(\lambda
x+(1-\lambda)[x]_{\epsilon,f})f(\lambda x+(1-\lambda)[x]_{\epsilon,f})}$, over
$x>0$ and $\lambda\in(0,1)$.

###### Theorem 5.1

Let $f:{\mathbb{R}}_{\geq 0}\rightarrow{\mathbb{R}}_{\geq 0}$ be a semi-convex
latency function, and let $\epsilon\geq 0$. We have that

${\sf PoA}_{\epsilon}({\sf
WSLB}(\\{f\\}))\leq\sup_{x>0}\max_{\lambda\in(0,1)}\gamma_{\epsilon,f}(x,\lambda).$
(24)

######  Theorem 5.2 (Lower Bound)

For any $\epsilon\geq 0$ and for any $x\geq 0$, let
$\lambda^{*}(x)\in\arg\max_{\lambda\in(0,1)}\gamma_{\epsilon,f}(x,\lambda)$.
If (i) $\lambda^{*}(x)\leq\frac{1}{2}$, and (ii) either $\epsilon=0$, or
$\lambda^{*}(x)x+(1-\lambda^{*}(x))[x]_{\epsilon,f}-x/2\geq 0$, for any $x>0$,
then

${\sf PoA}_{\epsilon}({\sf
WSLB}(\\{f\\}))\geq\sup_{x>0}\max_{\lambda\in(0,1)}\gamma_{\epsilon,f}(x,\lambda).$
(25)

By exploiting (25), one can obtain tight bounds on the price of anarchy of
weighted symmetric load balancing games with identical resources having
polynomial latency functions. The same tight bounds have been given in [40,
30] for monomial latency functions. In the following corollary of Theorems 5.1
and 5.2 we show that the same bounds hold for more general polynomial latency
functions.

###### Corollary 1

Let $\mathcal{P}(d)$ be the class of polynomial latency functions of maximum
degree $d$. Then, ${\sf PoA}_{0}({\sf
WSLB}(\mathcal{P}(d)))=\frac{d^{d}(2^{d+1}-1)^{d+1}}{2^{d}(d+1)^{d+1}(2^{d}-1)^{d}}\in\Theta\left(\frac{2^{d}}{d}\right)$.

In Table 9, we show a comparison between the cases of general and identical
resources with respect to the price of anarchy for games with polynomial
latency functions.

$d$ | Identical | General | $d$ | Identical | General
---|---|---|---|---|---
1 | 1.125 | 2.618 | 6 | 7.544 | 14,099
2 | 1.412 | 9.909 | 7 | 12.866 | 118,926
3 | 1.946 | 47.82 | 8 | 22.478 | 1,101,126
4 | 2.895 | 277 | $\vdots$ | $\vdots$ | $\vdots$
5 | 4.571 | 1,858 | $\infty$ | $\Theta\left(\frac{2^{d}}{d}\right)$ | $\left(\Theta\left(\frac{d}{\log d}\right)\right)^{d+1}$
Figure 9: The price of anarchy of weighted symmetric load balancing games with
polynomial latency functions of maximum degree $d$: a comparison between the
cases of identical and general resources.

As in Corollary 1, the general upper bound provided in Theorem 5.1 is well-
suited to derive (possibly non-tight) upper bounds on the
$\epsilon$-approximate price of anarchy of symmetric polynomial load balancing
games with identical resources for any $\epsilon>0$.

###  5.2 Lower Bounds for Exact One-Round Walks

The following construction gives a class of lower bounds for exact one-round
walks generated by selfish/cooperative players in unweighted load balancing
games with identical resources having latency function $f$. Fix
$n\in\mathbb{N}$ and a sequence of integers $1=o_{1}\leq o_{2}\leq\ldots\leq
o_{n}$. Let $E=E_{0}\supset E_{1}\supset E_{2}\supset\ldots\supset
E_{n}\supset E_{n+1}=\emptyset$ be a sequence of sets of resources such that
$(|E_{i-1}|-|E_{i}|)o_{i}=|E_{i}|$ (observe that such a sequence exists). For
any $i\in[n]$, we have $|E_{i}|$ players of type $i$ whose set of strategies
is $E_{i-1}$. Suppose that players enter the game in non-decreasing order with
respect to their type. One can easily prove that the strategy profile
${\bm{\sigma}}$ in which each player of type $i$ selects a different resource
$e\in E_{i}$ is a possible outcome for an exact one-round walk generated by
selfish/cooperative players. Consider the strategy profile in which, for any
resource $e\in E_{i-1}\setminus E_{i}$, there are exactly $o_{i}$ players of
type $i$ selecting $e$. We get

${\sf CR}^{s}_{0}(\\{f\\})\geq\frac{{\sf SUM}({\bm{\sigma}})}{{\sf
SUM}({\bm{\sigma}}^{*})}=\frac{\sum_{i=1}^{n}(|E_{i}|-|E_{i+1}|)if(i)}{\sum_{i=1}^{n}(|E_{i-1}|-|E_{i}|)o_{i}f(o_{i})}.$
(26)

For linear latency functions, by using $n=10^{13}$ and
$o_{i}=\left\lfloor\frac{44411}{100000}i+1+\left\lfloor\frac{\sqrt{i}}{7}\right\rfloor\right\rfloor$
in (26), we get a lower bound of at least $4.0009$ which improves the
currently known lower bound of 4 given in [20]. We conjecture that a tight
class of lower bounding instances for linear and more general polynomial
latency functions is given by the union of all the instances described above,
over all values of $n\in\mathbb{N}$ and all sequences $(o_{i})_{i\in[n]}$.

##  6 Open Problems and Research Directions

We have investigated how the combinatorial structure of the players’ strategy
space impacts on the efficiency of some decentralized solutions in congestion
games by focusing on the simplest possible situation: that of singleton
strategies. All of our negative results clearly carry over to more general
structures, such as in matroid congestion games and in network congestion
games.

Our work leaves two main open problems. The first is to understand whether
better performance are possible for approximate one-round walks in weighted
symmetric load balancing games (we conjecture this is not the case), while the
second is to give upper bounds on the performance of one-round walks in
weighted and unweighted load balancing games with identical resources.
Relatively to further research directions, we believe that the modus-operandi
considered in this work can be efficiently used to find tight lower bounds in
several variants of congestion games or scheduling games, and with respect to
different solution concepts. For instance, after the appearance of the
conference version of this work, similar ideas have been efficiently reused in
[11, 21, 47, 15, 10, 6, 14] to derive tight lower bounds on the efficiency of
some variants of congestion games and load balancing games.

## References

  * [1] Ackermann, H., Röglin, H., Vöcking, B.: On the impact of combinatorial structure on congestion games.  Journal of ACM 55(6) (2008)
  * [2] Ackermann, H., Röglin, H., Vöcking, B.: Pure Nash equilibria in player-specific and weighted congestion games.  Theoretical Computer Science 410(17), 1552–1563 (2009)
  * [3] Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact price of anarchy for polynomial congestion games.  SIAM Journal on Computing 40(5), 1211–1233 (2011)
  * [4] Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow.  SIAM Journal on Computing 42(1), 160–177 (2013)
  * [5] Awerbuch, B., Azar, Y., Grove, E.F., Kao, M.Y., Krishnan, P., Vitter, J.S.: Load balancing in the $l_{p}$ norm.  In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), pp. 383–391 (1995)
  * [6] Benita, F., Bilò, V., Monnot, B., Piliouras, G., Vinci, C.: Data-driven models of selfish routing: Why price of anarchy does depend on network topology.  In: Web and Internet Economics - 16th International Conference, WINE, Proceedings (2020)
  * [7] Bhawalkar, K., Gairing, M., Roughgarden, T.: Weighted congestion games: price of anarchy, universal worst-case examples, and tightness.  ACM Transactions on Economics and Computation 2(4), 1–23 (2014)
  * [8] Bilò, V.: A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games.  Theory of Computing Systems 62(5), 1288–1317 (2018)
  * [9] Bilò, V., Fanelli, A., Flammini, M., Moscardelli, L.: Performances of one-round walks in linear congestion games.  Theory of Computing Systems 49(1), 24–45 (2011)
  * [10] Bilò, V., Monaco, G., Moscardelli, L., Vinci, C.: Nash social welfare in selfish and online load balancing.  In: Web and Internet Economics - 16th International Conference, WINE, Proceedings (2020)
  * [11] Bilò, V., Moscardelli, L., Vinci, C.: Uniform mixed equilibria in network congestion games with link failures.  In: Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP), pp. 146:1–146:14 (2018)
  * [12] Bilò, V., Vinci, C.: On the impact of singleton strategies in congestion games.  In: 25th Annual European Symposium on Algorithms, ESA, pp. 17:1–17:14 (2017)
  * [13] Bilò, V., Vinci, C.: Dynamic taxes for polynomial congestion games.  ACM Transantions on Economics and Computation 7(3), 15:1–15:36 (2019)
  * [14] Bilò, V., Vinci, C.: Congestion games with priority-based scheduling.  In: Algorithmic Game Theory - 13th International Symposium, SAGT 2020, Proceedings, pp. 67–82 (2020)
  * [15] Bilò, V., Vinci, C.: The price of anarchy of affine congestion games with similar strategies.  Theor. Comput. Sci. 806, 641–654 (2020)
  * [16] Caragiannis, I.: Better bounds for online load balancing on unrelated machines.  In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 972–981 (2008)
  * [17] Caragiannis, I.: Efficient coordination mechanisms for unrelated machine scheduling.  Algorithmica 66(3), 512–540 (2013)
  * [18] Caragiannis, I., Fanelli, A., Gravin, N., Skopalik, A.: Efficient computation of approximate pure nash equilibria in congestion games.  In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 532–541 (2011)
  * [19] Caragiannis, I., Fanelli, A., Gravin, N., Skopalik, A.: Approximate pure Nash equilibria in weighted congestion games: existence, efficient computation and structure.  ACM Transactions on Economics and Computation 3(1) (2015)
  * [20] Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight bounds for selfish and greedy load balancing.  Algorithmica 61(3), 606–637 (2011)
  * [21] Caragiannis, I., Gkatzelis, V., Vinci, C.: Coordination mechanisms, cost-sharing, and approximation algorithms for scheduling.  In: Web and Internet Economics - 13th International Conference, WINE, pp. 74–87 (2017)
  * [22] Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games.  In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 67–73 (2005)
  * [23] Christodoulou, G., Koutsoupias, E., Spirakis, P.G.: On the performance of approximate equilibria in congestion games.  Algorithmica 61(1), 116–140 (2011)
  * [24] Christodoulou, G., Mirrokni, V.S., Sidiropoulos, A.: Convergence and approximation in potential games.  Theoretical Computer Science 438, 13–27 (2012)
  * [25] Correa, J., de Jong, J., de Keijzer, B., Uetz, M.: The curse of sequentiality in routing games.  In: Proceedings of the 11th International Conference on Web and Internet Economics (WINE), _LNCS_ , vol. 9470, pp. 258–271 (2015)
  * [26] Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The complexity of pure Nash equilibria.  In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 604–612 (2004)
  * [27] Feldotto, M., Gairing, M., Kotsialou, G., A., S.: Computing approximate pure nash equilibria in shapley value weighted congestion games.  In: Proceedings of the 13th International Conference on Web and Internet Economics (WINE), pp. 191–204 (2017)
  * [28] Fotakis, D.: Stackelberg strategies for atomic congestion games.  Theor. Comp. Sys. 47(1), 218–249 (2010)
  * [29] Fotakis, D., Kontogiannis, S., Spirakis, P.: Selfish unsplittable flows.  Theoretical Computer Science 348, 226–239 (2005)
  * [30] Gairing, M., Lücking, T., Mavronicolas, M., Monien, B.: The price of anarchy for polynomial social cost.  Theoretical Computer Science 369(1–3), 116–135 (2006)
  * [31] Gairing, M., Lücking, T., Mavronicolas, M., Monien, B., Rode, M.: Nash equilibria in discrete routing games with convex latency functions.  J. Comput. Syst. Sci. 74(7), 1199–1225 (2008)
  * [32] Gairing, M., Schoppmann, F.: Total latency in singleton congestion games.  In: Proceedings of the Third International Workshop on Internet and Network Economics (WINE), _LNCS_ , vol. 4858, pp. 381–387 (2007)
  * [33] Giannakopoulos, Y., Noarov, G., Schulz, A.S.: Computing approximate equilibria in weighted congestion games via best-responses.  Mathematics of Operations Research (2021).  To appear
  * [34] Harks, T., Klimm, M.: On the existence of pure Nash equilibria in weighted congestion games.  Mathematics of Operations Research 37(3), 419–436 (2012)
  * [35] de Jong, J., Klimm, M., Uetz, M.: Efficiency of equilibria in uniform matroid congestion games.  In: Proceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT), _LNCS_ , vol. 9928, pp. 105–116 (2016)
  * [36] Kleer, P., Schäfer, G.: Potential function minimizers of combinatorial congestion games: Efficiency and computation.  In: Proceedings of the 2017 ACM Conference on Economics and Computation (EC), pp. 223–240 (2017)
  * [37] Kleer, P., Schäfer, G.: Computation and efficiency of potential function minimizers of combinatorial congestion games.  Math. Program. 190(1), 523–560 (2021)
  * [38] Klimm, M., Schmand, D., Tönnis, A.: The online best reply algorithm for resource allocation problems.  In: Algorithmic Game Theory - 12th International Symposium, SAGT, Proceedings, pp. 200–215 (2019)