The Price of Stability of Weighted Congestion Games
George Christodoulou Martin Gairing Yiannis Giannakopoulos Paul G. Spirakis


[
    Constantinos Kardaras
    December 30, 2023
=========================



We give exponential lower bounds on the Price of Stability (PoS) of weighted
congestion games with polynomial cost functions. In particular, for any positive
integer d we construct rather simple games with cost functions of degree at most
d which have a PoS of at least (Φ_d)^d+1, where Φ_d∼ d/ln
d is the unique positive root of equation x^d+1=(x+1)^d. This almost closes the
huge gap between (d) and Φ_d^d+1. Our bound extends also to
network congestion games. We further show that the PoS remains exponential even for
singleton games. More generally, we provide a lower bound of
((1+1/α)^d/d) on the PoS of α-approximate Nash equilibria for
singleton games. All our lower bounds hold for mixed and correlated equilibria as
well.

On the positive side, we give a general upper bound on the PoS of
α-approximate Nash equilibria, which is sensitive to the range W of the
player weights and the approximation parameter α. We do this by explicitly
constructing a novel approximate potential function, based on Faulhaber's formula,
that generalizes Rosenthal's potential in a continuous, analytic way. From the
general theorem, we deduce two interesting corollaries. First, we derive the
existence of an approximate pure Nash equilibrium with PoS at most (d+3)/2; the
equilibrium's approximation parameter ranges from (1) to d+1 in a
smooth way with respect to W. Secondly, we show that for unweighted congestion
games, the PoS of α-approximate Nash equilibria is at most (d+1)/α.




  congestion games, price of stability, Nash equilibrium, approximate equilibrium, potential games




68Q99, 91A10, 91A43, 90B20, 90B18






§ INTRODUCTION


In the last 20 years, a central strand of research within Algorithmic
Game Theory has focused on understanding and quantifying the
inefficiency of equilibria compared to centralized, optimal
solutions. There are two standard concepts that measure this
inefficiency. The Price of Anarchy (PoA) <cit.> which takes the
worst-case perspective, compares the worst-case equilibrium with the
system optimum. It is a very robust measure of performance. On the
other hand, the Price of Stability (PoS) <cit.>, which is
also the focus of this work, takes an optimistic perspective, and uses
the best-case equilibrium for this comparison. The PoS is an appropriate
concept to analyse the ideal solution that we would like our protocols
to produce.

The initial set of problems that arose from the Price of Anarchy
theory have now been resolved. The most rich and well-studied among
these models are, arguably, the atomic and non-atomic variants of
congestion games (see <cit.> for a
detailed discussion). This class of games is very descriptive and
captures a large variety of scenarios where users compete for
resources, most prominently routing games. The seminal work of
Roughgarden and Tardos <cit.> gave the answer for the
non-atomic variant, where each player controls a negligible amount of
traffic.  <cit.> resolved the Price of Anarchy for atomic
congestion games with affine latencies, generalized by
<cit.> to polynomials; this led to the development of
Roughgarden's Smoothness Framework <cit.> which extended the
bounds to general cost functions, but also distilled and formulated
previous ideas to bound the Price of Anarchy in an elegant, unified
framework. At the computational complexity front, we know that even for simple congestion
games, finding a (pure) Nash equilibrium is a PLS-complete problem <cit.>.

Allowing the players to have different loads, gives rise to the class
of weighted congestion games <cit.>; this is a natural and very
important generalization of congestion games, with numerous
applications in routing and scheduling. Unfortunately though, an
immediate dichotomy between weighted and unweighted congestion games
occurs: the former may not even have pure Nash equilibria <cit.>; as a matter of fact, it is a strongly NP-hard problem to even determine if that is the case <cit.>.
Moreover, in such games
there does not, in general, exist a potential function <cit.>,
which is the main tool for proving equilibrium existence in the
unweighted case.

As a result, a sharp contrast with respect to our understanding of the
two aforementioned inefficiency notions arises.  The Price of Anarchy
has been studied in depth and general techniques for providing tight
bounds are known.  Moreover, the asymptotic behaviour of weighted and
unweighted congestion games with respect to the Price of Anarchy is
identical; it is Θ(d/log d)^d for both classes when
latencies are polynomials of degree at most d <cit.>.

The situation for the Price of Stability though, is completely different. For
unweighted games we have a good understanding[Much work has been also done
on the PoS for network design games, which is though not so closely related
to ours; in such games the cost of using an edge is split equally among players, and
thus cost functions are decreasing, as opposed to our model of congestion games with
nondecreasing latencies. This problem was first studied by <cit.> who
showed a tight bound of H_n, the harmonic number of the number of players n, for
directed networks. Finding tight bounds on undirected networks is still a
long-standing open problem (see, e.g., <cit.>). Recently,
<cit.> (asymptotically) resolved the question for broadcast networks. For
the weighted variant of this problem, <cit.> showed a lower bound of
(log W/loglog W), where W is the sum of the players' weights, while
<cit.> an upper bound of O(log W/α) for α-approximate
equilibria (the latter is similar in spirit to our results in
<ref>). See <cit.> and references therein for
a thorough discussion of those results.] and the values are much lower than the
Price of Anarchy values, and also tight; approximately 1.577 for affine
functions <cit.>, and Θ(d) <cit.>
for polynomials. For weighted games though there is a huge gap; the current state of
the art lower bound is (d) and the upper bound is (d/ln d)^d.

These previous results are summarized at the left of <ref>.

The main focus of this work is precisely to deal with this lack of
understanding, and to determine the Price of Stability of weighted
congestion games.

What makes this problem challenging is that the only general known technique for
showing upper bounds for the Price of Stability is the potential method, which is
applicable only to potential games. In a nutshell, the idea of this method is to use
the global minimizer of Rosenthal's potential <cit.> as an
equilibrium refinement. This equilibrium is also a pure Nash equilibrium and can
serve as an upper bound of the Price of Stability.  Interestingly, it turns out
that, for several classes of potential games, this technique actually provides the
tight answer (see for example <cit.>). However, as already mentioned above, unlike their unweighted
counterparts, weighted congestion games are not potential games;[For the
special case of weighted congestion games with linear latency functions, a potential
does exist <cit.> and this was used by <cit.> to provide a
PoS upper bound of 2.] so, a completely fresh approach is required.

One way to override the aforementioned limitations of non-existence of pure Nash
equilibria, but also their computational hardness, is to consider approximate
equilibria. In this direction, <cit.> have shown that
(d+1)-approximate pure Nash equilibria always exist in weighted congestion games
with polynomial latencies of maximum degree d, while, in the negative side, there
exist games that do not have 1.153-approximate pure Nash equilibria.  Notice here,
that these results do not take into account computational complexity considerations;
if we insist in polynomial-time algorithms for actually finding those equilibria,
then the currently best approximation parameter becomes d^O(d)
<cit.>.



 §.§ Our Results


We provide lower and upper bounds on the Price of Stability for the
class of weighted congestion games with polynomial latencies
with nonnegative coefficients. We consider both exact and approximate
equilibria.




Our lower bounds are summarized at <ref>.



  
Lower Bound for Weighted Congestion Games

In our main result in <ref>, we resolve a
long-standing open problem by providing almost tight bounds
for the Price of Stability of weighted congestion games with
polynomial latency functions. We construct an instance having a Price
of Stability of (Φ_d)^d+1, where d is the maximum
degree of the latencies and Φ_d∼d/ln d is the unique
positive solution of equation (x+1)^d=x^d+1.

This bound almost closes the previously huge gap between (d) and
Φ_d^d+1 for the PoS of weighted congestion games. The previously best lower
and upper bounds were rather trivial: the lower bound corresponds to the PoS results
of <cit.> for the unweighted case (and thus, it is also a valid
lower bound for the general weighted case as well) and the upper bound comes from
the Price of Anarchy results of <cit.> (PoA, by definition, upper-bounds
PoS). It is important to make clear here that our lower bound still leaves an open
gap for future work: the constant within the base of (Φ_d) in
<ref> produces a lower bound of (1/2Φ_d)^d+1,
which is formally a factor of 2^d+1 away from the Φ_d^d+1 PoA upper
bound.

Although as mentioned before, weighted congestion
games do not always possess pure equilibria, our lower bound
construction involves a unique equilibrium occurring by
iteratively eliminating strongly dominated strategies. As a result,
this lower bound holds not only for pure, but mixed and correlated
equilibria as well.



  
Singleton Games Next we switch to the class of singleton
congestion games, where a pure strategy for each player is a single resource. This class is very well-studied as, on one hand,
it abstracts scheduling environments, and on the other, it has very
attractive equilibrium properties; unlike general weighted congestion
games, there exists an (ordinal) lexicographic potential <cit.>, thus
implying the existence of pure Nash equilibria. It is important
to note that the tight lower bounds for the Price of Anarchy of
general weighted congestion games hold also for the class of
singleton games <cit.>.

Even for this special class, we show in
<ref> an exponential lower bound of
(2^d/d). The previous best lower and upper bounds were the
same as those of the general case, namely (d) and Φ_d^d+1,
respectively.
As a matter of fact, this new lower bound comes as a corollary of a
more general result that we show in <ref>,
that extends to approximate equilibria and gives a lower bound of
((1+1/α)^d/d) on the PoS of α-approximate
equilibria, for any (multiplicative) approximation parameter
α∈[1,d).

Setting α=1 we recover the special case of exact
equilibria and the aforementioned exponential lower bound on the
standard, exact notion of the PoS.

Notice here that, as we show in <ref>, the optimal solution (which, in general, is not an equilibrium) itself constitutes a (d+1)-approximate equilibrium with a (trivially) optimal PoS of 1.



  
Positive Results for Approximate Equilibria

In light of the above results, in <ref>, we
turn our attention to identifying environments with more structure or
flexibility with respect to the underlying solution concept, for which
we can hope for improved quality of equilibria. Both our lower bound
constructions discussed above
use players' weights that form a
geometric sequence. In particular the ratio W of the largest over the
smallest weight is equal to w^n (for some w>1),
which grows very large as the number of players n→∞. On the other hand, for games
where the players have equal weights, i.e. W=1, we know that the PoS is at most
d+1. It is therefore natural to ask how the performance of the good
equilibria captured by the notion of PoS varies with respect to W. In <ref>, we are able to give a general upper bound for α-approximate
equilibria which is sensitive to this parameter W and to α.
This general theorem has two immediate, interesting corollaries.


Firstly (<ref>), by allowing the ratio W to range in [1,∞), we derive the existence of an
α-approximate pure Nash equilibrium with PoS at most (d+3)/2; the equilibrium's approximation parameter α ranges from (1) to d+1 in a smooth way with respect to W.
This is
of particular importance in settings where player weights are not very
far away from each other (that is, W is small).

Secondly (<ref>), by setting W=1 and allowing
α to range up to d+1, we get an upper bound of d+1/α for the
α-approximate PoS of unweighted congestion games which, to the best of
our knowledge, was not known before, degrading gracefully from d+1 (which is the
actual PoS of exact equilibria in the unweighted case <cit.>)
down to the optimal value of 1 if we allow (d+1)-approximate equilibria (which
in fact can be achieved by the optimum solution itself; see <ref>).




  
Our Techniques

An advantage of our main lower bound (<ref>) is the simplicity of the underlying
construction, as well as its straightforward adaptation to network games (see
<ref>)). However, fine-tuning the parameters of the game
(player weights and latency functions), to ensure uniqueness of the
equilibrium at the “bad” instance, was a technically involved task.

This was in part due to
the fact that, in order to guarantee uniqueness (via iteratively
dominant strategies), each player interacts with a window of μ
other players. This μ depends on d in a delicate way (see <ref>); it has
to be an integer but, at the same time, needs also to balance nicely with the algebraic properties of
Φ_d.

Moreover we needed to provide deeper insights on the asymptotic, analytic behaviour
of Φ_d, and to explore some new algebraic characteristics of Φ_d (see,
e.g., <ref>). It is important to keep in mind that
asymptotically Φ_d∼d/ln d (see (<ref>)). The fact that
Φ_d=(d/ln d) was already known by the work
of <cit.>; here we provide a more refined characterization of Φ_d's
growth, using the Lambert-W function (see (<ref>)).

In order to derive our upper bounds, we need to define a novel approximate potential
  function <cit.>.

First, in <ref>, we identify clear algebraic
sufficient conditions for the existence of approximate equilibria with good
social-cost guarantees, and then explicitly define (see
(<ref>) and (<ref>) in the proof of
<ref>) a function that satisfies them. This continuous
function, which is defined in the entire space of positive reals, essentially
generalizes that of Rosenthal's in a smooth way: by setting W=α=1, we recover
exactly the first significant terms of the well known Rosenthal
potential <cit.> polynomial, with which one can demonstrate the
usual PoS results for the unweighted case (see, e.g. <cit.>). The simple,
analytic way in which this function is defined, is the very reason why we can handle
both the approximation parameter α of the equilibrium and the ratio W of
the weights in a smooth manner while at the same time providing good PoS guarantees.

It is important to stress that, by
the purely analytical way in which our approximate potential function
is defined, in principle it can also incorporate more general cost functions than
polynomials; so, we believe that this technique may be of independent
interest. We point towards that direction in <ref>.




§ MODEL AND NOTATION

Let  denote the set of real numbers, _≥ 0=[0,∞) and _>0=(0,∞).



  
Weighted Congestion Games
A weighted congestion game
consists of a finite, nonempty set of players N and resources (or facilities) E.

Each player i∈ N has a weight w_i∈_>0 and a strategy set
S_i⊆ 2^E. Associated with each resource e∈ E is a cost (or
latency) function c_e: _>0_≥ 0. In this paper we
mainly focus on polynomial cost functions with maximum degree d≥ 0 and
nonnegative coefficients; that is, every cost function is of the form
c_e(x)=∑_j=0^d a_e,j· x^j, with a_e,j≥ 0 for all j. In the
following, whenever we refer to polynomial cost functions we mean cost functions of
this particular form.

A pure strategy profile is a choice of strategies s= (s_1, s_2,...,
s_n)∈S=S_1×⋯×S_n by the players. We use the standard
game-theoretic notation s_-i=(s_1,…, s_i-1,
s_i+1,… s_n), S_-i=S_1×⋯× S_i-1×
S_i+1×⋯× S_n, such that s=(s_i,s_-i). Given a
pure strategy profile s, we define the load x_e(s) of
resource e∈ E as the total weight of players that use resource e on s,
i.e., x_e(s)=∑_i∈ N: e∈ s_i w_i. The cost player i is
defined by C_i(s)=∑_e∈ s_i c_e(x_e(s)).

A singleton weighted congestion game is a special form of congestion games
where the strategies of all players consist only of single resources; that is, for
all players i∈ N, s_i=1 for all s_i∈ S_i. In a weighted
network congestion games the resources E are given as the edge set of some
directed graph G=(V,E), and each player i∈ N has a source o_i∈ V and
destination t_i∈ V node; then, the strategy set S_i of each player is
implicitly given as the edge sets of all directed o_i→ t_i paths in G.



  
Nash Equilibria A pure strategy profile s is a pure Nash
equilibrium if and only if for every player i∈ N and for all s'_i∈S_i,
we have C_i(s)≤ C_i(s'_i,s_-i). Similarly a strategy profile is
an α-approximate pure Nash equilibrium, for α≥ 1, if
C_i(s)≤α· C_i(s'_i,s_-i) for all players i∈ N
and s'_i∈ S_i. As discussed in the introduction, weighted congestion games do
not always admit pure Nash equilibria. However, by Nash's theorem they have mixed
Nash equilibria. A tuple σ=( σ_1, ⋯, σ_N) of
independent probability distributions over players' strategy sets is a mixed
Nash equilibrium if

    _s∼σ[C_i(s)] ≤_s_-i∼σ_-i[C_i(s_i',s_-i )]
 holds for every i∈ N and s_i'
∈ S_i. Here σ_-i is a product distribution of all σ_j's with
j≠ i, and s_-i denotes a strategy profile drawn from this
distribution. We use G to denote the set of all mixed Nash equilibria of
a game G.



  
Social Cost and Price of Stability
Fix a weighted congestion game G. The social cost of a pure strategy
profile s is the weighted sum of the players' costs

    (s)=∑_i∈ Nw_i · C_i(s) = ∑_e∈ E
    x_e(s) · c_e(x_e(s)).


Denote by (G)=min_s∈ S(s) the optimum social
cost over all strategy profiles s∈S.

Then, the Price of Stability (PoS) of G is the social cost of the best-case
Nash equilibrium over the optimum social cost: 
    (G) =
    min_σ∈G_s∼σ[(s)]/(G).
 The Price of Stability of
α-approximate Nash equilibria is defined accordingly. The PoS for a class
𝒢 of games is the worst (i.e., largest) PoS among all games in the class,
that is, (𝒢)=sup_G∈𝒢(G). For example, our focus
in this paper is determining the Price of Stability for the class 𝒢 of
weighted congestion games with polynomial cost functions.

For brevity, we will sometimes abuse our formal terminology and refer to the “PoS
of s” for a specific (approximate) equilibrium s of a game G
(see, e.g., <ref>); by that we will mean the approximation
ratio of the social cost of s to the optimum, i.e., C(
s)/(G). Clearly, the PoS of any such equilibrium s is a valid
upper bound to the PoS of the entire game G.

Finally, notice that, by using a straightforward scaling argument, it is without
loss with respect to the PoS metric to analyse games with player weights in
[1,∞); if not, divide all w_i's with min_i w_i and scale cost functions
accordingly.



§ LOWER BOUNDS



In this section, we present our lower bound constructions. In
<ref> we present the general lower bound and then
in <ref> the lower bound for singleton games.




 §.§ General Congestion Games


The next theorem presents our main negative result on the Price of
Stability of weighted congestion games with polynomial latencies of
degree d, that almost matches the Price of Anarchy upper
bound of Φ_d^d+1 from <cit.>. Our result shows a
strong separation for the Price of Stability between weighted and unweighted
congestion games; the Price of Stability of the latter is at most
d+1 <cit.>. This is in sharp contrast to the Price of Anarchy
of these two classes, where the respective bounds are essentially the same.

To state our result, we first introduce some notation. Let Φ_d∼d/ln
d be the unique positive root of equation (x+1)^d=x^d+1 and let β_d be a
parameter with β_d≥ 0.38 for any d,
lim_d→∞β_d=1/2 (formally, β_d is defined in
(<ref>) below, and a plot of its values can be seen in <ref>).


 The Price of Stability of weighted congestion games
with polynomial latency functions of degree at most d≥ 9 is at least
(β_dΦ_d)^d+1.


We must mention here that the restriction of d≥ 9 is without loss: for
polynomial latencies of smaller degrees d≤ 8 we can instead apply the simpler
lower-bound instance for singleton games given in <ref>. To
prove the theorem, we will need the following technical lemma. Its proof can be
found in <ref>.


 For any positive integer d define

    c_d=1/d⌊
    dln(2·Φ_d+1)-ln(Φ_d+1)/lnΦ_d⌋
 and

    β_d = 1-Φ_d^-c_d.

Then

    Φ_d^d+2≤(Φ_d+1/β_d)^d,
 and for all d≥ 9,

    d· c_d ≥ 3,
         0.38≤β_d ≤1/2    and    lim_d→∞β_d=1/2.


Plots of parameters c_d and β_d can be found in <ref>.




Fix some
integer d≥ 9.

Our lower bound instance consists of n+μ players and n+μ+1 facilities, where
μ:= c· d for c=c_d defined as in (<ref>). In particular then,
due to (<ref>) of <ref>, μ≥ 3 is an integer.
You can think of n as a very large integer, since at the end we will take
n→∞. Every player i=1,2,…,n+μ has a weight of w_i = w^i, where w
= 1+1/Φ_d.

It will be useful for subsequent computations to notice that


    w^d=(1+1/Φ_d)^d=(Φ_d+1)^d/Φ_d^d=Φ_d^d+1/Φ_d^d=Φ_d,



    w^d+1=w^d· w=Φ_d(1+1/Φ_d)=Φ_d+1.
 Let us also
define

    α=α(μ)
    :=∑_j=1^μw^-j =1-w^-μ/w-1 =1-(w^d)^-c/w-1
    =1-Φ_d^-c/1+1/Φ_d-1 =Φ_d(1-Φ_d^-c) =βΦ_d,

where β=β_d is defined as in (<ref>). In the following we will
make extensive use of the observation that

    w^-μ=(w^d)^-c=Φ_d^-c=1-β.

Furthermore, for every i≥μ+1

    ∑_j=i-μ^i-1w_j=∑_j=1^μw^i-j=α· w^i
        and    ∑_j=i-μ^iw_j=(α+1)· w^i,
 and


    ∑_ℓ=1^∞ w^-ℓ=1/w-1=1/1+1/Φ_d-1=Φ_d.


The facilities have latency functions


    c_j(t)    = Φ_d(1-β)(α+1)^d,       if  j=1,…,μ, 
     
    c_j(t)    = w^-j(d+1)t^d,       if   j=μ+1,…, μ+n,
     
    c_n+μ+1(t)    = 0.


Every player i has two available strategies, s_i^* and s̃_i. Eventually we will show that the profile s^* corresponds
to the optimal solution, while s̃ corresponds to the
unique Nash equilibrium of the game.  Informally, at the former
the player chooses to stay at her “own” i-th facility, while at
the latter she chooses to deviate and play the μ following
facilities i+1,…,i+μ. However, special care shall be taken for
the boundary cases of the first μ and last μ players, so for
any player i we formally define S_i=s_i^*,s̃_i where
s_i^*=i and

    s̃_i=
    μ+1,…,μ+i,    if   i=1,…,μ,
    i+1,…,i+μ,    if   i=μ+1,…,n,
    i+1,…,n+μ+1,    if   i=n+1,…,n+μ.

These two outcomes, s^* and s̃, are shown in
<ref>.



Notice here that any facility j cannot get a load greater than the sum of the
weights of the previous μ players plus the weight of the j-th player. So, for
and any strategy profile s:

    x_j( s) ≤∑_ℓ=j-μ^j
    w_ℓ=(α+1)w^j
        for all   j≥μ+1



Next we will show that the strategy profile s̃=(s̃_1,…,s̃_n+μ) is the unique Nash equilibrium of our congestion
game. We do that by proving that



  * It is a strongly dominant strategy for any player
  i=1,…,μ to play s̃_i.


  * For any i=μ+1,…,n+μ, given that every player k<i has chosen to play
s̃_k, then it is a strongly dominant strategy for player i to
deviate to s̃_i as well.


For the first condition, fix some player i≤μ and a strategy profile s_-i for the other players and observe that by choosing s̃_i, player i
incurs a cost of at most

    C_i(s̃_i, s_-i)    =∑_j∈s̃_ic_j(x_j(s̃_i))
    ≤∑_ℓ=μ+1^μ+i c_ℓ((α+1) w^ℓ)
       =
    ∑_ℓ=μ+1^μ+i w^-ℓ(d+1)(α+1)^d w^ℓ d = (α+1)^d
    ∑_ℓ=μ+1^μ+i w^-ℓ
       < (α+1)^d · w^-μ·∑_ℓ=1^∞
    w^-ℓ = (α+1)^d · (1-β)·Φ_d
       = C_i(s_i^*, s_-i),
 where in the first inequality we used the bound from
(<ref>).

For the second condition, we will consider the deviations of the remaining players.
Fix now some i=μ+1,…,n and assume a strategy profile s_-i=(s̃_1,…, s̃_i-1, s_i+1,…,s_n+μ) for the remaining
players[For the remaining last μ players i=n+1,…,n+μ the proof
is similar, and as a matter of fact easier, since when these players
deviate to s̃_i they also use the final “dummy” facility n+μ+1 that
has zero cost.]. If player i chooses strategy s_i^* she will experience a cost
of

    C_i(s^*_i, s_-i)=c_i(∑_ℓ=i-μ^i
    w_ℓ)=c_i((α+1)
    w^i)=w^-i(d+1)(α+1)^dw^id=(α+1)^d w^-i.



It remains to show that

    C_i(s̃_i, s_-i) < C_i(s^*_i, s_-i)=(α+1)^d
    w^-i.


The cost C_i(s̃_i, s_-i) is complicated to bound
immediately, for any profile s_-i. Instead, we will resort
to the following claim which characterizes the profile s_-i
where this cost is maximized, as shown
in <ref>.
Its proof can be found in <ref>.



There exists a profile
s'_-i with


  * s_j'=s_j for all j<i and j>i+μ 

  * s_i+μ'=s^*_i+μ 

  * there exists some k∈i+1,…,i+μ-1 such that


    s_j'=s̃_j    for all  
    j∈i+1,…,i+μ-1∖k,

 that dominates s_-i, i.e.
    C_i(s̃_i, s_-i) ≤ C_i(s̃_i, s'_-i).




By use of <ref>, it remains to show


    C_i(s̃_i, s_-i') < (α+1)^d w^-i,
 just for the special case of profiles s' that are described in <ref> and also shown in <ref>.
We do this in <ref>.



Summarizing, we proved that indeed s̃ is the unique Nash
equilibrium of our congestion game. Finally, to conclude with lower-bounding the
Price of Stability, let us compute the social cost on profiles s̃ and
s^*. On s^*, any facility j (except the last one) gets a load
equal to the weight of player j, so

    C( s^*)    =∑_j=1^n+μw_j c_j(w_j)
       =∑_j=1^μw^j
    Φ_d(1-β)(α+1)^d + ∑_j=μ+1^n+μw^jw^-j(d+1)(w^j)^d
       =Φ_d(1-β)(α+1)^d∑_j=1^μ w^j+∑_j=μ+1^μ+n 1
       =Φ_d(1-β)(α+1)^d
    ww^μ-1/w-1+n
       =Φ_d(1-β)(α+1)^d
    (1+1/Φ_d)1/1-β-1/1+1/Φ_d-1+n
       =Φ_d(1-β)(α+1)^d (Φ_d+1)β/1-β +n
       ≤ n+
    Φ_d(Φ_d+1)β(α+1)^d.

On the other hand, at the unique Nash equilibrium s̃
each facility j≥μ+1 receives a load equal to the sum of the weights of the
previous μ players, i.e.

    x_j(s̃)=∑_ℓ=j-μ^j-1 w_ℓ=α w^j

so

    C(s̃)
    ≥∑_j=μ+1^n+μx_j(s̃)c_j(x_j(s̃))
    =∑_j=μ+1^n+μ w^-j(d+1)(α w^j)^d+1
    =α^d+1∑_j=μ+1^μ+n1=α^d+1 n.

By taking n arbitrarily large we get a lower bound on the Price of Stability of

    lim_n→∞C(s̃)/C( s^*) ≥lim_n→∞α^d+1 n/n+Φ_d(Φ_d+1)β(α+1)^d 
    =α^d+1=(βΦ_d)^d+1,

where from <ref> we know that 1/3≤β=1/2-o(1).





  §.§.§ Network Games


Due to the rather simple structure of the players' strategy sets in the lower bound
construction of <ref>, it can be readily extended to network
games as well:


<ref> applies also to network weighted congestion games.




We arrange the resources from the instance in the proof of
<ref> as edges in a graph as depicted in <ref>. In
particular, for all j=μ+1,…,n+μ+1, resource j from
<ref> corresponds to edge (u_j,u_j+1). For the special
case of the first μ resources, for j=1,…,μ, we represent resource j by
the directed edge (u_μ+1,u_j).

Regarding strategies, recall from the instance used in the proof of
<ref> that, for each i=μ,…,n, player i has two
available strategies: resource i or resources i+1,…,i+μ. To
map this to our network instance, we set the source node o_i of player i to be
o_i=u_i+1 and introduce a new destination node t_i connected to the rest of
the graph by zero-latency directed edges (u_i,t_i) and (u_i+μ+1,t_i).
In that way, strategy i of <ref> corresponds to the
path o_i=u_i+1→ u_i→ t_i of our graph, while strategy
i+1,…,i+μ to path o_i=u_i+1→ u_i+2→…→ u_i+μ+1→ t_i. To avoid clutter, these destination nodes t_i and the corresponding
zero-latency edges are not depicted in <ref>. In an analogous way, we can
set the sources and destinations of the remaining first i=1,…,μ-1 and last
i=n+1,…,n+μ+1 players, taking into consideration their specially restricted
strategy sets in the construction of the proof of <ref>.

Summarizing, each player i∈[1,n+μ] has to route its traffic from o_i
to t_i, where 
    o_i=
    
    u_μ+1,    if   i=1,…,μ,
    
    u_i+1,    if   i=μ+1,…,n+μ,

and nodes t_i are connected with zero latency edges as follows:


  * For each i∈[1,n+μ] there is a directed zero cost edge from u_i to t_i.

  * For each i∈[1,n] there is a directed zero cost edge from u_μ+1+i to t_i.

  * For each i∈[n+1,n+μ] there is a directed zero cost edge from u_μ+n+2 to t_i.

Then, by construction, each player i has two available o_i→ t_i paths, which
correspond directly to strategy sets s_i^* and s̃_̃ĩ used in the proof of
<ref>.

There is one issue left to complete our network game construction: we have not yet
set a direction on some of our edges, namely (u_i,u_i+1) for
i=μ+1,…,n+μ+1 which are depicted also as undirected edges in
<ref>. This is due to the fact that, by our construction so far, these
edges can be used in both directions: by player i (left-to-right) or player
i+1 (right-to-left). Thus, to turn our instance to a valid directed
network, we need to replace such edges with a “gadget” that essentially forces
both players, no matter from which direction they enter the edge, to use it in the
same direction and both contribute to its load. This can be achieved by using
the structure depicted in the bottom right corner of <ref>.





 §.§ Singleton Games


In this section we give an exponential lower bound for singleton
weighted congestion games with polynomial latency functions.

The following theorem handles also approximate equilibria and provides
a lower bound on the Price of Stability in a very strong sense; even
if one allows for the best approximate equilibrium with approximation
factor α=o(d/ln d), then its cost is
lower-bounded by ω(poly(d)) times the optimal cost.[ To see
this, just take any upper bound of d+1/cln (d+1) on
α, for a constant c>2. Then, the lower bound in
(<ref>) becomes Ω(d^c-1).]
In other words, in order to achieve polynomial (with respect to d) guarantees on the Price of
Stability, one has to consider (d/ln d)-approximate
equilibria—almost linear in d; this shows that our positive result in
<ref>, of the following
<ref>, is almost tight. This is furthermore
complemented by <ref>, where we show that the socially
optimum profile is a (d+1)-approximate equilibrium (achieving an
optimal Price of Stability of 1).




For any positive integer d and any real α∈ [1,d), the
α-approximate (mixed) Price of Stability of weighted (singleton) congestion
games with polynomial latencies of degree at most d is at least

    1/e(d+1)(1+1/α)^d+1.

In particular, for the special case of α=1, we derive that the Price of Stability of exact equilibria is (2^d/d).



Fix a positive integer d and the desired approximation parameter
α∈[1,d). Also, let γ∈(α,d) be a parameter
arbitrarily close to α.  Our instance consists of n players
with weights w_i=w^i, i=1,2,…,n, where we set

    w=γd+1/d-γ>γ,

the inequality holding due to the fact that d+1>d-γ>0.

At the end of our construction we will take n→∞, so one can
think of n as a very large integer.

There are n+1 facilities with latency
functions

    c_1(t)    = γ w^d(w+1)^d, 
    
    c_j(t)    = (γ w^d)^2-j· t^d,        j=2,…, n,
    
    c_n+1(t)    = γ^1-nw^d(w+1)^d.


Any player i has exactly two strategies, s^*_i={i} and s̃_i={i+1}
i.e., S_i=i,i+1 for all i=1,…,n.  Let s^*,
s̃ be the strategy profiles where every player i plays s_i^*,
s̃_i respectively. These two outcomes, s^* and s̃ are
depicted in <ref>.



One should think of
s^* as the socially optimal profile. We will show that
s̃ is the unique α-approximate Nash
equilibrium of our game. To ensure this, it suffices to require the
following, which corresponds to eliminating all other possible
strictly dominated α-approximate equilibria:




  * It is a strictly α-dominant strategy for player 1 to
  use facility 2, i.e. 
  
    α C_1(s̃_1, s_-i)<
      C_1( s)
 
  for any profile s.

  * For any i=2,…,n, if every player k<i has chosen facility k+1 then it is a strictly  α-dominant strategy for player i to chose facility i+1, i.e.

    α C_i(s̃_1,…,s̃_i-1,s̃_i, s_i+1,…,s_n) < C_i(s̃_1,…,s̃_i-1,s_i,s_i+1,…,s_n)

 for any strategies (s_i,s_i+1,…,s_n)∈ S_i×…× S_n.



For the first condition, since facility 2 can be used by at most
players 1 and 2, and γ>α, it is enough to show that γ
c_2(w_1+w_2)≤ c_1(w_1). Indeed

    γ c_2(w_1+w_2)=γ (γ w^d)^2-2(w+w^2)^d=γ w^d(1+w)^d=c_1(w_1).


Similarly, for the second condition, it suffices to show that γ c_i+1(w_i+w_i+1) ≤ c_i(w_i-1+w_i) for
i=2,…,n-1, and γ c_n+1(w_n)≤
c_n(w_n-1+w_n) for the special case of i=n. This is
because, facility i+1 can be used by at most players i and
i+1, while facility i is already being used by player
i-1. Indeed, for any i=2,…,n-1 we see that:


    γ c_i+1(w_i+w_i+1)    =γ (γ w^d)^2-(i+1)(w^i+w^i+1)^d
    = (γ w^d)^2-i(w^i-1+w^i)^d
       = c_i(w_i-1+w_i),

while for i=n,

    c_n(w_n-1+w_n)    = (γ w^d)^2-n(w^n-1+w^n)^d
       = γ^2-nw^d(2-n)+d(n-1)(w+1)^d
       =γ·γ^1-nw^d(w+1)^d
       =γ c_n+1(w_n).


The social cost at equilibrium s̃ is at least the cost of player n at s̃, that is,

    C(s̃)≥ w_n c_n+1(w_n)=w^n·γ^1-nw^d(1+w)^d=(w/γ)^n γ· w^d(1+w)^d


On the other hand, consider the strategy profile s^* where every player i chooses facility i:

    C( s^*)
        =w_1 c_1(w_1)+∑_i=2^nw_i c_i(w_i)
       = γ w^d+1(1+w)^d+ ∑_i=2^nw^i (γ w^d)^2-i w^id
       =γ w^d+1(1+w)^d+γ^2w^2d∑_i=2^n(w/γ)^i
       =γ w^d+1(1+w)^d+γ^2w^2d·(w/γ)^2(w/γ)^n-1-1/w/γ-1
       ≤γ w^d+1(1+w)^d+γ^2w^2d·(w/γ)^2(w/γ)^n-1/w/γ-1
       = (w/γ)^nγ·[(w/γ)^-n· w^d+1(w+1)^d + w^2d+1/w/γ-1]


Recall now that, from (<ref>), w/γ>1, and thus lim_n→∞(w/γ)^-n=0. So, as the number of players n grows large we get the following lower bound on the Price of Stability:

    lim_n→∞C(s̃)/C( s^*)≥lim_n→∞w^d(1+w)^d/(w/γ)^-n· w^d+1(w+1)^d + w^2d+1/w/γ-1=(w/γ-1)(1+w)^d/w^d+1.

Since γ is chosen arbitrarily close to α, deploying
(<ref>) to substitute w, the above lower bound can be
written as

    lim_n→∞C(s̃)/C( s^*)   ≥(d+1/d-α-1)[1+α(d+1)/d-α]^d/[α(d+1)/d-α]^d+1
       = (α+1/d-α)[d(α+1)/d-α]^d/[α(d+1)/d-α]^d+1
       = (α+1)^d+1 d^d/α^d+1 (d+1)^d+1
       = 1/d+1(1-1/d+1)^d(1+1/α)^d+1
       ≥1/e1/d+1(1+1/α)^d+1.





§ UPPER BOUNDS



The negative results of the previous sections involve constructions
where the ratio W of the largest to smallest weight can be
exponential in d. In the main theorem (<ref>)
of this section we present an analysis which is sensitive to this
parameter W, and identify conditions under which the performance of
approximate equilibria can be significantly improved.

Our upper bound approach is based on the design of a suitable
approximate potential function and has three main steps. First, in
<ref>, we set up a framework for the
definition of this function by identifying conditions that, on the one
hand, certify the existence of an approximate equilibrium and, on the other,
provide guarantees about its efficiency.
Then, in <ref>, by use of the Euler-Maclaurin summation formula we present a
general form of an approximate potential function, which extends
Rosenthal's potential for weighted congestion games (see also <ref>).
Finally, in <ref>, we deploy this potential for polynomial latencies.  Due to its analytic description, our
potential differs from other extensions of the Rosenthal's potential
that have appeared in previous work, and we believe that this contribution might be
of independent interest, and applied to other classes of
latency functions.



 §.§ The Potential Method



In the next lemma we lay the ground for the design and analysis of
approximate potential functions, by supplying conditions that not only
provide guarantees for the existence of approximate equilibria, but also for their performance with respect to the social optimum.
In the premises of the lemma, we
give conditions on the resource functions ϕ_e, having in
mind that ( s)=∑_e∈ Eϕ_e(x_e( s)) will eventually
serve as the “approximate” potential function.


  
  Consider a weighted congestion game with latency functions c_e,
  for each facility e∈ E, and player weights w_i, for each
  player i∈ N. If there exist functions ϕ_e:_≥ 0 and parameters α_1,α_2,β_1,β_2>0 such that
  for any facility e and player weight w∈w_1,…,w_n

    α_1≤ϕ_e(x+w)-ϕ_e(x)/w· c_e(x+w)≤α_2,
        for all   x≥ 0,

and

    β_1≤ϕ_e(x)/x· c_e(x)≤β_2,
         for all   x≥min_n w_n,

then our game has an α_2/α_1-approximate pure Nash
equilibrium which, furthermore, has Price of Stability at most
β_2/β_1.


  Denote α=α_2/α_1,
  β=β_2/β_1. First we will show that the
  function ( s)=∑_e∈ Eϕ_e(x_e( s))
  (defined over all feasible outcomes s) is an
  α-approximate potential, i.e. for any profile s, any
  player i and strategy s_i'∈ S_i,

    C_i(s_i', s_-i)< 1/αC_i( s)
        (s_i', s_-i) < ( s).

This would be sufficient to establish the existence of a pure α-approximate equilibrium, since any (local) minimizer of  will do. So, it is enough to prove that

    (s_i', s_-i)-( s) ≤ w_iα_1[α· C_i(s_i', s_-i) - C_i( s) ].

Indeed, if for simplicity we denote x_e=x_e( s) and
x_e'=x_e(s_i', s_-i) for all facilities e, we can compute

    (s_i', s_-i)-( s)
       = ∑_e∈ E[ ϕ_e(x_e')-ϕ_e(x_e)]
       = ∑_e∈ s_i'∖ s_i[ ϕ_e(x_e+w_i)-ϕ_e(x_e)] + ∑_e∈ s_i∖ s_i'[ ϕ_e(x_e-w_i)-ϕ_e(x_e)]
       ≤α_2∑_e∈ s_i'∖ s_i w_i c_e(x_e+w_i) - α_1∑_e∈ s_i∖ s_i' w_i c_e(x_e)
       ≤  w_iα_2(∑_e∈ s_i'∖ s_i c_e(x_e+w_i) +∑_e∈ s_i' s_i c_e(x_e))
                   - w_iα_1 (∑_e∈ s_i∖ s_i' c_e(x_e) +∑_e∈ s_i' s_i c_e(x_e))
       = w_iα_1[α(∑_e∈ s_i'∖ s_i  c_e(x_e+w_i) +∑_e∈ s_i' s_i c_e(x_e)).
                       -. (∑_e∈ s_i∖ s_i' c_e(x_e) +∑_e∈ s_i' s_i c_e(x_e)) ]
       = w_iα_1[α C_i(s_i', s_-i) - C_i( s) ].

where the first inequality holds due to (<ref>)
and the second one because α_2≥α_1.

Next, for the upper bound of β on the Price of Stability, it is enough to show that for any profiles s, s',

    ( s) ≤( s')      C( s) ≤β· C( s'),

because then, if s^*∈_ s C( s) is an optimal-cost
profile and s̃∈_ s( s) is a
global minimizer of , then C(s̃)≤β C(
s^*) (and furthermore, as a minimizer of , s̃ is clearly an
α-approximate equilibrium as well; see the first part of the current proof).
Indeed, denoting x_e=x_e( s), x_e'=x_e( s') for simplicity, we have:

    ( s')-( s)     = ∑_e∈ Eϕ_e(x_e')-∑_e∈ Eϕ_e(x_e)
       ≤β_2∑_e∈ Ex_e'c_e(x_e') -β_1∑_e∈ Ex_ec_e(x_e)
       =β_2 C( s') - β_1 C( s)
       =β_1(β C( s') -  C( s) ),

where for the first inequality we deployed (<ref>).





 §.§ Faulhaber's Potential


In this section we propose an approximate potential function, which is based on the
following classic number-theoretic result, known as Faulhaber's
formula[See, e.g., <cit.> or
<cit.>). Johann Faulhaber <cit.> was the first to
discover the formula and express it in a systematic way, up to the power of m=17.
Jakob Bernoulli was able to state it in its full generality as his famous
Summæ Potestatum <cit.>, by introducing what are now
known as Bernoulli numbers (see also <ref>). The first
to rigorously prove the formula was Carl Jacobi <cit.>.], which states
that for any positive integers n,m,

    ∑_k=1^n k^m
         = 1/m+1∑_j=0^m(-1)^jm+1j B_jn^m+1-j
       = 1/m+1n^m+1+1/2n^m+1/m+1∑_j=2^mm+1j B_jn^m+1-j ,

where the coefficients B_j are the usual Bernoulli
numbers.[See, e.g., <cit.> or
  <cit.>. The first Bernoulli numbers are:
  B_0=1, B_1=-1/2, B_2=1/6, B_3=0, B_4=-1/30, …. Also, we know
  that B_j=0 for all odd integers j≥ 3.] In
particular, this shows that the sum of the first n powers with exponent m can
be expressed as a polynomial of n with degree m+1.  Furthermore,
this sum corresponds to the well-known potential of Rosenthal <cit.> for
unweighted congestion games when the latency function is the
monomial x↦ x^m.

Based on the above observation, we go beyond just integer values of
n, and generalize this idea to all positive reals; in that way, we
design a “potential” function that can handle different player
weights and, furthermore, incorporate in a more powerful, analytically
smooth way, approximation factors with respect to both the Price of
Stability, as well as the approximation parameter of the equilibrium
(in the spirit of <ref>). A natural way
to do that is to directly generalize
(<ref>) and simply define, for any real
x≥ 0 and positive integer m,

    S_m(x) :=1/m+1x^m+1+1/2x^m,

keeping just the first two significant terms.[See
  <ref> for further discussion on this
  choice.]

For the special case of m=0 we set S_0(y):= y.

For any positive integer m we define the function
A_m:[1,∞)_>0 with

    A_m(x):=[S_m(x)/x^m+1]^-1
    =(1/m+1+1/2x)^-1
    =2(m+1)x/2x+m+1;

for m=0 in particular, this gives A_0(x)= 1.
Observe that A_m is strictly increasing (in x) for all m≥ 1,

    A_m(1)=2(m+1)/m+3∈ [1,2),
        and    lim_x→∞A_m(x)=m+1.

For the special case of m=0 we simply have A_0(x)=1 for all x≥ 0.



<Ref> shows a graph of these functions.
Since A_m is strictly increasing for m≥ 1, its inverse function, A^-1_m:[2m+1/m+3,m+1) [1,∞), is well-defined and also strictly increasing for all m≥ 1, with

    A^-1_m(x)=(m+1)x/2(m+1-x).


The following two lemmas (whose proofs can be found in
<ref>)
describe some useful properties regarding the algebraic behaviour, and the relation
among, functions A_m and S_m:



Fix any reals y≥ x≥ 1. Then the sequences
A_m(x)/m+1 and A_m(x)/A_m(y)
are decreasing, and sequence A_m(x) is increasing (with respect to m).





Fix any integer m≥ 0 and reals γ, w ≥ 1. Then

    γ^m+1/A_m(γ w)≤S_m(γ(x+w))-S_m(γ x)/w(x+w)^m≤γ^m+1,
        for all   x≥ 0,

and

    γ^m+1/m+1≤S_m(γ x)/x^m+1≤γ^m+1/A_m(γ),
        for all   x≥ 1.







 §.§ The Upper Bound


Now we are ready to state our main positive result:


At any congestion game with polynomial latency functions of degree at most d≥ 1
and player weights ranging in [1,W], for any
2(d+1)W/2W+d+1≤α≤ d+1
there exists an α–approximate pure Nash equilibrium that, furthermore, has Price of Stability at
most

    1+(d+1/α-1)W.


Observe that, as the approximation parameter α increases, the Price of
Stability decreases, in a smooth way, from d+3/2 down to the optimal value
of 1. Furthermore, notice how the interval within which α ranges, shrinks
as the range of player weights W grows; in particular, its left boundary
2(d+1)W/2W+d+1 goes from 2d+1/d+3=2-4/d+3 (for W=1) up
to d+1 (for W→∞).

As a result, <ref> has two interesting
corollaries, one for α=2(d+1)W/2W+d+1 and one for W=1 (unweighted games):



At any congestion game with polynomial latencies of degree at most
d≥ 1 where player weights lie within the range [1,W], there is
an 2(d+1)W/2W+d+1-approximate pure Nash equilibrium with Price of Stability
at most d+3/2.

It is interesting to point out here that, in light of <ref>, the above result
of <ref> is almost asymptotically tight as
far as the Price of Stability is concerned (see the discussion preceding <ref>).



At any unweighted congestion game with polynomial latencies of degree at most d≥
1, the Price of Stability of α-approximate equilibria is at most
d+1/α, for any 2d+1/d+3≤α≤ d+1.


Before proving <ref>, we first restate it in the following
equivalent form, that parametrizes the approximation factor of the equilibrium, as
well as its Price of Stability guarantee, with respect to an “external”, seemingly
artificial parameter γ∈[1,∞). The equivalence of the two formulations
is formally proven in <ref>.

[Restatement of <ref>]

For any γ≥ 1 there exists an A_d(γ W)-approximate pure Nash
equilibrium, which furthermore has Price of Stability at most
d+1/A_d(γ), where A_d is the strictly increasing
function[See <ref>.] taking values within
[2d+1/d+3,d+1) defined in (<ref>).


The statement of <ref> may at first seem a bit cryptic,
compared to <ref>. Nevertheless, it brings forth some
important aspects of our upper bound construction that are not immediately obvious
from <ref>. In particular, notice how the weight range W has
no effect in the Price of Stability guarantee in the statement
of <ref>, but appears only in the approximation factor of
the equilibrium. Furthermore, as it will become more clear in
<ref>, this formulation provides a good degree of high-level
abstraction that helps with generalizing and improving our result in certain cases,
in a unified way. We believe this is important, since it is a promising direction
for future work (see also the discussion in <ref>). 


Without loss of generality, it is enough to consider only weighted congestion games with
monomial latency functions (of degree at most d); any polynomial is a sum
of monomials, so we can just simulate the polynomial latency of a facility by
introducing monomial-latency facilities for each one of its summands. More formally,
if a facility e has latency function c_e(x)=∑_j=0^d a_e,jx^j, with
constants a_e,0,a_e,1,…,a_e,d≥ 0, we can replace e by facilities
e_0,…,e_d with latencies c_e_j(x)=a_e,jx^j, without any change to the
costs of the players. Furthermore, we can safely ignore all such facilities e_j with a_e,j=0, since they have absolutely no effect in the players' costs.

So, from now on assume that for each facility e∈ E there exists a real constant
a_e> 0 and an nonnegative integer m_e≤ d such that

    c_e(x)=a_ex^m_e.

Then, in order to utilize <ref>, we choose functions

    ϕ_e(x)
    =a_e· S_m_e(γ x),

were γ is a real parameter, free to range in [1,∞).
Recall here that functions S_m and A_m are defined in
(<ref>) and (<ref>). 

To simplify notation, from now on we fix an arbitrary facility e and drop the e-subscripts from ϕ_e, c_e, a_e and m_e.

From
(<ref>) of <ref> we get that, for any x≥
0 and w∈[1,W],


    γ^m+1/A_m(γ w)≤ϕ(x+w)-ϕ(x)/w· c(x+w)   =a[S_m(γ(x+w))-S_m(γ x)]/w· a·  (x+w)^m≤γ^m+1.


Similarly, from (<ref>) we have that for any x≥ 1,

    γ^m+1/m+1≤ϕ(x)/x· c(x)
    = a· S_m(γ x)/x· a· x^m=S_m(γ x)/x^m+1≤γ^m+1/A_m(γ).


Now let us just scale the functions ϕ_e we defined in (<ref>)
by a factor of 1/S_m(γ) and define a potential function

    ϕ̅(x)=ϕ(x)/S_m(γ)=A_m(γ)/γ^m+1·ϕ(x)=aA_m(γ)/γ^m+1 S_m(γ x).

Our previous bounds for ϕ show us that ϕ̅ satisfies
the requirements of <ref> with parameters

    α_1    =γ^m+1/A_m(γ w)·A_m(γ)/γ^m+1=A_m(γ)/A_m(γ w)≥A_d(γ)/A_d(γ w)≥A_d(γ)/A_d(γ W)
    α_2    = γ^m+1·A_m(γ)/γ^m+1=A_m(γ)≤ A_d(γ)
    β_1    = γ^m+1/m+1·A_m(γ)/γ^m+1=A_m(γ)/m+1≥A_d(γ)/d+1
    β_2    =γ^m+1/A_m(γ)·A_m(γ)/γ^m+1=1,

where the inequalities hold due to <ref>,
taking into consideration the fact that γ w≥γ≥ 1 and m≤ d;
specifically for the last inequality on the bound of α_1 we also used the
fact that A_d is monotonically increasing.

Putting everything together, from <ref> we deduce that
indeed there exists an A_d(γ W)–approximate pure Nash equilibrium with Price
of Stability at most d+1/A_d(γ). The fact that A_d(γ) ranges
(monotonically) in [2d+1/d+3,d+1) is a consequence
of (<ref>).




 §.§ Small vs Large Degree Polynomials



One can argue that our choice to keep only the first two terms in Faulhaber's
formula (<ref>), when defining our approximate potential
in (<ref>), is suboptimal. To some extent, this is correct; it
is exactly the reason why this seemingly “unnatural” lower bound of
2d+1/d+3=2-4/d+3 for the approximation parameter α appears
in <ref> (or, more generally,
2(d+1)W/2W+d+1 in <ref>). It would be nicer if
α could simply start from 1 instead. Indeed, this can be achieved for small
values of d, as described below.

Considering the entire right-hand side expression in
(<ref>), one can take the full, exact version of
Faulhaber's formula, that can be written[See, e.g.,
<cit.> or <cit.>.] in a very elegant
way as

    ∑_k=1^n k^m
    	= 1/m+1[B_m+1(n+1)-B_m+1(0) ],

where

    B_m(y)=∑_k=0^mmkB_ky^m-k,      y≥ 0,

are the Bernoulli polynomials, and coefficients B_k=B_k(0) are the standard
Bernoulli numbers we used before. Now we can use (<ref>)
to define a more fine-tuned version for S_m, that is, for m≥ 1 set Ŝ_m(x)=1/m+1[B_m+1(x+1)-B_m+1] instead of
(<ref>). For example, for degrees up to m≤ 4 these new
polynomials are:

    Ŝ_0(x)=x,    Ŝ_1(x)= 1/2 x (x+1),    Ŝ_2(x)= 1/6 x (2 x^2+3 x+1)
    Ŝ_3(x)= 1/4 x^2 (x+1)^2,
        Ŝ_4(x)= 1/30 x (6 x^4+15 x^3+10 x^2-1)


Using these values, one can verify that for up to m≤ 4, all our critical
technical requirements for the proof of <ref> (and thus,
<ref> itself) are satisfied: most notably
<ref>, and the
monotonicity of Â_m(x)=x^m+1/Ŝ_m(x) (with respect to x≥
1). In particular, now we have that Â_m(1)=1^m+1/Ŝ_m(1)=1,
which is exactly what we wanted: it means that the critical quantities Â_d(γ W) and Â_d(γ) in <ref> can start
taking values all the way down to Â_d(W) and Â_d(1)=1, respectively.
This translates to the approximation ratio parameter α in our main result in
<ref> starting to range from α≥Â_d(W).

Thus,

<ref> can be rewritten for d≤ 4, with the
approximation parameter α taking values in Â_d(W)≤α≤ d+1. In particular, for unweighted games, this means that
<ref> can be rewritten with α taking values
within the entire range of [1,d+1].


However, there is a catch, that does not allow us to do that in general; as m
grows large, the Bernoulli polynomials, that now play a critical role in our
definition of functions Ŝ_m (see (<ref>)), start to
behave in a rather erratic, non-smooth way within the interior of the real intervals
between consecutive integer values. For example, one can check that, for d=14
function Â_14 is not monotonically increasing within [1,2]. Even
more disastrously, for d=20,21 functions Ŝ_d take negative values in
[1,2] !





§ LOWER BOUND PROOFS




 §.§ Technical Lemmas




 For any d≥ 9,

    (1+ln d/d)^d ≥d/ln d.




From <cit.> we know that the following inequality holds for all n ≥ 1 and 1≤ x ≤ n:

    (1+x/n)^n ≥ e^x(1-x^2/n).

Applying it with n=d and x=ln d we get that indeed

    (1+ln d/d)^d 
    ≥
    e^ln d(1-ln^2 d/d)
    ≥ d 1/ln d,

the last inequality holding due to the fact that for d≥ 9, 
ln^2 d/d+1/ln d≤ln^2 (9)/9+1/ln (9)≈ 0.992 ≤ 1.




For any integer d≥ 2, the function
f:(0,∞)^2 (0,∞) defined by

    f(x,y)=(y+x+1)^d-(y+x)^d/(y+1)^d-y^d

is monotonically decreasing with respect to y. Furthermore, for d≥ 9,

    ζ^d+1≤
    f((β_dΦ_d+1)(ζ-1),β_dΦ_d-(1-β_d)ζ)
        for all  ζ∈[1,2],

where β_d is defined in <ref>.


 First let us define function h:(0,∞) (0,∞) with

    h(t)=(t+1)^d-t^d/(t+1)^d-1-t^d-1.
 We will show that h is increasing, which will suffice to prove the
desired monotonicity of f since its derivative is

    ∂ f(x,y)/∂ y   =
    d [(x+y+1)^d-1-(x+y)^d-1]/(y+1)^d-y^d
    
                    -
    d
    [(y+1)^d-1-y^d-1]
    [(x+y+1)^d-(x+y)^d]/[(y+1)^d-y^d]^2
       =d[(y+1)^d-1-y^d-1][(x+y+1)^d-1-(x+y)^d-1]/[(y+1)^d-y^d]^2[h(y)-h(x+y)
    ],
 which is negative due to the monotonicity of h. To prove that h is
indeed increasing, we will show something stronger; namely that function h̅:(1,∞)
(0,∞) with

    h̅(t)=t^d-(t-1)^d/t^d-t(t-1)^d-1
 is increasing. This will suffice to demonstrate that h is
increasing as well, since h(t)=(t+1)·h̅(t+1).

Taking its derivative we see that

    ∂h̅(t)/∂ t=
    [(t-1)^d-t^d+d t^d-1](t-1)^d /[t^d+1-t^d-t
    (t-1)^d]^2>0

since from the convexity of function t↦ t^d we know that t^d-(t-1)^d<
dt^d-1.

Now let us prove the
remaining part of our lemma, that is (<ref>). Observe that if we
set ζ = 1 to (<ref>) it is satisfied, since f(0,y)=1 for
any y>0. So, it is enough if we prove that

    ζ^-(d+1)f((β_dΦ_d+1)(ζ-1),β_dΦ_d-(1-β_d)ζ)
    =
    ζ^-(d+1)[(α+β)ζ]^d-[(α+β)ζ-1]^d/[α+1-(1-β)ζ]^d-[α-(1-β)ζ]^d

is increasing with respect to ζ∈ [1,2], where here we are using β=β_d and 
α=βΦ_d. So, if we define

    f_1(ζ )    =
    [(α+β)ζ]^d-[(α+β)ζ-1]^d
     f_2(ζ)
       = [α+1-(1-β)ζ]^d-[α-(1-β)ζ]^d
 and we compute the derivative ∂/∂ζ(ζ^-(d+1)f_1(ζ)/f_2(ζ)) of the above
expression, we need to show that

    ζ[f_1'(ζ)/f_1(ζ)-f_2'(ζ)/f_2(ζ)] ≥
    d+1.
 Now notice that

    ζf_1'(ζ)/f_1(ζ)=d(α+β)ζ[(α+β)ζ]^d-1-[(α+β)ζ-1]^d-1/[(α+β)ζ]^d-[(α+β)ζ-1]^d=d/h̅((α+β)ζ),

where h̅ is the increasing function defined in (<ref>), so taking into consideration that

    (α+β)ζ=β(Φ_d+1)ζ≤1/2(Φ_d+1)2≤Φ_d+1,

we can get that

    ζf_1'(ζ)/f_1(ζ)   ≥d/h̅(Φ_d+1) =d(Φ_d+1)(Φ_d+1)^d-1-Φ_d^d-1/(Φ_d+1)^d-Φ_d^d
       = dΦ_d^d+1-Φ_d^d-Φ_d^d-1/Φ_d^d+1-Φ_d^d
    = d-d/Φ_d^2-Φ_d.

Similarly, we can see that

    -ζf_2'(ζ)/f_2(ζ)
    =
    d(1-β)ζ/h(α-(1-β)ζ),

where h is the increasing function defined in (<ref>), so taking into consideration that

    α-(1-β)ζ≤βΦ_d-(1-β)≤Φ_d-1/2    and     (1-β)ζ≥1/2,

we get that

    -ζf_2'(ζ)/f_2(ζ)≥d/2/h((Φ_d-1)/2)
    =
    d(Φ_d+1)^d-1-(Φ_d-1)^d-1/(Φ_d+1)^d-(Φ_d-1)^d.

Putting everything together, in order to prove the desired
(<ref>), it now suffices to show that

    d(Φ_d+1)^d-1-(Φ_d-1)^d-1/(Φ_d+1)^d-(Φ_d-1)^d-d/Φ_d^2-Φ_d≥
    1,

which we know holds from (<ref>) of
<ref>.





For any integer d≥ 9,

    (Φ_d+1)^d-1-(Φ_d-1)^d-1/(Φ_d+1)^d-(Φ_d-1)^d-1/Φ_d^2-Φ_d≥1/d.

Furthermore, asymptotically Φ_d∼d/ln d, i.e.

    lim_d→∞Φ_d/d/ln d=1.

In particular, for any integer d,

    Φ_d ≤γ_dd/ln d    with  γ_d:=ln d/𝒲(d)≤ 1.368
       and  lim_d→∞γ_d=1,
 where 𝒲(·) denotes the (principal branch of the) Lambert–W
function[That is, for any positive real x, 𝒲(x)=z gives the unique
positive real solution z to the equation x=z· e^z.].



To show (<ref>), first one can simply
numerically verify that it indeed holds for all integers d=9,10,…,17, so let us
just focus on the case when d≥ 18. For simplicity, in the remainder of the
proof we denote y=Φ_d. It is easy to see[Here we are silently using
the fact that Φ_n is an increasing function of the integer n. One can
formally prove this by, e.g., combining Lemmas 5.1 and 5.2 of <cit.>.]
then that

    y≥Φ_18≈ 8.11>8.

Performing some elementary algebraic manipulations in (<ref>),
we can equivalently write it as

    (y+1)^d-1[-y^3+dy^2-(2d-1)y-d]≥ (y-1)^d+1(d-y).

Using the fact that (y+1)^d-1=y^d+1/y+1, and then that y^d+1≥ (y-1)^d+1, we
can see that it is enough to show that

    -y^3+dy^2-(2d-1)y-d ≥ (d-y)(y+1),

or equivalently,

    y^2(d-y) -2dy + y -d ≥ (d-y)(y+1) 
    
    (d-y)[y^2-1-(y+1)] ≥ 2dy 
    
    (d-y)(y+1)(y-2) ≥ 2y d 
    (y+1)(y-2)/2y≥1/1-y/d.


For the last inequality we took into consideration that y/d<1. As a matter of fact, using an upper
bound of y≤2d/ln d on y=Φ_d (see <cit.> or (<ref>)), we have that

    y/d≤2/ln d≤2/ln(18)≈ 0.692.

Due to the fact that function z↦1/1-z is increasing for z∈
[0,1), this bound gives us that 1/1-y/d≤1/1-0.69≤
3.226. In a similar way, noticing that function z↦(z+1)(z-2)/2z is
increasing for z>2, using the fact that y>8 we can derive that
(y+1)(y-2)/2y>(8+1)(8-2)/2· 8=27/8≈ 3.375. This
establishes the validity of (<ref>).

Next, we deal with upper-bounding the values of Φ_d and proving
(<ref>), since we'll need this for establishing the asymptotics
of Φ_d in (<ref>). Here we will make use of the following property,
which was shown in <cit.>: for any real
γ>0,

    Φ_d<γd/ln d    (1+ln d/γ d)^d < γ d/ln d.

In a similar way to the proof of <cit.>, using a binomial expansion we can compute:

    (1+ln d/γ d)^d 
       = ∑_k=0^ddk(ln d/γ d)^k
    = ∑_k=0^dd!/d^k(d-k)!(ln d/γ)^k1/k!
       = ∑_k=0^d(1-1/d)(1-2/d)…(1-k-1/d)(ln d/γ)^k1/k!
       < ∑_k=0^∞(ln d/γ)^k/k!
    =e^ln d/γ=d^1/γ,

where for the second to last equality we used the power series representation of the
exponential function: e^z=∑_k=0^∞z^k/k!. Thus, from
(<ref>) we can derive that, for any γ>0,

    d^1/γ≤γ· d/ln d    Φ_d<γd/ln d,
 
Using γ_d=ln d/𝒲(d)
as defined in the statement of our lemma, we compute:

    d^1/γ_d=d^𝒲(d)/ln d=e^𝒲(d)

and

    γ_dd/ln d=ln d/𝒲(d)d/ln d=d/𝒲(d).

Thus, since from the definition of function 𝒲 we know that

    𝒲(d)e^𝒲(d)=d,

we deduce that γ=γ_d indeed satisfies the left hand
side of
(<ref>), giving us the desired upper bound for Φ_d.

For the asymptotic behaviour of γ_d when d grows large, observe that by
taking logarithms in (<ref>) we get 
    𝒲(d) + ln𝒲(d) =
    ln d
 and so

    lim_d→∞γ_d =lim_d→∞ln d/𝒲(d)
    =lim_d→∞[ln𝒲(d)/𝒲(d)+1
    ]=1+lim_z→∞ln z/z=1,

since it is easy to see that lim_d→∞𝒲(d)=∞.

Finally, let us now establish (<ref>). Due to (<ref>)
that we have already proved, it is enough to just show a lower bound of
lim_d→∞Φ_d/d/ln d≥ 1. We will do this by showing that
Φ_d≥d/ln d for sufficiently large values of d. Indeed, by
(<ref>) this is equivalent to proving that

    (1+ln d/d)^d ≥d/ln d,

which from <ref> we know it holds for all d≥ 9.





 §.§ Proof of Lemma 3.2



To decongest notation a bit in the proof, we will drop the d
subscripts from c_d and β_d whenever this is causing no confusion. Starting
with
(<ref>), if we solve with respect to β we get

    Φ_d+1/β≥Φ_d^1+2/d    β≤1/Φ_d(Φ_d^2/d-1)
    =Φ_d/2Φ_d+1,

where for the last equality we used the fact that

    Φ_d^2/d=(1+1/Φ_d)^2=1/Φ_d^2+2/Φ_d+1

which is a direct consequence of the definition of Φ_d:

    Φ_d^d+1=(Φ_d+1)^d    Φ_d^1+1/d=Φ_d+1
        Φ_d^1/d=1+1/Φ_d.


Substituting (<ref>) into (<ref>),

    1-Φ_d^-c≤Φ_d/2Φ_d+1   Φ_d^-c≥Φ_d+1/2Φ_d+1
        c≤ln(2Φ_d+1)-ln(Φ_d+1)/lnΦ_d,

which holds by the very definition of c in (<ref>) if we relax the floor
operator.

Let us now move to (<ref>), and in particular  lower-bound the
values of parameter β, as d grows large. Due to the floor operator in
(<ref>), parameter c can be lower bounded by

    c ≥ln(2Φ_d+1)-ln(Φ_d+1)/lnΦ_d
    -1/d=log_Φ_d2Φ_d+1/Φ_d+1
    -1/d
 and since β is increasing with respect to c,

    β = 1-Φ_d^-c≥ 1- Φ_d+1/2Φ_d+1Φ_d^1/d= 1- Φ_d+1/2Φ_d+1(1+1/Φ_d).

Taking limits and recalling that lim_d→∞Φ_d=∞, we get the
desired lower bound of

    lim_d→∞β≥ 1-1/2· (1+0)=1/2.


The upper bound of β≤1/2 can be easily derived by (<ref>):

    β≤Φ_d/2Φ_d+1≤Φ_d/2Φ_d=1/2.


For small values of d, and in particular in order to prove that β≥0.38,
one can numerically compute the values for β directly from (<ref>).
For example, for d=9,…,100, these values are shown in <ref>. The
lower and upper red lines in <ref> correspond to the relaxation of the
floor operator we used in the lower and upper bounds for β in
(<ref>) and
(<ref>), respectively. The actual values of β lie
between these two lines. Using these values and the resulting monotonicity for
β, one can also prove the lower bound of 3 for dc, by observing that by
setting d=9 in (<ref>) we have that for any d≥ 9

    d· c ≥⌊
    9ln(2·Φ_9+1)-ln(Φ_9+1)/ln(Φ_9)⌋≈⌊ 3.368⌋=3,

since Φ_9≈ 5.064.


 §.§ Proof of Claim 3.3



Since we have fixed that s_j=s̃_j for all
players j< i and also the strategies of players j>i+μ have no effect on the
cost of player i (and in particular in (<ref>)), it is safe
if we briefly abuse notation and for now assume that s_-i=(s_i+1,…,s_i+μ).

We generate the desired dominating profile s'_-i inductively, by running
Procedure Dominate( s_-i,i) described formally below, scanning and
modifying profile s_-i from right to left.



Profile s_-i=(s_i+1,…,s_i+μ); Player
i∈μ+1,…,n
Profile s'_-i=(s_i+1',…,s_i+μ') of the form described in
<ref> of
<ref>, that satisfies <ref>
s_-i'  s_-i 
s_i+μ'  s_i+μ^*  
k  i+μ -1 
exists j∈i+1,…,k-1 such that s'_j= s_j^*

s'_k s̃_k  
k  k-1  
Procedure Dominate( s_-i,i)



First, it is not difficult to see that the output profile s'_-i of
Dominate( s_-i,i) indeed has the desired format described in
<ref> of <ref>. In particular, after any execution of the
while-loop in lines
<ref>–<ref> of
Procedure Dominate, s_j'=s̃_j for any j=k+1,…,i+μ-1.

Furthermore, it is also easy to see that switching player's i+μ strategy to
s'_i+μ= s^*_i+μ can only increase player's i cost,
i.e. (<ref>) is satisfied after line
<ref> of Dominate: if player i+μ
chooses s̃_i+μ instead, she contributes nothing to the cost of player
i, since she does not put her weight in any of the facilities i+1,…, i+μ
played by player i.


So, it remains to be shown that after every iteration of the while-loop, condition
(<ref>) is maintained. Since in any such loop only the
strategy of player k is possibly switched from s_k^* to s̃_k, it is
enough if we show that
C_i(s̃_k, s'_-k) ≥ C_i(s^*_k, s'_-k)
or, since for any facility j<k it holds that x_j(s̃_k,
s'_-k)=x_j(s^*_k, s'_-k), equivalently

    ∑_j=k^i+μc_j(x_j(s̃_k, s'_-k))
    ≥∑_j=k^i+μc_j(x_j(s^*_k, s'_-k)).

If we let z_j, for any j≥ k, denote the load on facility j induced by every
player except from player k, that is formally

    z_j = ∑w_ℓℓ∈j-μ,…,j∖k     j∈ s_ℓ',

the above can be written as

    ∑_j=k+1^i+μ[ c_j(z_j+w_k)-c_j(z_j) ]
    ≥ c_k(z_k+w_k)-c_k(z_k).

Thus, it is sufficient only take j=i+μ in the above sum and just prove that

    c_i+μ(z_i+μ+w_k)-c_i+μ(z_i+μ) ≥ c_k(z_k+w_k)-c_k(z_k),
 which
is equivalent to

    w^-(i+μ-k)(d+1)(z_i+μ+w_k)^d-z_i+μ^d/(z_k+w_k)^d-z_k^d≥ 1.


If we define

    A=j∈i+1,…,k-1s_j=s_j^*,

that is, A is the set of players below k (and above i) that do not
contribute with their weight to the cost of players k and i+μ, we have that

    z_k=∑_j∉ Aj=k-μ^k-1w_j=α w_k -∑_j∈ A w_j

and

    z_i+μ=∑_j∉ Akj=i^i+μw_j=(α+1)
    w_i+μ -w_k -∑_j∈ A w_j,

because by our inductive process we know that s_j'=s̃_j for all
j=k+1,…,i+μ-1. Thus

    z_i+μ=z_k+(α+1)(w_i+μ-w_k).

Now we can rewrite the left hand side of (<ref>) as

    w^-(i+μ-k)(d+1)[z_k+(α+1)w_i+μ-α
    w_k]^d-[z_k+(α+1)w_i+μ-(α+1)w_k]^d/(z_k+w_k)^d-z_k^d,

and, if we additionally define for simplicity

    ζ:= w^λ,
        where    λ:=μ-k+i∈1,…,μ-2

and

    y_k:=z_k/w_k,

(<ref>) can be written as

    ζ^-(d+1)[y_k+(α+1)ζ-α]^d-[y_k+(α+1)ζ-α-1]^d/(y_k+1)^d-y_k^d≥ 1,

or more simply,

    ζ^-(d+1)f(x,y)≥ 1

if we use function f from <ref> with values

    x= (α+1)w^λ-α-1=(α+1)(ζ-1)>0
        and     y=y_k>0.

Deploying the monotonicity of f from <ref> and using that

    y=z_k/w_k=α-1/w_k∑_j∈ A w_j≤α-1/w_kw_i+1=α-w^i+1-k=α - w^λ-μ+1≤α-(1-β)ζ,

where the first inequality holds due to the fact that from the while-loop test in
line <ref> of Procedure Dominate we know that
A≠∅ and the last one because of 1-β=w^-μ, we finally get that it is enough if we show that

    ζ^d+1≤ f((α+1)(ζ-1),α-(1-β)ζ)    for
    all  ζ∈[1,1/1-β],

since ζ≥ w^1≥ 1 and ζ≤ w^μ-2≤ w^μ=(1-β)^-1.
But this is is satisfied, due to (<ref>) of <ref>, since we have selected our parameters c=c_d and β=β_d as in
<ref>.



 §.§ Proof of Equation (3.8)



In any such profile, player i+μ plays s_i+μ^* and

  
  * Either all other players j=i+1,…,i+μ-1 play s̃_j, in
  which case
  
    C_i(s̃_i, s_-i')    = c_i+μ(∑_ℓ=i^i+μ
        w_ℓ) + ∑_j=i+1^i+μ-1c_j(∑_ℓ=j-μ^j-1
        w_ℓ)
       = c_i+μ((α+1)w^i+μ) +
        ∑_j=i+1^i+μ-1c_j(α w^j)
       =
        w^-(i+μ)(d+1)(α+1)^dw^d(i+μ) +
        ∑_j=i+1^i+μ-1w^-j(d+1)α^dw^dj
       =w^-(i+μ)(α+1)^d+∑_j=i+1^i+μ-1w^-jα^d
       =w^-i[(α+1)^dw^-μ+α^d∑_j=1^μ-1w^-j]
       =w^-i[(α+1)^dw^-μ+α^d(α-w^-μ)],

  the last equality holding due to the definition of α.
  
  * Or there exists a single player
  k∈i+1,…,i+μ-1 that plays s_k^* (instead of s̃_k
  which corresponds exactly to the previous case), in which case
  
    C_i(s̃_i, s_-i')    ≤ c_k(∑_ℓ=k-μ^k w_ℓ)+ c_i+μ(∑_ℓ=i^i+μ w_ℓ -w_k ) +
        ∑_j≠
        k,i+μj=i+1^i+μc_j(∑_ℓ=j-μ^j-1 w_ℓ)
       =
        c_k((α+1)w^k) +
        c_i+μ((α+1)w^i+μ-w^k) + ∑_j≠
        kj=i+1^i+μ-1c_j(α w^j)
       = w^-i[(α+1)^dw^-(k-i)+(α+1-w^k-i-μ)^dw^-μ.
                               .+α^d(α-w^-μ-w^-(k-i))],
 which is decreasing with respect to k, so taking the smallest
  possible value k=i+1 we have that
  
    C_i(s̃_i, s_-i') ≤
    
      w^-i[(α+1)^dw^-1+(α+1-w^1-μ)^dw^-μ+α^d(α-w^-μ-w^-1)].

 Considering both the above possible scenarios, in order to prove
(<ref>) it is thus sufficient to make sure that

    α^d(α-w^-μ)< (α+1)^d(1-w^-μ)
 and

    (α+1-w^1-μ)^dw^-μ+α^d(α-w^-μ-w^-1)<
    (α+1)^d(1-w^-1).
 For (<ref>), its left-hand side can be written
as

    (βΦ_d)^d(βΦ_d-(1-β)) <
    (βΦ_d)^d(βΦ_d) =β^d+1Φ_d^d+1
    =β^d+1(Φ_d+1)^d,

the first inequality holding because β<1, while the right-hand side is

    (βΦ_d+1)^d(1-(1-β))=β^d+1(Φ_d+1/β)^d.
 Thus it is enough to prove that

    (Φ_d+1)^d≤(Φ_d+1/β)^d,

which holds since β∈ (0,1).

For (<ref>), the left-hand side is written as

    (βΦ_d+1-(1+1/Φ_d)(1-β))^d(1-β)
                           + (βΦ_d)^d(βΦ_d-(1-β)-(1+1/Φ_d)^-1)
    
      =   (βΦ_d+β-1-β/Φ_d)^d(1-β)
      +β^dΦ_d^d(βΦ_d-(1-β)-Φ_d/Φ_d+1)
     <   (βΦ_d+β)^d(1-β)
      +β^dΦ_d^d(βΦ_d-Φ_d/Φ_d+1)
     =   β^d(Φ_d+1)^d(1-β)
      +β^dΦ_d^d(βΦ_d-Φ_d/Φ_d+1)
    
      =   β^d(Φ_d)^d+1(1-β)
      +β^dΦ_d^d(βΦ_d-Φ_d/Φ_d+1)
    
      =   β^dΦ_d^d(Φ_d-βΦ_d+βΦ_d-Φ_d/Φ_d+1)
    
      =   β^dΦ_d^d+2/Φ_d+1
 and the right-hand side

    (βΦ_d+1)^d(1-(1+1/Φ_d)^-1)
    =β^d(Φ_d+1/β)^d1/Φ_d+1.

Thus it suffices to prove that

    Φ_d^d+2≤(Φ_d+1/β)^d,

which holds due to (<ref>) since we have already selected parameter
c=c_d as in (<ref>).



§ UPPER BOUND PROOFS




 §.§ Technical Lemmas




For any positive integer m and real x>0,

    (1+1/x)^m ≥ 1+m+1/2x



Expanding the power in the left hand side we get

    (1+1/x)^m
    = ∑_j=0^mmj1/x^j≥∑_j=0^1mj1/x^j
    =1+m/x≥ 1+ m+1/2x,

since

    m/x≥m+1/2x m ≥m+1/2
    m ≥ 1.






For any integer m≥ 0 and real x≥ 0,

    (x+1)^m+1-x^m+1≤m+1/2[(x+1)^m+x^m].



Expanding the powers, our inequality can be rewritten equivalently as:

    ∑_j=0^m+1m+1j x^j -x^m+1≤m+1/2[∑_j=0^mmjx^j+x^m]



    ∑_j=0^m-1m+1j x^j+ (m+1)x^m
    ≤m+1/2[∑_j=0^m-1mjx^j+2x^m].



    ∑_j=0^m-1m+1j x^j
    ≤m+1/2∑_j=0^m-1mjx^j.

Now, we can see that the above holds by bounding each term; for integers j=0,1,…,m-1:

    m+1j   =
     (m+1)!/(m+1-j)! j!
     = m+1/m+1-jm!/(m-j)! j!
       = m+1/m+1-jmj≤m+1/2mj.





 §.§ Proof of Lemma 4.2



Observe that from the definition of A_m in (<ref>),

    (A_m(x))^-1=1/m+1+1/2x

which is decreasing with respect to m, and

    (A_m(x)/m+1)^-1
    =1+m+1/2x,

which is increasing with respect to m. For the remaining sequence, observe that for any integer m≥ 0 and reals y≥ x≥ 1,

    A_m(x)/A_m(y)≥A_m+1(x)/A_m+1(y)A_m+1(y)/A_m(y)≥A_m+1(x)/A_m(x),

so it is enough to show that function A_m+1(x)/A_m(x) is monotonically increasing with respect to x≥ 0. Indeed,

    A_m+1(x)/A_m(x)   =1/m+1+1/2x/1/m+2+1/2x
    =2x(m+2)+(m+1)(m+2)/2x(m+1)+(m+1)(m+2)
       =1+1/m+1(1+m+2/2x)^-1.




 §.§ Proof of Lemma 4.3



First for (<ref>), notice that it can be rewritten equivalently as

    1/m+1≤S_m(γ x)/(γ x)^m+1=1/A_m(γ x)≤1/A_m(γ),

which holds, as an immediate consequence of the monotonicity of function A_m (see (<ref>)), given that γ x≥γ≥ 1.

For (<ref>), it is enough to prove just the special case when w=1, i.e.,

    γ^m+1/A_m(γ)=S_m(γ)
    ≤S_m(γ x+γ)-S_m(γ x)/(x+1)^m≤γ^m+1,

since then it is not difficult to check that we can recover the more general case in
(<ref>) by simply substituting γ := γ w and
x := x/w in (<ref>).

It is not difficult to check that (<ref>)
holds for m=0, recalling that S_0(x)=x for all x≥ 0. Next, assume for the
remainder of the proof that m≥ 1.

For the left-hand inequality of (<ref>) first,
it can be equivalently rewritten as:

    (x+1)^m(1/m+1γ^m+1+1/2γ^m)
    ≤
    1/m+1γ^m+1[(x+1)^m+1-x^m+1]
    1/2γ^m[(x+1)^m-x^m]



    1/2x^m ≤γ/m+1[(x+1)^m+1-(x+1)^m-x^m+1],

and since γ≥ 1, it is sufficient to show that

    (m+1)x^m ≤ 2[(x+1)^m+1-(x+1)^m-x^m+1]

and thus, enough to show that

    (m+1)x^m ≤ 2x[(x+1)^m-x^m ].

Now observe that the above trivially holds if x=0, while for x>0 it can be equivalently written as

    m+1/2x≤(1+1/x)^m-1,

which holds due to <ref>.

For the right-hand inequality of (<ref>), it
can be equivalently written as:

    1/m+1γ[(x+1)^m+1-x^m+1]+1/2[(x+1)^m-x^m] ≤γ (x+1)^m



    2γ[(x+1)^m+1-x^m+1] ≤ (m+1)[(2γ-1)(x+1)^m+x^m]


    (x+1)^m+1-x^m+1≤ (m+1)[(1-1/2γ)(x+1)^m+1/2γ x^m].

Since γ≥ 1, we know that 1/2γ∈[0,1/2]. Thus,
taking into consideration that (x+1)^m>x^m≥ 0, the linear combination on the
right-hand side of the above inequality is minimized for
1/2γ=1/2. So, it is enough to show that

    (x+1)^m+1-x^m+1≤m+1/2[(x+1)^m+x^m],

which holds due to <ref>.



 §.§ Equivalence of Theorem 4.4 and Claim 4.7



To verify that <ref> gives indeed an equivalent restatement
of <ref>, fix an arbitrary W≥ 1 and observe the
equivalence

    α= A_d(γ W)=2(d+1)γ W/2γ W+d+1    γ= 1/2Wα(d+1)/d+1-α,

by using the definition of function A_d from (<ref>).
Therefore, it is not difficult to also compute that

    d+1/A_d(γ)   =(d+1)(1/d+1+1/2γ)=1+d+1/21/γ
       = 1+d+1/2· 2W d+1-α/α(d+1)
    =1+W(d+1/α-1).




§ BEYOND POLYNOMIAL LATENCIES: EULER-MACLAURIN



Our definition of the approximate potential function in
<ref> was based in Faulhaber's formula
(<ref>) for the sum of powers of positive integers. This
approach can be generalized further, by considering the Euler-Maclaurin summation
formula[See, e.g., <cit.> and <cit.>.] :

    ∑_j=0^n f(j)=∫_0^nf(t) dt+1/2[f(n)+f(0)]+∑_j=2^mB_j/j![f^(j-1)(n)-f^(j-1)(0)]+ℛ_m,

for any infinitely differentiable function f:[0,∞) (0,∞) (with
f^(j) denoting the j-th order derivative of f) and integers n,m≥ 1,
where B_j denotes the Bernoulli numbers we have already used in
<ref> and the error-term ℛ_m can be bounded by

    ℛ_m≤2ζ(m)/(2π)^m∫_0^nf^(m)(t) dt,

where ζ(m)=∑_j=1^∞1/j^m is Riemann's zeta function. Thus, if
function f is such that the quantity in the right-hand side of
(<ref>) eventually vanishes, i.e. for any real x≥
0,

    lim_m→∞ζ(m)/(2π)^m∫_0^xf^(m)(t) dt =0,

then we can define our approximate-potential candidate function on any real x≥ 0 by generalizing (<ref>):

    S(x)=S_f(x) = ∫_0^xf(t) dt+1/2[f(x)+f(0)]+∑_j=2^∞B_j/j![f^(j-1)(x)-f^(j-1)(0)].


For example, it is not difficult to see that, for any monomial f(x)=x^d of degree
d≥ 1, condition (<ref>) is indeed satisfied
(since f^(m)=0 for all m≥ d+1) and, because also f^(m)(0)=0 and
f^(m)(x)=d!/(d-m)!x^d-m, one recovers exactly
(<ref>) from (<ref>) above.


Let us now demonstrate this general approach for latency functions f that are not
polynomials. For the remaining of this section let f(x)=e^x be an exponential
delay function. Then, for any y≥ 0,

    lim_m→∞ζ(m)/(2π)^m∫_0^yf^(m)(t) dt =(e^y-1) lim_m→∞ζ(m)/(2π)^m=0,

since lim_m→∞ζ(m)=1 and lim_m→∞(2π)^m=∞. Thus, condition (<ref>) is satisfied, and we can define from (<ref>)

    S(x)   = ∫_0^xe^t dt+1/2[e^x+e^0]+∑_j=2^∞B_j/j![e^x-e^0]
       = (e^x-1)-1/2(e^x-1)+∑_j=2^∞B_j/j!(e^x-1) +e^x
       = (e^x-1)∑_j=0^∞B_j/j!+e^x.

But since for the integer value x=1 we know that
S(1)=∑_j=0^1f(j)=1+e,
it must be that

    e+1=(e^x-1)∑_j=0^∞B_j/j!+e
        ∑_j=0^∞B_j/j!=1/e-1.

So, we
finally have that

    S(x)=(e^x-1)1/e-1+e^x=e^x+1-1/e-1.

From this, for all reals x≥ 0, w>0 we compute:

    S(x+w)-S(x)/w f(x+w)=1/e-1e^x+w+1-e^x+1/w e^x+w=e/e-11-e^-w/w,

which does not depend on x. Thus, from (<ref>) in
<ref> we deduce that exact pure Nash equilibria
always exist for weighted congestion games with exponential latencies. The function
S we defined in (<ref>) essentially serves as a weighted
potential <cit.>; its global minimum is a pure Nash equilibrium.
Notice here that these results regarding exponential latency functions were already
known by the work of <cit.>.



§ SOCIAL OPTIMUM IS A (D+1)-APPROXIMATE EQUILIBRIUM

In this section we show that the socially optimum solution is itself an
(d+1)-appproximate equilibrium, where d is the maximum degree of the polynomial
latency functions. We must mention here that, the approximation factor on its own,
i.e. d+1, does not constitute a novel contribution: existence of
(d+1)-approximate equilibria was already known by the work of <cit.>.
However, the new element in <ref> below is that this can be achieved by
all optimum solutions.

Related to this, we would like to emphasize that, if we only cared about showing the
existence of an optimal solution that is a (d+1)-approximate equilibrium,
this would have been an immediate corollary of our main upper bound result: by
simply setting α=d+1 in <ref> we get exactly what we
want. However, the following theorem demonstrates the stronger statement that
all social cost minimizers have the property we want.



Consider any weighted congestion game with polynomial latency functions of maximum
degree d and let s^* be a strategy profile that minimizes social cost.
Then s^* is a (d+1)–approximate pure Nash equilibrium. As an immediate
consequence, the Price of Stability of (d+1)–approximate Nash equilibria is 1.


Let c be an arbitrary cost function of maximum degree d with non-negative
coefficients, i.e., c(x)=∑_j=0^d a_j x^j, with a_j≥ 0 for all j. We
will first show that for all w>0 and x≥ 0:

    w · c(x+w) ≤ (x+w) · c(x+w) - x · c(x) ≤ (d+1) · w · c(x+w).

To this end, with z=x/w, we get

    (x+w) · c(x+w) - x · c(x)
       = ∑_j=0^d a_j ·[ (x+w)^j+1 - x^j+1]
       = ∑_j=0^d a_j · w^j+1[ (1+z)^j+1 - z^j+1]
       = ∑_j=0^d a_j · w^j+1[ ∑_k=0^j j+1k z^k ],

and

    w · c(x+w)
       = ∑_j=0^d a_j · w(x+w)^j
       = ∑_j=0^d a_j · w^j+1[∑_k=0^j jk z^k ].

Clearly, j+1k≥jk for all integer j∈[0,d], k∈[0,j],
which immediately implies the first inequality in (<ref>). To see the
second inequality, observe that

    j+1k/jk = j+1/j+1-k≤ j+1 ≤ d+1.


Since s^* minimizes social cost, for all players i∈[n] and strategies
s_i∈ S_i,

    C(s^*) ≤ C(s_i,s^*_-i).


Denoting y_e=∑_j∈[n]∖{i}: e∈ s^*_j w_j,
from (<ref>), we get

    0    ≤ C(s_i,s^*_-i) -C(s^*) 
       = ∑_e∈ s_i∖ s_i^*[ (y_e+w_i) c_e(y_e+w_i) - y_e c_e(y_e) ]
                                   - ∑_e∈ s^*_i∖ s_i[  (y_e+w_i) c_e(y_e+w_i)- y_e c_e(y_e) ]
       = ∑_e∈ s_i[ (y_e+w_i) c_e(y_e+w_i) - y_e c_e(y_e) ]
      - ∑_e∈ s^*_i[  (y_e+w_i) c_e(y_e+w_i)- y_e c_e(y_e) ]
       ≤  (d+1) ∑_e∈ s_i w_i  · c_e(y_e+w_i) -  ∑_e∈ s^*_i w_i  · c_e(y_e+w_i)
       = (d+1) C_i(s_i,s^*_-i) -C_i(s^*),

or equivalently  C_i(s^*)≤ (d+1) C_i(s_i,s^*_-i). So s^* is a (d+1)-approximate Nash equilibrium.






§ ACKNOWLEDGMENTS
 We thank the anonymous reviewers for the careful and thorough reading of our manuscript, and for their valuable feedback.

abbrvnat 

