Tight Inefficiency Bounds for Perception-Parameterized Affine Congestion Games
Pieter Kleer Guido Schäfer
llncs



a4paper,hmargin=3.5cm,top=3cm,nohead,bottom=3.2cm,nohead


fancy



 




 


















       

OMScmsymn











arrows,automata,positioning








positioning,chains,fit,shapes,calc



































rtheorem[3][]
#1#2 #3.#2 #3 (#1)



       

OMScmsymn



⌊⌋



x[1]>p#1






P. Kleer G. Schäfer 


  Centrum Wiskunde & Informatica (CWI), Networks and Optimization Group 

  Vrije Universiteit Amsterdam, Department of Econometrics and Operations Research 
 Amsterdam, The Netherlands 
 
  kleer@cwi.nl, schaefer@cwi.nl





Tight Inefficiency Bounds for Perception-Parameterized Affine Congestion Games
    Pieter Kleer1 Guido Schäfer1,2
    December 30, 2023
==============================================================================






Congestion games constitute an important class of non-cooperative games which was introduced by Rosenthal in 1973. In recent years, several extensions of these games were proposed to incorporate aspects that are not captured by the standard model. Examples of such extensions include the incorporation of risk sensitive players, the modeling of altruistic player behavior and the imposition of taxes on the resources. These extensions were studied intensively with the goal to obtain a precise understanding of the inefficiency of equilibria of these games. 

In this paper, we introduce a new model of congestion games that captures these extensions (and additional ones) in a unifying way. The key idea here is to parameterize both the perceived cost of each player and the social cost function of the system designer. Intuitively, each player perceives the load induced by the other players by an extent of ρ≥ 0, while the system designer estimates that each player perceives the load of all others by an extent of σ≥ 0.
The above mentioned extensions reduce to special cases of our model by choosing the parameters ρ and σ accordingly. As in most related works, we concentrate on congestion games with affine latency functions here. 

Despite the fact that we deal with a more general class of congestion games, we manage to derive tight bounds on the price of anarchy and the price of stability for a large range of parameters. Our bounds provide a complete picture of the inefficiency of equilibria for these perception-parameterized congestion games. As a result, we obtain tight bounds on the price of anarchy and the price of stability for the above mentioned extensions. Our results also reveal how one should “design” the cost functions of the players in order to reduce the price of anarchy. Somewhat counterintuitively, if each player cares about all other players to the extent of 0.625 only (instead of 1 in the standard setting) the price of anarchy reduces from 2.5 to 2.155 and this is best possible.







§ INTRODUCTION


Congestion games constitute an important class of non-cooperative games which was introduced by Rosenthal in 1973 <cit.>. In a congestion game, we are given a set of resource from which a set of players can choose. Each resource is associated with a cost function which specifies the cost of this resource depending  on the total number of players using it. Every player chooses a subset of resources (from a set of resource subsets available to her) and experiences a cost equal to the sum of the costs of the chosen resources. 

Congestion games are both theoretically appealing and practically relevant. For example, they have applications in network routing, resource allocation and scheduling problems.

Rosenthal <cit.> proved that every congestion game has a pure Nash equilibrium, i.e., a strategy profile such that no player can decrease her cost by unilaterally deviating to another feasible set of resources. 
This result was established through the use of an exact potential function (known as Rosenthal potential) satisfying that the cost difference induced by a unilateral player deviation is equal to the potential difference of the respective strategy profiles. In fact, Monderer and Shapley <cit.> showed that the class of games admitting an exact potential function is isomorphic to the class of congestion games. 

One of the main research directions in algorithmic game theory focusses on quantifying the inefficiency caused by selfish behavior. The idea is to assess the quality of a Nash equilibrium relative to an optimal outcome. Here the quality of an outcome is measured in terms of a given social cost objective (e.g., the sum of the costs of all players). Koutsoupias and Papadimitriou <cit.> introduced the price of anarchy as the ratio between the worst social cost of a Nash equilibrium and the social cost of an optimum. Anshelevich et al. <cit.> defined the price of stability as the ratio between the best social cost of a Nash equilibrium and the social cost of an optimum. 



In recent years, several extensions of Rosenthal's congestion games were proposed to incorporate aspects which are not captured by the standard model. For example, these extensions include risk sensitivity of players in uncertain settings <cit.>, altruistic player behavior <cit.> and congestion games with taxes <cit.>. We elaborate in more detail on these extensions in Section <ref>. These games were studied intensively with the goal to obtain a precise understanding of the price of anarchy.

In this paper, we introduce a new model of congestion games, which we term perception-parameterized congestion games, that captures all these extensions (and more) in a unifying way. The key idea here is to parameterize both the perceived cost of each player and the social cost function. Intuitively, each player perceives the load induced by the other players by an extent of ρ≥ 0, while the system designer estimates that each player perceives the load of all others by an extent of σ≥ 0.
The above mentioned extensions reduce to special cases of our model by choosing the parameters ρ and σ accordingly. 

Despite the fact that we deal with a more general class of congestion games, we manage to derive tight bounds on the price of anarchy and the price of stability for a large range of parameters. Our bounds provide a complete picture of the inefficiency of equilibria for these perception-parameterized congestion games. As a consequence, we obtain tight bounds on the price of anarchy and the price of stability for the above mentioned extensions. While the price of anarchy bounds are (mostly) known from previous results, the price of stability results are new. 
As in <cit.>, we focus here on congestion games with affine cost functions.[Conceptually, our model can easily be adapted to more general latency functions; only the derivation of the respective bounds is analytically much more involved.]

We illustrate our model by means of a simple example; formal definitions of our perception-parameterized congestion games are given in Section <ref>. Suppose we are given a set of m resources and that every player has to choose precisely one of these resources. The cost of a resource e ∈ [m][Given a positive integer m, we use [m] to refer to the set {1, …, m}.] is given by a cost function c_e that maps the load on e to a real value. In the classical setting, the load of a resource e is defined as the total number of players x_e using e. That is, the cost that player i experiences when choosing resource e is c_e(x_e). In contrast, in our setting players have different perceptions of the load induced by the other players. More precisely, the perceived load of player i choosing resource e is 1+ ρ(x_e - 1), where ρ≥ 0 is a parameter. Consequently, the perceived cost of player i for choosing e is c_e(1+ ρ(x_e - 1)). Note that as ρ increases players care more about the presence of  other players.[In general, the parameter ρ can be player- or resource-specific, but in this work we concentrate on the homogenous case (i.e., all players have the same perception parameter).] In addition, we introduce a similar parameter σ≥ 0 for the social cost objective. Intuitively, this can be seen as the system designer's estimate of how each player perceives the load of the other players. In our example, the social cost is defined as ∑_e ∈ [m] c_e(1+σ(x_e-1)) x_e.



  
Our Results. In Section <ref>, we prove a bound of

    max{ρ + 1, 2ρ(1 + σ) + 1/ρ + 1}

on the price of anarchy of affine congestion games for a large range or parameters (ρ,σ) (see also Figure <ref> for an illustration). For general affine congestion games we prove that this bound is tight. Further, even for the special case of symmetric network congestion games we show that the bound (2ρ(1+σ)+1)/(ρ + 1) is asymptotically tight (on the range for which it is attained). 

In Section <ref>, we give a bound of

    √(σ(σ+2)) + σ/√(σ(σ+2)) + ρ - σ

on the price of stability of affine congestion games for a large range or pairs (ρ,σ) (see below for details). For general affine congestion games we show that this bound is tight. For symmetric network congestion games we give a better (tight) bound on the price of stability for the case σ = 1 and ρ≥ 0 arbitrary (details are given in Section <ref>). 




An overview of the price of anarchy and the price of stability results that we obtain from (<ref>) and (<ref>) for several applications known in the literature is given in Table <ref>. The respective references where these bounds were established first are given in the rightmost column. The connection between these applications and our model is discussed in detail at the end of Section <ref>.

In light of the above bounds, we obtain an (almost) complete picture of the inefficiency of equilibria (parameterized by ρ and σ); for example, see Figure <ref> for an illustration of the price of anarchy if σ = 1. Note that the price of anarchy decreases from 5/2 for ρ = 1 to 2.155 for ρ = h(1) ≈ 0.625.[The price of anarchy for ρ = h(1) was first established by Caragiannis et al. <cit.>. However, our bounds reveal that the price of anarchy is infact minimized at ρ = h(1) (see also Figure <ref>).] We refer the reader to Section <ref> for further remarks and discussions of the results. 






§ OUR MODEL, APPLICATIONS AND RELATED WORK
 

We first formally introduce our model of congestion games with parameterized perceptions. We then show that our model subsumes several other models that were studied in the literature as special cases. 



  
Congestion Games. 

A congestion game Γ is given by a tuple (N,E,(𝒮_i)_i∈ N,(c_e)_e∈ E) where N = [n] is the set of players, E the set of resources (or facilities), 𝒮_i ⊆ 2^E the set of strategies of player i, and c_e : _≥ 0→_≥ 0  the cost function of facility e. Given a strategy profile s = (s_1,…,s_n) ∈×_i 𝒮_i, we define x_e as the number of players using resource e, i.e., x_e = x_e(s) = |{i ∈ N : e ∈ s_i}|. 
If 𝒮_i = 𝒮_j for all i,j ∈ N, the game is called symmetric. For a given graph G = (V,E), we call Γ a (directed) network congestion game if for every player i there exist s_i,t_i ∈ V such that 𝒮_i is the set of all (directed) (s_i,t_i)-paths in G. 
An affine congestion game has cost functions of the form c_e(x) = a_ex + b_e with a_e,b_e ≥ 0. If b_e = 0 for all e ∈ E, the game is called linear. 



  
Our Model.
We introduce our unifying model of perception-parameterized congestion games with affine latency functions.
For a fixed parameter ρ≥ 0, we define the cost of player i ∈ N by  

    C_i^ρ(s) = ∑_e ∈ s_i c_e(1 + ρ(x_e - 1)) = a_e[1 + ρ(x_e-1)] + b_e

for a given strategy profile s = (s_1,…,s_n). For a fixed parameter σ≥ 0, the social cost of a strategy profile s is given by 

    C^σ(s) = ∑_i C_i^σ(s) = ∑_e ∈ Ex_e(a_e[1 + σ(x_e-1)] + b_e).

 We refer to the case ρ = σ = 1 as the classical congestion game with cost functions c_e(x) = a_e x + b_e for all e ∈ E.



  
Inefficiency of Equilibria. 

A strategy profile s is a Nash equilibrium if for all players i ∈ N it holds that C_i^ρ(s) ≤ C_i^ρ(s_i',s_-i) for all s_i' ∈𝒮_i, where (s_i',s_-i) denotes the strategy profile in which player i plays s_i' and all the other players their strategy in s. The price of anarchy (PoA) and price of stability (PoS) of a game Γ are defined as

    PoA(Γ,ρ,σ) = max_s ∈ NE C^σ(s)/min_s^* ∈×_i 𝒮_iC^σ(s^*)   and   PoS(Γ,ρ,σ) = min_s ∈ NE C^σ(s)/min_s^* ∈×_i 𝒮_iC^σ(s^*),

where NE = NE(ρ) denotes the set of Nash equilibria with respect to the player costs as defined in (<ref>). For a collection of games ℋ we define PoA(ℋ,ρ,σ) = sup_Γ∈ℋPoA(Γ,ρ,σ) and  PoS(ℋ,ρ,σ) = sup_Γ∈ℋPoS(Γ,ρ,σ).
Rosenthal <cit.> shows that classical congestion games (i.e., ρ = σ = 1) have an exact potential function: Φ : ×_i 𝒮_i → is an exact potential function for a congestion game Γ if for every strategy profile s, for every i ∈ N and every s'_i ∈𝒮_i:  Φ(s) - Φ(s_-i,s_i') = C_i(s) - C_i(s_-i,s_i'). The Rosenthal potential Φ(s) = ∑_e ∈ E∑_k=1^x_e c_e(k) is an exact potential function for classical congestion games. 



  
Applications.

We review various models that fall within, or are related to, the framework proposed above (for certain values of ρ and σ). These models sometimes interpret the parameters differently than explained above.

Altruism <cit.>. We can rewrite the cost of player i as

    C^ρ_i(s) = ∑_e ∈ s_i (a_ex_e + b_e) + (ρ - 1)a_e(x_e-1).

The term (ρ-1)a_e(x_e-1) can be interpreted as a “dynamic” (meaning load-dependent) tax that players using resource e have to pay.[In fact, for ρ = 2 this corresponds to the dynamic taxes as proposed in a technical report by Singh <cit.>.] 
For 1 ≤ρ≤∞ and σ = 1, this model is equivalent to the altruistic player setting proposed by Caragiannis et al. <cit.>. Chen et al. <cit.> also study this model of altruism for 1 ≤ρ≤ 2 and σ = 1. (The equivalence between the altruistic model and our model is proved in Lemma <ref> in the appendix.)

Constant taxes <cit.>. We can rewrite the cost of player i as 

    C^ρ_i(s) = ∑_e ∈ s_iρ a_e x_e + (1-ρ)a_e + b_e.

Now a strategy profile s is a Nash equilibrium if for every player i and every s'_i ∈𝒮_i

    ∑_e ∈ s_iρ a_e x_e + (1-ρ)a_e + b_e ≤∑_e ∈ s_i ∩ s_i'ρ a_e x_e + (1-ρ)a_e + b_e + ∑_e ∈ s_i'∖ s_iρ a_e (x_e+1) + (1-ρ)a_e + b_e.

Dividing by ρ gives that s is also a Nash equilibrium for the cost functions 

    T^ρ_i(s) = ∑_e ∈ s_i  a_e x_e  + b_e/ρ + ∑_e ∈ s_i1 - ρ/ρ a_e.

That is, s is a Nash equilibrium in a classical congestion game in which players take into account constant resource taxes of the form (1-ρ)/ρ· a_e. Caragiannis, Kaklamanis and Kanellopoulos <cit.> study this type of taxes, which they call universal tax functions, for ρ satisfying (1-ρ)/ρ = 3/2√(3) - 2. They consider these taxes to be refundable, i.e., they are not taken into account in the social cost, which is equivalent to the case σ = 1. Note that the function τ: (0,1] → [0,∞) defined by τ(ρ) = (1-ρ)/ρ is bijective.[This relation between altruism (or spite) and constant taxes is also mentioned by Caragiannis et al. <cit.>.]

Risk sensitivity under uncertainty <cit.>. Nikolova, Piliouras and Shamma <cit.> consider congestion games in which there is a (non-deterministic) order of the players on every resource. A player is only affected by players in front of her. That is, the load on resource e for player i in a strict ordering r, where r_e(i) denotes the position of player i, is given by x_e(i) = |{j ∈ N : r_e(j) ≤ r_e(i)}|. The cost of player i is then C_i(s) = ∑_e ∈ s_i c_e(x_e(i)). Note that x_e(i) is a random variable if the ordering is non-deterministic. The social cost of the model is defined by the sum of all player costs, 

    C^1/2(s) = ∑_e ∈ E a_e x_e(x_e+1)/2 + b_e

which is independent of the ordering r. (This holds because in every ordering there is always one player first, one player second, and so on.) Note that the social cost corresponds to the case σ = 1/2 in our framework. Nikolova et al. <cit.> study various risk attitudes towards the ordering r that is assumed to have a uniform distribution over all possible orderings. The two relevant attitudes are that of risk-neutral players and players applying Wald's minimax principle. Risk-neutral players define their cost as the expected cost under the ordering r, which correspond to the case ρ = 1/2 in (<ref>). This can roughly be interpreted as that players expect to be scheduled in the middle on average. Wald's minimax principle implies that players assume a worst-case scenario, i.e., being scheduled last on all the resources. This corresponds to the case ρ = 1.

Approximate Nash equilibria <cit.>. Suppose that s is a Nash equilibrium under the cost functions defined in (<ref>). Then, in particular, we have

    C^1_i(s) ≤ C^ρ_i(s) ≤ C^ρ_i(s_i', s_-i) ≤ρ C^1_i(s_i', s_-i)

for any player i and s_i' ∈𝒮_i and ρ≥ 1. That is, we have C^1_i(s) ≤ρ· C^1_i(s_i', s_-i) which means that the strategy profile s is a ρ-approximate equilibrium, as studied by Christodoulou, Koutsoupias and Spirakis <cit.>. In particular, this implies that any upper bound on the price of anarchy, or price of stability, in our framework yields an upper bound on the price of stability for ρ-approximate equilibria for the same class of games.



Generalized affine congestion games. Let 𝒜' denote the class of all congestion games Γ for which all resources have the same cost function c(x) = a x + b, where  a = a(Γ) and b = b(Γ) satisfy a ≥ 0 and a+b > 0. The class of affine congestion games with non-negative coefficients is contained in 𝒜' since every such game can always be transformed[This transformation can be done in such a way that both PoA and PoS of the game do not change. For a proof the reader is referred to, e.g., <cit.>.] into a game Γ' with a_e = 1 and b_e = 0 for all resources e ∈ E', where E' is the resource set of Γ'.

Without loss of generality  we can assume that a + b = 1, since the cost functions can be scaled by 1/(a+b). The cost functions of  Γ∈𝒜' can then equivalently be written as c(x) = ρ x + (1 - ρ) for ρ≥ 0. This is precisely the definition of C^ρ_i(s) (with a_e = 1 and b_e = 0 taken there). In particular, if we take σ = ρ, meaning that C^ρ(s) = ∑_i ∈ N C^ρ_i(s), we have

    PoA(𝒜') = sup_ρ≥ 0 PoA(𝒜,ρ,ρ)
      and  PoS(𝒜') = sup_ρ≥ 0 PoS(𝒜,ρ,ρ),

where 𝒜 denotes the class of affine congestion games with non-negative coefficients.

Due to page limitations some material is omitted from the main text below and can be found in the appendix. 




§ PRICE OF ANARCHY


In this section we derive an upper bound on the price of anarchy for affine congestion games of

    max{ρ + 1, 2ρ(1 + σ) + 1/ρ + 1}

for a wide range of pairs (ρ,σ) that captures all known (to us) price of anarchy results in the literature that fall within our model. We show that this bound is tight for general congestion games. We also show that the bound (2ρ(1 + σ) + 1)/(ρ + 1) is (asymptotically) tight for symmetric network congestion games, for the range of (ρ,σ) on which it is attained. 


We need the following technical result for the proof of the main result in Theorem <ref>: 

 
Let s be a Nash equilibrium under the cost functions C_i^ρ(s) and let s^* be a minimizer of C^σ(·). For ρ, σ≥ 0 fixed, if there exist α(ρ,σ), β(ρ,σ) ≥ 0 such that

    (1 + ρ· x)y - ρ(x - 1)x - x ≤ - β(ρ,σ)(1 + σ(x - 1))x + α(ρ,σ)(1 + σ(y - 1))y

for all non-negative integers x and y, then β(ρ,σ) C^σ(s) ≤α(ρ,σ) C^σ(s^*).




Let s be a Nash equilibrium under the cost functions C_i^ρ(s) and let s^* be a minimizer of C^σ(·). Then

    C^σ(s)/C^σ(s^*)≤2ρ(1 + σ) + 1/ρ + 1



  * if 1/2≤σ≤ρ≤ 2σ,

  * if σ = 1 and h(σ) ≤ρ≤ 2 σ,

where h(σ) = g(1 + σ + √(σ(σ + 2)), σ) is the optimum of the function

    g(a,σ) = σ(a^2 - 1)/(1 + σ)a^2 - (2σ + 1)a + 2σ(σ+1).

Furthermore, there exists a function Δ = Δ(σ) (specified in the appendix) satisfying for every fixed σ_0 ≥ 1/2: if Δ(σ_0) ≥ 0, then (<ref>) is true for all h(σ_0) ≤ρ≤ 2σ_0. 

 For the functions α(ρ,σ) = (2ρ(1+σ)+1)/(1+2σ) and β(ρ,σ) = (1+ρ)/(1+2σ), we prove the inequality in Lemma <ref>. We show that, for certain functions f_1 and f_2, the smallest ρ satisfying the inequality of Lemma <ref> is given by the quantity

    h(σ) = sup_x,y ∈: f_1(x,y,σ) > 0 - f_2(x,y,σ)/f_1(x,y,σ).

We divide the set (x,y) ∈× in lines of the form x = ay and determine the supremum over every line.  After that we take the supremum over all lines, which then gives the desired result. We first show that the case x ≤ y which is trivial. We then focus on y > x. In this case we want to determine

    h(σ) = sup_a  ∈_> 1sup_ y > 1 - f_2(ay,y,σ)/f_1(ay,y,σ).

We show that h(σ) = max{γ_1(σ),γ_2(σ)} for certain functions γ_1 and γ_2. Numerical experiments suggest that Δ(σ) := γ_1(σ) - γ_2(σ) ≥ 0, that is, the maximum is always attained for γ_1 (which is the definition of h given in the statement of the theorem). In particular, this means that if, for a fixed σ, the non-negativity of Δ(σ) is checked, then the proof indeed yields the inequality of Lemma <ref> for h(σ) ≤ρ≤ 2σ. 

Numerical experiments suggest that Δ(σ) is non-negative for all σ≥ 1/2.

We emphasize that for a fixed σ, with Δ(σ) ≥ 0, the proof that the inequality holds for all h(σ) ≤ρ≤ 2σ is exact in the parameter ρ. The first two cases of Theorem <ref> capture all the price of anarchy results from the literature. 

We next show that the bound of Theorem <ref> is also an (asymptotic) lower bound for linear symmetric network congestion games.[In the appendix (Theorem <ref>) we show (non-asymptotic) tightness for general congestion games.] This improves a result in the risk-uncertainty model of Piliouras et al. <cit.>, who only prove asymptotic tightness for symmetric linear congestion games (for their respective values of ρ and σ). It also improves a result in the altruism model by Chen et al. <cit.>, who show tightness only for general congestion games. The proof is a generalization of the construction of Correa et al. <cit.>, who proved that for the classical case ρ = σ = 1, the Price of Anarchy upper bound of 5/2, shown in <cit.>, is asymptotically tight for symmetric network congestion games.


For ρ, σ > 0 fixed, and players with cost functions C_i^ρ(s), there exist symmetric network linear congestion games such that

    C^σ(s)/C^σ(s^*)≥2ρ(1 + σ) + 1/ρ + 1 - ϵ

for any ϵ > 0, where s is a Nash equilibrium, and s^* a socially optimal strategy profile.


We construct a symmetric network linear congestion game with  n players. 
We first describe the graph topology used in the proof of Theorem 5 in <cit.> (using similar notation and terminology). 
The graph G consists of n principal disjoint paths, called P_1,…,P_n from s to t (horizontal paths in Figure <ref>), each consisting 2n-1 arcs (and hence 2n nodes). With e_i,j the j-th arc on path i is denoted for i = 1,…,n and j = 1,…,2n-1. Also, v_i,j denotes the j-th node on path i for i = 1,…,n and j = 1,…,2n. There are also n(n-1) connecting arcs: for every path i there is an arc (v_i,2k+1, v_i-1,2k) for k = 1,…,n-1, where i - 1 is taken modulo n (the diagonal arcs in Figure <ref>). For j ≥ 1 fixed, we say that the arcs e_i,j for i = 1,…,n form the (j-1)-th layer of G (see Figure <ref>).



The cost functions are as follows. All arcs leaving s (the arcs e_i,1 for i = 1,…,n) and all arcs entering t (the arcs e_i,2n for i = 1,…,n) have latency c_e(x) = (1+ρ)x. For all i = 1,…,n, the arcs e_i,2k-1 for k = 1,…,n-1 have cost function c_e(x) = ρ x, whereas the arcs e_i,2k for k = 1,…,n-2 have cost function c_e(x) = x. All other arcs (the diagonal connecting arcs) have cost zero. 

The feasible strategy profile t in which player i uses principal path P_i, for all i = 1,…,n has social cost C^σ(t) = n(2(1+ρ) + (n-1)ρ + (n-2)) = n((1+ρ)n +ρ). A Nash equilibrium is given by the strategy profile in which every player k uses the following path: she starts with arcs e_k,1 and e_k,2, then uses all arcs of the form e_k+j,2j, e_k+j,2j+1, e_k+j,2j+2 for j = 1,…,n-1, and ends with arcs e_k+n-1,2n-2, e_k+n-1,2n-1 (and uses all connecting arcs in between).[This is similar to the construction in Theorem 5 <cit.>.] Note that all the (principal) arcs of layer j have load 1 is j is even, and load 2 if j is odd. The social cost of this profile is given by
C^σ(s) = n(2(1+ρ) + (n-1) · 2 ·ρ(1+σ(2-1)) + n-2) = n((1+2ρ(1+σ))n - 2ρσ). It follows that C^σ(s)/C^σ(t) ↑ (1+2ρ(1+σ))/(1+ρ) as n →∞. We now show that the above mentioned strategy profile s is indeed a Nash equilibrium. 

Fix some player, say player 2, as in Figure <ref>, and suppose that this player deviates to some path Q. Let j be the first layer in which P_2 and Q overlap. Note that j must be odd. The cost C_2^ρ(s) of player 2, on the subpath of P_2 leading to the first overlapping arc with Q, is at most

    (1+ρ) + j-1/2· [2·[ρ(1 + ρ(2-1))] + 1] + ρ(1 + ρ(2-1)) =(1+ρ)^2 + j-1/2(1 + 2ρ(1+ρ))

The subpath of Q leading to the first overlapping arc with P_2 has C^ρ_i(Q,s_-i) as follows. She uses at least one arc in every odd layer (before the overlapping layer) with a load of 3 and one arc of every even layer (before the overlapping arc) with load 2, meaning that the cost of player i on the subpath of Q is at least

    (1+ρ)(1+ρ(2 - 1)) + j-1/2· [(ρ(1 + ρ(3-1))) + (1 + ρ(2-1))] = (1+ρ)^2 + j-1/2· (2ρ + 1)(1+ρ)

Since 1 + 2ρ(1+ρ) < (2ρ+1)(1+ρ) for all ρ≥ 0, if follows that the cost of player i on the subpath of P_2 is no worse than that of the subpath of Q, when player 2 deviates from P_2 to Q. If follows that it suffices to show that P_2 is an equilibrium strategy in s with respect to deviations Q that overlap on the first arc e_2,1 with P_2. A similar argument shows that it also suffices to look at deviations Q for which Q and P_2 overlap on the last arc e_2,2n-1 of P_2.

Now suppose that P_2 and Q do not overlap on some internal part of P_2. Note that the first arc of Q that is not contained in P_2, say (v_1,w_1) must be in an even layer, and also that the last arc, say (v_2,w_2) (which is a connecting arc) is in an odd layer (note that v_1 ≠ s and w_2 ≠ t w.l.o.g. by what is said in the previous paragraph). It is not hard to see that the subpath of Q from v_1 to w_2 contains the same number of even-layered arcs as the subpath of P_2, and the same number of odd-layered arcs as the subpath of P_2. However, the load on all the odd-layered arcs on the subpath of deviation Q is 3, whereas the load on odd-layered arcs in the subpath of P_2 between v_1 and w_2 (in strategy s) is 2. Similarly, the load on every even-layered arc on the subpath of deviation Q is 2, whereas the load on ever even-layered arc in the subpath of P_2 is 1. Hence the subpath of deviation Q between v_1 and w_2 can never be profitable. 


For ρ≥ 2σ, we can obtain a tight bound of ρ + 1 on the price of anarchy. Remarkably, the bound itself does not depend on σ, only the range of ρ and σ for which it holds. For the parameters σ = 1 and ρ≥ 2 in the altruism model of Caragiannis et al. <cit.>, this bound is known to be tight for non-symmetric singleton congestion games (where all strategies consist of a single resource). We only provide tightness for general congestion games, but the construction is significantly simpler.


Let s be a Nash equilibrium under the cost functions C_i^ρ(s) and let s^* be a minimizer of C^σ(·). Then
C^σ(s)/C^σ(s^*) ≤ρ + 1 for 1 ≤ 2σ≤ρ. Furthermore, this bound is tight.









§ PRICE OF STABILITY
 
In this section we give a tight bound for the price of stability of 

    √(σ(σ+2)) + σ/√(σ(σ+2)) + ρ - σ

for a large range of pairs (ρ,σ). 

We show this bound to be (asymptotically) tight. 

We need the following technical lemma.


For all non-negative integers x and y, and σ≥ 0 arbitrary, we have

    (x - y + 1/2)^2- 1/4 + 2σ x(x - 1) + (√(σ(σ+2)) + σ)[y(y-1) - x(x-1)] ≥ 0.



 Let s be a best Nash equilibrium under the cost functions C_i^ρ(s) and let s^* be a minimizer of C^σ(·). We have

    C^σ(s)/C^σ(s^*)≤√(σ(σ+2)) + σ/√(σ(σ+2)) + ρ - σ

for all σ > 0 and

    2σ/1 + σ + √(σ(σ+2))≤ρ≤ 2σ.




An overview of the implications of this bound is given in Table <ref>. 
The bound of 2 for generalized affine congestion games requires some additional arguments (see appendix). 







Our proof is similar to a technique of Christodoulou, Koutsoupias and Spirakis <cit.> for upper bounding the price of stability of ρ-approximate equilibria (we elaborate on the conceptual difference in Section <ref>). However, for a general σ the analysis is more involved. The main technical contribution comes from establishing the inequality in Lemma <ref>.

We can write C^ρ_i(s) = a_e x_e + b_e + (ρ - 1)a_ex_e, which, by Rosenthal <cit.>, implies that

    Φ^ρ(s) := ∑_e ∈ E a_ex_e(x_e + 1)/2  + b_e x_e + (ρ - 1)∑_e ∈ E a_e(x_e - 1)x_e/2

is an exact potential for C^ρ_i(s). 

The idea of the proof is to combine the Nash inequalities, and the fact that the global minimum of Φ^ρ(·) is a Nash equilibrium (because it is an exact potential). Let s denote the global minimum of Φ^ρ, and s^* a socially optimal solution. We can without loss of generality assume that a_e = 1 and b_e = 0. The Nash inequalities (as in the price of anarchy analysis) yield

    ∑_e∈ E x_e(1 + ρ(x_e - 1)) ≤∑_e ∈ E (1+ρ x_e)x_e^*

whereas the fact that s is a global optimum of Φ^ρ(·) yields Φ^ρ(s) ≤Φ^ρ(s^*), which reduces to

    ∑_e ∈ Eρ x_e^2 + (2 - ρ)x_e ≤∑_e ∈ Eρ (x_e^*)^2 + (2 - ρ)x_e^*.

If we can find γ, δ≥ 0, and some K ≥ 1, for which

    ( 0 ≤)  γ[ ρ(x_e^*)^2 + (2 - ρ)x_e^* - ρ x_e^2 - (2 - ρ)x_e ] + δ[ (1+ρ x_e)x_e^* - x_e(1 + ρ(x_e - 1)]


    ≤ K · x_e^*[1 + σ(x_e^*-1)] - x_e[1 + σ(x_e-1)],

then this implies that C^σ(s)/C^σ(s^*) ≤ K. We take

    δ = K - 1/ρ     and     γ = (ρ - 1)K + 1/2ρ.

It is not hard to see that δ≥ 0 always holds, however, for γ we have to be more careful. We will later verify for which combinations of ρ and σ the parameter γ is indeed non-negative. Rewriting the expression in (<ref>) yields that we have to find K satisfying

    K ≥f_2(x_e,x_e^*,σ)/f_1(x_e,x_e^*,ρ,σ) :=  (x_e^*)^2 - 2x_ex_e^* + (1+2σ)x_e^2 - x_e^* + (1-2σ)x_e/[(1 - ρ + 2σ)(x_e^*)^2 - 2x_ex_e^* + (1+ρ)x_e^2 + (ρ - 1 - 2σ)x_e^* - (ρ - 1)x_e].

Note that this reasoning is only correct if f_1(x_e,x_e^*,ρ,σ) ≥ 0. This is true since 

    f_1(x_e,x_e^*,ρ,σ) = (x_e - x_e^* + 1/2)^2 - 1/4 + (2σ - ρ)x_e^*(x_e^*-1) + ρ x_e(x_e-1)

which is non-negative for all x_e,x_e^* ∈, σ≥ 0 and 0 ≤ρ≤ 2σ. Furthermore, the expression is zero if and only if (x_e,x_e^*) ∈{(0,1),(1,1)}, but for these pairs the nominator is also zero, and hence, the expression in (<ref>) is therefore satisfied for those pairs. We can write

    f_2(x_e,x_e^*,σ) = (x_e - x_e^* + 1/2)^2- 1/4 + 2σ x_e(x_e - 1)

and therefore f_2/f_1 = A/A + (2σ - ρ)B, where

    A = (x_e - x_e^* + 1/2)^2- 1/4 + 2σ x_e(x_e - 1),     B =  x_e^*(x_e^*-1) - x_e(x_e-1).

Note that if ρ = 2σ, we have f_2/f_1 = 1, and hence we can take K = 1. Otherwise,

    A/A + (2σ - ρ)B≤√(σ(σ+2)) + σ/√(σ(σ+2)) + ρ - σ =: K    ⇔   A + (√(σ(σ+2))+σ)B ≥ 0

The inequality on the right is true by Lemma <ref>.

To finish the proof, we determine the pairs (ρ,σ) for which the parameter γ is non-negative. This holds if and only if

    (ρ - 1)K + 1 = (ρ - 1)√(σ(σ+2)) + σ/√(σ(σ+2)) + ρ - σ + 1 ≥ 0.

Rewriting this yields the bound on ρ in the statement of the theorem. 



In the next theorem we provide a lower bound on the price of stability for arbitrary non-negative pairs (ρ,σ). The proof is similar to a construction of Christodoulou et al. <cit.> used to give a lower bound on the price of stability for ρ-approximate equilibria. The key difference is to tune the parameters α, β in the proof with respect to the Nash definition based on the cost function C_i^ρ(·), rather than the ρ-approximate Nash definition.


Let ρ, σ > 0 fixed, with ρ < 2σ, and ϵ > 0 arbitrary. Then there exists a linear congestion game, with player cost functions C_i^ρ(s), such that

    C^σ(s)/C^σ(s^*)≥√(σ(σ+2)) + σ/√(σ(σ+2)) + ρ - σ - ϵ.

Here, s is a best Nash equilibrium, and s^* a social optimum.


We describe the construction of Theorem 9 <cit.> using similar notation. We have a game of n = n_1 + n_2 players divided into two sets G_1 and G_2 with size resp. n_1 and n_2. Each player i ∈ G_1 has two strategies: A_i and P_i. The players in G_2 have a unique strategy D. The strategy profile A = (A_1,…,A_n_1,D,…,D) will be the unique Nash equilibrium, and the strategy profile P = (P_1,…,P_n_1,D,…,D) will be the social optimum. We have three types of resources:


  * n_1 resources α_i, i = 1,… n_1, with cost function c_α_i(x) = α x. The resource α_i only belongs to strategy P_i.

  * n_1(n_1 - 1) resources[The proof of Theorem 9 <cit.> contains a typo here: it says there are n(n-1) resources of this type, instead of n_1(n_1-1).] β_ij, i,j = 1,…,n_1 with i ≠ j, with cost function c_β_ij(x) = β x. The resource β_ij belongs only to strategies A_i and P_j.

  * One resource γ with cost function c_γ(x) = x, that belongs to A_i for i = 1,…, n_1 and to D.


The idea is to set the parameters α and β in such a way that A becomes the unique Nash equilibrium. For any strategy profile s, there are k players playing strategy A_i and n_1 - k players playing strategy P_i in the set G_1, for some 0 ≤ k ≤ n_1. By symmetry, it then suffices to look at profiles S_k = (A_1,…,A_k,P_k+1,…,P_n_1,D,…,D) for 0 ≤ k ≤ n_1. Furthermore, the first k players playing A_i all have the same cost, and also, the n_1 - k players playing P_i have the same cost. We can therefore focus on the costs of player 1, denoted by C^ρ_A(k), and that of player n_1, denoted by C^ρ_P(k). We have

    C^ρ_A(k)    =    β (k-1) + β (1 + ρ(2-1))(n_1 - k) + 1 + ρ(n_2+k - 1) 
       =    (β - β(1+ρ) + ρ)k + (-β + β(1+ρ)n_1 + 1 + ρ(n_2 - 1)) 
       =   ρ(1 - β)· k + (1 - β - ρ) + β(1+ρ)n_1 + ρ n_2

and

    C^ρ_P(k)    =    α + β (n_1 - 1 - k)+ β(1 + ρ(2-1))k 
       =   βρ· k + α + β(n_1 - 1)

 
We can set the parameters α and β such that C^ρ_A(k) = C^ρ_P(k-1), meaning that S_k is a Nash equilibrium for every k (we will create a unique Nash equilibrium in a moment), that is we take

    ρ(1-β) = βρ    and    (1 - β - ρ) + β(1+ρ)n_1 + ρ n_2 = α + β(n_1 - 1) - βρ

Note that the -βρ term on the far right of the second equation comes from the fact that we evaluate C^ρ_P(·) in k-1 (remember that k denotes the number of players playing strategy A_i, so if a player would switch to P_i this number decreases by 1). Solving the left equation leads to β = 1/2. Inserting this in the right equation, and solving for α, gives 

    α = ρ( n_1/2 + n_2 - 1/2) + 1.

We emphasize that α, β > 0 for all ρ≥ 0. In order to make A the unique Nash equilibrium, we can slightly increase α such that we get C^ρ_A(k) < C^ρ_P(k-1)
for all k (which means that A_i is a dominant strategy for player i). Note that this increase in α can be arbitrary small.
We have

    C^σ(A)/C^σ(P) = n_1[1 + σ(n_1+n_2 - 1) + 1/2(n_1 - 1)] + n_2[1 + σ(n_1+n_2 - 1)]/n_1[ρ(n_1 + 1/2 + n_2 - 1) + 1 + 1/2(n_1-1) ] + n_2[1 + σ(n_2 - 1)]

Inserting n_2 = a · n_1 for some rational a > 0, and sending n_1 →∞ gives a lower bound of

    f(a) = 2σ(1+a)^2 + 1/ρ(1+2a) + 1 + 2σ a^2

on the price of stability. Optimizing over a > 0 (this only works if ρ < 2σ) gives a^* = -1/2 + √(1/4 + 1/2σ) and f(a^*) then yields the bound in the statement of the theorem. 





§ REMARKS AND ADDITIONAL INSIGHTS


We discuss the results of Sections <ref> and <ref> for the applications mentioned in Section <ref> and obtain some additional application-specific insights and results. We conclude this section by showing that the price of stability results are not tight for the special case of symmetric network congestion games (as opposed to the price of anarchy results, which are tight for this class). 





Altruism <cit.>.  For σ = 1, we see that the resulting bound (4ρ+1)/(ρ+1) is increasing in ρ. Especially in the context of altruism or taxes, this is not desirable. A natural question to ask is therefore if there exist collections ℋ for which the price of anarchy is non-increasing as a function of ρ. 

The next theorem gives a sufficient condition for a class of instances to have the property of non-increasing price of anarchy, which can be interpreted as follows. For ρ = 2, it can be shown that the social optimum becomes a Nash equilibrium  under the player cost function C^ρ_i(s), which implies that the price of stability is 1. Nevertheless, it might happen that  worse Nash equilibria arise as well. The condition PoA(ℋ,2,1) = 1 states that this does not happen, and even stronger, that all Nash equilibria of the game for ρ = 2 become social optima (it is said that the social optimum is strongly enforceable).

Let ℋ be a collection of congestion games. If PoA(ℋ,2,1) = 1, then PoA(ℋ,ρ,1) is a non-increasing function for 1 ≤ρ≤ 2.

In a technical report, Singh <cit.> shows that the social optimum is strongly enforceable for symmetric network congestion games on series-parallel graphs. We can therefore conclude that the (altruistic) price of anarchy will be a non-increasing function of ρ. This is a remarkable result since, to the best of our knowledge, the classical price of anarchy is unknown (the best lower bound is given by Fotakis <cit.>). 


Constant taxes <cit.>. Caragiannis et al. <cit.> showed that the price of anarchy can be decreased to 2.155 by the usage of universal tax functions (see also Section 1 and Figure <ref>), which improves significantly the classical bound of 2.5. However, the price of stability increases from 1.577 (for classical games) to 2.013, for this specific set of tax functions.  Furthermore, from Theorem 3.7 <cit.> it follows that the price of anarchy can never be better than 2.155 for 0 ≤ρ≤ h(1). In Theorem <ref> we even show that the price of anarchy goes to infinity as ρ→ 0.

Risk sensitivity under uncertainty <cit.>. We do not only re-obtain the price of anarchy results for risk-neutral players and players applying Wald's minimax principle (worst-case players), but our results also give a tight bound for any convex combination (in terms of player costs) of risk-neutral and worst-case risk attitudes. Furthermore, we also obtain tight price of stability results for this model.

Approximate Nash equilibria <cit.>. For σ = 1 and 1 ≤ρ≤ 2, we obtain a bound of (√(3) + 1)/(√(3) + ρ - 1) on the price of stability. In particular, this also yields the same bound on the price of stability for ρ-approximate equilibria. This bound was previously obtained by Christodoulou et al. <cit.>. Conceptually our approach is different since we obtain correctness of the bound through the observation that every Nash equilibrium in our framework yields an approximate equilibrium. In particular, this immediately yields a potential function  that can be used to carry out the technical details (namely the potential function that is exact for our congestion game). Nevertheless, the framework of Christodoulou et al. <cit.> is somewhat more general and might be used to obtain a tight bound for the price of stability of approximate equilibria (which is not known to the best of our knowledge).



 §.§ Price of stability for symmetric network congestion games

The price of anarchy bound of (1+2ρ(1+σ))/(1 + ρ) obtained in Section <ref> is tight even for symmetric network congestion games with linear cost functions, as was shown in Theorem <ref>. This is not true for the price of stability, which we will show here for the case σ = 1.






 Let Γ be a linear symmetric network congestion game, then 

    PoS(Γ, ρ, 1) ≤{[     4/(ρ(4-ρ))   if  0  ≤ρ≤ 1;        4/(2+ρ)   if  1  ≤ρ≤ 2;        (2+ρ)/4 if  2  ≤ρ  < ∞ ].

In particular, if Γ is a symmetric congestion game on an extenstion-parallel[A graph G is extension parallel if it consists of either (i) a single edge, (ii) a single edge and an extension-parallel graph composed in series, (iii) two extension-parallel graphs composed in parallel.] graph G, then the upper bounds even hold for the price of anarchy. All bounds are tight.

For ρ≥ 1, the bounds were previously shown by Caragiannis et al. <cit.> for the price of anarchy of singleton symmetric congestion games (which can be modeled on an extension-parallel graph).

Since any Nash equilibrium under the player cost C_i^ρ(·) is in particular a ρ-approximate Nash equilibrium, we also obtain the following result.
 

The price of stability for ρ-approximate equilibria, with 1 ≤ρ≤ 2, is upper bounded by 4/(2+ρ) for linear symmetric network congestion games.




Acknowledgements. We thank the anonymous referees for useful comments and one referee in particular for very detailed suggestions and pointing out important typos.

splncs03







§ OMITTED MATERIAL OF SECTION <REF>

The following lemma shows the equivalence between dynamic taxes and altruistic players.

For 1 ≤ρ≤ 2, a strategy profile s  ∈×_i 𝒮_i is a Nash equilibrium under the cost

    C_i^ρ(s) = ∑_e ∈ s_i c_e(x_e) + (ρ - 1) ∑_e ∈ s_i (x_e - 1)[c_e(x_e) - c_e(x_e-1)]
 if and only if it is a Nash equilibrium under the altruistic cost 

    𝒜_i^ρ(s) = (2 - ρ) C^0_i(s) + (ρ - 1) C^0(s)




Let s be a Nash equilibrium under the perceived costs 𝒜_i^γ(s), and let s^* be any other strategy profile. Furthermore, define γ = ρ - 1. Leaving out all the resources that are not in the symmetric difference[Resources used by at most on strategy.] of s_i and s_i^* (for the social cost term), we find that the Nash condition is equivalent to

    (1 - γ)∑_e ∈ s_i ∖ s_i^* c_e(x_e)  + γ( ∑_e ∈ s_i ∖ s_i^* x_ec_e(x_e) +  ∑_e ∈ s_i^* ∖ s_i x_ec_e(x_e))    ≤   (1 - γ)∑_e ∈ s_i^* ∖ s_i c_e(x_e + 1)   
           +  γ∑_e ∈ s_i ∖ s_i^* (x_e - 1)c_e(x_e - 1)  
           +  γ∑_e ∈ s_i^* ∖ s_i (x_e + 1)c_e(x_e + 1)

which is equivalent to

    ∑_e ∈ s_i ∖ s_i^* c_e(x_e)  + γ∑_e ∈ s_i ∖ s_i^* (x_e - 1)[c_e(x_e) - c_e(x_e - 1)] ≤∑_e ∈ s_i^* ∖ s_i c_e(x_e + 1) +  γ∑_e ∈ s_i^* ∖ s_i x_e[c_e(x_e + 1) - c_e(x_e)]

which is equivalent to C_i^γ(s) ≤C_i^γ(s_-i,s_i^*) since the terms for e ∈ s_i ∩ s_i^* do not change. 



§ OMITTED MATERIAL OF SECTION <REF>

Lemma<ref>
Let s be a Nash equilibrium under the cost functions C_i^ρ(s) and let s^* be a minimizer of C^σ(·). For ρ, σ≥ 0 fixed, if there exist α(ρ,σ), β(ρ,σ) ≥ 0 such that

    (1 + ρ· x)y - ρ(x - 1)x - x ≤ - β(ρ,σ)(1 + σ(x - 1))x + α(ρ,σ)(1 + σ(y - 1))y

for all non-negative integers x and y, then

    C^σ(s)/C^σ(s^*)≤α(ρ,σ)/β(ρ,σ).



Without loss of generality, we may assume that a_e = 1 and b_e = 0. We then have

    ∑_i C_i^ρ(s)    =   ∑_e ρ (x_e - 1)x_e + ∑_e x_e 
       =   ∑_e ρ [1 - σ + σ](x_e - 1)x_e +ρ x_e - ρ x_e + ∑_e x_e 
       =   ρ∑_e [1 + σ(x_e - 1)]x_e + ρ∑_e (1 - σ)(x_e-1)x_e - x_e + ∑_e x_e 
       =   ρ C^σ(s) + ρ∑_e (1 - σ)(x_e-1)x_e + (1 - ρ) ∑_e x_e.
 Rewriting this, we find

    ρ· C^σ(s)    =    ∑_i C_i^ρ(s) + ρ(σ - 1)∑_e (x_e-1)x_e  + (ρ - 1) ∑_e x_e
       ≤   ∑_i C_i^ρ(s^*_i,s_-i) + ρ(σ - 1)∑_e (x_e-1)x_e  + (ρ - 1) ∑_e x_e
       ≤   ∑_e [1 + ρ(x_e - 1 + 1)]x_e^* + ρ(σ - 1)∑_e (x_e-1)x_e  + (ρ - 1) ∑_e x_e
        =    ∑_e [1 + ρ x_e]x_e^* + ρ(σ - 1)(x_e - 1)x_e + (ρ - 1)x_e  
        =    ∑_e [1 + ρ x_e]x_e^* + ρ[ 1 + σ(x_e - 1)]x_e - ρ (x_e - 1)x_e - x_e  
        =    ∑_e [1 + ρ x_e]x_e^* - ρ (x_e - 1)x_e - x_e  +  ρ C^σ(s) 
       ≤    - β(ρ,σ)  C^σ(s) + α(ρ,σ) C^σ(s^*) + ρ C^σ(s)
 
Rearranging terms then gives the desired result.




 The following proposition is used in the proof of Theorem <ref> below.

For every (x,y) ∈^2 ∖{(1,0)}, we have

    f_1(x,y,σ) = 2y(y-1)σ^2 + [x^2 + 2y^2 - 2xy -x] σ + [x^2 - xy +2(y - x)] ≥ 0

for σ≥σ^* = 1/2.


Note that 2y(y-1) ≥ 0 for all y ∈. Furthermore, 

    x^2 + 2y^2 - 2xy -x = (x - y)^2 + y^2 - x ≥ (x-y)^2 + (y-x) ≥ 0

for all (x,y) ∈^2, using the fact that a^2 - a ≥ 0 for all a ∈. This means that f_1(x,y,σ) is non-decreasing, and hence it suffices to prove the statement for σ^* = 1/2. We need to prove

    1/2y(y-1) + 1/2[x^2 + 2y^2 - 2xy -x] + [x^2 - xy +2(y - x)] ≥ 0,

or equivalent,

    y(y-1) + x^2 + 2y^2 - 2xy - x + 2x^2 - 2xy + 4(y-x) ≥ 0.

Simplifying gives

    3x^2 + 3y^2 - 4xy + 3y - 5x ≥ 0

which is equivalent to 

    2(x -y)^2 + x(x-5) + y(y+3) ≥ 0

and this last formulation is clearly true for all pair (x,y) with x ≥ 5. For x = 4, we find 2(4 - y)^2 - 4 + y(y+3) ≥ 0 which is clearly true for y ≥ 1, and for y = 0 in can be checked through inspection. For x = 3, we find 2(3-y)^2 - 6 + y(y+3) ≥ 0 which is clearly true for y ≥ 2. For y ∈{0,1}, it can be check through inspection. For x = 2, we find 2(2 - y)^2 - 6 + y(y+3) ≥ 0, which is again clear for y ≥ 2, and for y ∈{0,1} it can be check through inspection. For x = 1, we find 2(1 - y)^2 - 4 + y(y+3) ≥ 0, which is clearly true for y ≥ 1. For y = 0 the inequality does not hold, but this is the case (x,y) = (1,0) that we do not consider. For x = 0, it is clearly true.  

Theorem<ref>
Let s be a Nash equilibrium under the cost functions C_i^ρ(s) and let s^* be a minimizer of C^σ(·). Then

    C^σ(s)/C^σ(s^*)≤2ρ(1 + σ) + 1/ρ + 1



  * if 1/2≤σ≤ρ≤ 2σ,

  * if σ = 1 and h(σ) ≤ρ≤ 2 σ,

where h(σ) = g(1 + σ + √(σ(σ + 2)), σ) is the optimum of the function

    g(a,σ) = σ(a^2 - 1)/(1 + σ)a^2 - (2σ + 1)a + 2σ(σ+1).

Furthermore, there exists a function Δ = Δ(σ) which the property that, for any fixed σ_0 ≥ 1/2: if Δ(σ_0) ≥ 0, then (<ref>) is true for all h(σ_0) ≤ρ≤ 2σ_0 (the function Δ can be found in the proof below).


We show the following inequality,

    (1 + ρ· x)y - ρ(x - 1)x - x ≤ - 1 + ρ/1 + 2σ(1 + σ(x - 1))x + 2ρ(1 + σ) + 1/1 + 2σ(1 + σ(y - 1))y.

Multiplying with (1 + 2σ) we obtain the equivalent formulation

    (1 + 2σ)[(1 + ρ· x)y - ρ(x - 1)x - x] ≤ -(1 + ρ)(1 + σ(x - 1))x + (2ρ(1 + σ) + 1)(1 + σ(y - 1))y

which we can rewrite to f_1(x,y,σ) ρ + f_2(x,y,σ) ≥ 0 where

    f_1(x,y,σ)    =    -(1 + σ(x-1))x + 2(1 + σ)(1 + σ(y-1))y + (1 + 2σ)((x-1)x - xy) 
       =    2y(y-1)σ^2 + (-(x-1)x + 2(y-1)y + 2y + 2x(x-1) - 2xy)σ
       +    ( -x + 2y + (x-1)x - xy) 
        =     2y(y-1)σ^2 + [x^2 + 2y^2 - 2xy -x] σ + [x^2 - xy +2(y - x)]

and

    f_2(x,y,σ)    =    -(1 + σ(x-1))x + (1 + σ(y-1))y + (1+2σ)(x - y) 
        =    σ y(y-1) - σ x(x-1) + 2σ (x-y) 
        =    (y^2 - x^2 + 3(x-y))σ

We first consider the case (x,y) = (1,0), since then we do not have f_1(x,y,σ) ≥ 0. Substituting the values for x and y, we obtain

    -ρ + 2σ≥ 0

which is true if and only if ρ≤ 2σ. 

Case i).
For the pair (x,y) = (1,0), the inequality is true if and only if ρ≤ 2σ. For all other pairs, we have f_1(x,y,σ) ≥ 0, and hence 

    f_1(x,y,σ) ρ + f_2(x,y,σ) ≥ f_1(x,y,σ) σ + f_2(x,y,σ)

meaning that is suffices to show that f_1(x,y,σ) σ + f_2(x,y,σ) ≥ 0.
After dividing by σ, we see that this is equivalent to

    2y(y-1)σ^2 + [x^2 + 2y^2 - 2xy -x] σ + [x^2 - xy +2(y - x)] + (y^2 - x^2 + 3(x-y)) ≥ 0

which is equivalent to

    2y(y-1)σ^2 + [x^2 + 2y^2 - 2xy -x] σ + [y^2 - xy + (x - y)] ≥ 0

Again, we see that the terms before σ^2 and σ are non-negative for all x,y ∈ (see proof of Proposition <ref>), meaning that if the inequality holds for some σ^*, then it holds for all σ≥σ^*. We take σ^* = 1/2. Multiplying the resulting inequality with 2, we find

    y(y-1)+ [x^2 + 2y^2 - 2xy -x] + 2[y^2 - xy + (x - y)] ≥ 0

which is equivalent to

    x^2 + 5y^2 - 4xy -3y +x ≥ 0.

This can be rewritten as

    (x - 2y)^2 + y(y-3) + x ≥ 0

which is clearly true for all y ∉{1,2}. For y = 1, we find (x - 2)^2  - 2 + x ≥ 0. This is clearly true for all x ≥ 2. For x ∈{0,1}, it can be checked through inspection. For y = 2, we find (x - 4)^2 - 2 + x ≥ 0. This is again clearly true for x ≥ 2, and can be check through inspection for x ∈{0,1}. 

Case ii). Now let (x,y) ∈^2 ∖{(1,0)}, then  f_1(x,y,σ) ≥ 0 by Proposition <ref>, meaning that f_1(x,y,σ) ρ + f_2(x,y,σ) is non-decreasing in ρ. From the proof of Proposition <ref>, it follows that f_1(x,y,σ) = 0 if and only if (x,y) ∈{(1,1), (2,1)} (which can be seen by checking all the cases). Note that this observation is independent of σ. For (x,y) ∈{(1,1), (2,1)} it also holds that f_2(x,y,σ) = 0, which implies that f_1(x,y,σ) ρ + f_2(x,y,σ) = 0 for every ρ. Therefore, we can focus on pairs (x,y) for which f_1(x,y,σ) > 0. 
It follows that any ρ^* for which 

    ρ^* ≥sup_x,y ∈: f_1(x,y,σ) > 0 - f_2(x,y,σ)/f_1(x,y,σ).

yields the inequality for all ρ≥ρ^*. It is not hard to see that this supremum is indeed finite, for every fixed σ. It can be proved that f_1(x,y,σ) ρ' + f_2(x,y,σ) ≥ 0 holds for some large constant ρ', which then serves as an upper bound on the supremum. For the pair (x,y) = (0,1), we find -f_2/f_1 = σ/(1+σ), but we will see later that the supremum on the other pairs obtained is larger than σ/(1+σ).

Note that by now, we can focus on pairs in {(x,y) : x ≥ 1, y ≥ 2}, since for all other pairs we have either proven the inequality or given -f_2/f_1, that is, we are interested in 

    sup_{(x,y) : x ≥ 1, y ≥ 2} - f_2(x,y,σ)/f_1(x,y,σ).

Note that f_2(x,y,σ) = (y^2 - x^2 + 3(x-y))σ = (x+y - 3)(y - x) ≥ 0 if y ≥ x (using that x+y ≥ 3 for (x,y) ∈{(x,y) : x ≥ 1, y ≥ 2}). Hence, if y ≥ x, we have -f_2/f_1 ≤ 0, so those pairs are not relevant for the supremum (if it follows that the upper bound on the supremum for all other pairs is positive, which we will indeed see later). Therefore, we can focus on pairs with y < x.

We substitute x = ay for some (rational) a > 1. Note that

    sup_a  ∈_> 1sup_ y ≥ 2 - f_2(ay,y,σ)/f_1(ay,y,σ)

provides an upper bound on (<ref>). We have

    f_1(ay,y,σ) = [(1+σ)a^2 - (2σ + 1)a + 2σ(σ+1)]y^2 - [(2+σ)a + 2σ^2 - 2]y

and

    - f_2(ay,y,σ) = [(a^2 - 1)σ]y^2 + [3(1-a)σ]y

We determine an upper bound on the expression

    - f_2(ay,y,σ)/f_1(ay,y,σ)   =   [(a^2 - 1)σ]y^2 + [3(1-a)σ]y/[(1+σ)a^2 - (2σ + 1)a + 2σ(σ+1)]y^2 - [(2+σ)a + 2σ^2 - 2]y
        =    [(a^2 - 1)σ]y + [3(1-a)σ]/[(1+σ)a^2 - (2σ + 1)a + 2σ(σ+1)]y - [(2+σ)a + 2σ^2 - 2]
       =   α y + β/γ y - δ

for y ≥ 2. Elementary calculus shows that the derivative with respect to y of (<ref>) is given by -(αδ + γβ)/(γ y - δ)^2, which means the expression in (<ref>) is  non-decreasing or non-increasing in y. 
We have

    αδ + γβ    =    (a^2 - 1)σ[(2+σ)a + 2σ^2 - 2] + 3(1-a)[(1+σ)a^2 - (2σ+1)a +2σ(1+σ)] 
       =    (1-a)σ[-(1+a)((2+σ)a + 2σ^2 - 2) + 3((1+σ)a^2 - (2σ+1)a +2σ(1+σ))] 
       =    (1-a)σ[(3(1+σ) - (2+σ))a^2 + (2 - (2+σ) - 2σ^2 - 3(2σ + 1))a + 2 - 2σ^2 + 6σ(1 + σ)] 
       =    (1-a)σ[(2σ + 1)a^2 - (2σ^2 + 7σ + 3)a + (4σ^2 + 6σ + 2)] 
       =    (1-a)σ[(2σ + 1)a^2 - (2σ + 1)(σ+3)a + (2σ + 1)(2σ + 2)] 
       =    (1-a)σ(1+2σ) [a^2 - (σ+3)a + (2σ + 2)] 
       =    (1-a)σ(1+2σ) [(a - σ+3/2)^2 - 1/4 (1- σ)^2]



Intermezzo. If we consider the function x_2 = (α x_1 + β)/(γ x_1 - δ), we see it has vertical asymptote at x_1^* = δ/γ. 
We claim that x_1^* < 2. Note that, since a > 1, we have δ > 0 for all σ≥ 0. If γ < 0 then x_1^* < 0. If γ > 0, we claim that x_1^* < 2. This is equivalent to showing that

    (2+σ)a + 2σ^2 - 2 < 2(1+σ)a^2 - 2(2σ +1)a + 4σ(σ+1),

which holds if and only if

    2(1+σ)a^2 - (5σ + 4)a + 2(1+σ)^2 = 2(1+σ)( [a - 5σ + 4/4(1+σ)]^2 - 1/4[5σ + 4/2(1+σ)]^2 + (1+σ)) > 0.

If now suffices to show that - 1/4[5σ + 4/2(1+σ)]^2 + (1+σ) > 0, but this is true for all σ > 0, hence, the claim is proven. 


The situation σ = 1. It follows that the expression in (<ref>) is non-positive for all a > 1, which implies that -(αδ + γβ)/(γ y - δ)^2 ≥ 0 and hence -f_2/f_1 is non-decreasing in y ≥ 2 for every a > 1 (using the intermezzo). We then have

    lim_y →∞ -f_2(ay,y,σ)/f_1(ay,y,σ) =  σ(a^2 - 1)/(1 + σ)a^2 - (2σ + 1)a + 2σ(σ+1) =:h_1(a,σ)

and maximizing this function over a ∈_>1, we find the optimum

    a^*(σ) = 1 + σ + √(σ(σ + 2)).


The situation 1/2 ≤σ < 1.
More generally, for any σ < 1 it holds that αδ + γβ≤ 0 if and only if a ∉ (1+σ,2). In particular for every a ∉ (1+σ,2), we can then show that 

    sup_ y ≥ 2 - f_2(ay,y,σ)/f_1(ay,y,σ)≤lim_y →∞ -f_2(a^*y,y,σ)/f_1(a^*y,y,σ)

with a^* as in (<ref>) using the same argument as in the case σ = 1. The intermezzo implies that if the expression (<ref>) is non-increasing in y, which is the case when a ∈ (1 + σ,2), then the maximum value is attained in y = 2. That is, we are interested in the expression -f_2(2a,2,σ)/f_1(2a,2,σ), and in particular, we want to show that the supremum over a ∈ (1+σ, 2) does not exceed the right hand side of (<ref>), i.e., the supremum over all a ∉ (1+σ,2).

 Because of the discussion in the above, it suffices to study 

    -f_2(2a,2,σ)/f_1(2a,2,σ)   =   [(a^2 - 1)σ]2 + [3(1-a)σ]/[(1+σ)a^2 - (2σ + 1)a + 2σ(σ+1)]2 - [(2+σ)a + 2σ^2 - 2]
       =   σ(2a^2-3a+1)/2(1+σ)a^2 - (5σ + 4)a + 2(1+σ)^2 =:h_2(a,σ)







for a ∈ (1+σ,2). This expression, for a > 1, is maximized for b^*(σ) = 1 + σ + √(σ(σ+1/2)), which in particular gives an upper bound for a ∈ (1+σ,2)). 

It now suffices to show that 

    Δ(σ) := h_1(a^*(σ),σ) - h_2(b^*(σ),σ) ≥ 0,

since this implies that the supremum over a > 1 in (<ref>) is attained at some a ∉ (1+σ,2). We have checked this numerically (see Figure <ref>).

The situation  σ > 1.  We can use similar reasoning as in the previous case, but now the expression in (<ref>) is non-increasing for a ∈ (2,1+σ). Note that this does not affect the reasoning in the previous case, since we maximize over all a > 1 when obtaining b^*(σ). 




 



The following theorem shows that the bound in Theorem <ref> is also a lower bound for general congestion games and arbitrary ρ, σ≥ 0. We generalize the construction of Christodoulou and Koutsoupias <cit.>, who showed the lower bound for the classical case ρ = σ = 1.  This construction is also used in the risk-uncertainty model of Nikolova et al. <cit.>, and the altruism model of Chen et al. <cit.>.

For ρ, σ∈_>0 fixed, and players with cost functions C_i^ρ(s), there exist linear congestion games such 

    C^σ(s)/C^σ(s^*)≥2ρ(1 + σ) + 1/ρ + 1

where s is a Nash equilibrium, and s^* a socially optimal strategy profile.



We construct a congestion game of n ≥ 3 players and |E| = 2n resources with price of anarchy greater than or equal to (2ρ(1 + σ) + 1)/(ρ + 1). The set E is divided in the sets E_1 = {h_1,…,h_n} and E_2 = {g_1,…,g_n}. Player i has two pure strategies: {h_i,g_i} and {h_i+1,g_i-1,g_i+1}, where the indices appear as i mod n. The latency functions of the elements in E_1 are c_e(x) = x, whereas the latency functions of the elements in E_2 are c_e(x) = ρ x.

Regardless which strategy player i plays, he always uses at least one resource from both E_1 and E_2, implying that C^σ_i(s) ≥ρ + 1. This implies that

    C^σ(t)  = ∑_i ∈ N C^σ_i(s) ≥ (ρ + 1)n

for every strategy profile t, and in particular for a social optimum s^*. 

We will now show that the strategy profile s where every agent i plays its second strategy {h_i+1,g_i-1,g_i+1} is a Nash equilibrium. We have
C_i^ρ(s) = 2 ρ [1 + ρ(2 - 1)] + 1 = 2ρ^2 + 2ρ + 1.
If some agent i deviates to its first strategy s_i', we have
C_i^ρ(s_i',s_-i) = ρ[1 + ρ(3 - 1)] + (1 + ρ(2-1)) = 2ρ^2 + 2ρ + 1,
since there are then three agents using g_i and two agents using h_i. This shows that s is a Nash equilibrium. The social cost of this strategy s is

    C^σ(s) = n(1 + 2ρ [1 + σ(2-1)]) = (1 + 2ρ(1+σ) ) n.

Combining (<ref>) with (<ref>) then gives the desired result.

Theorem<ref>
Let s be a Nash equilibrium under the cost functions C_i^ρ(s) and let s^* be a minimizer of C^σ(·). Then C^σ(s)/C^σ(s^*) ≤ρ + 1 for 1 ≤ 2σ≤ρ. Furthermore, this bound is tight.


We show that

    (1 + ρ· x)y - ρ(x - 1)x - x ≤ - (1 + σ(x - 1))x + (1+ρ)(1 + σ(y - 1))y

and then the result follows from Lemma <ref>, with h = 1 and g = 1+ρ. Rewriting gives the equivalent statement

    [ y + σ y(y-1) - xy + x(x-1)]ρ + σ[y(y-1) - x(x-1)] ≥ 0.

We first show that [ y + σ y(y-1) - xy + x(x-1)] ≥ 0 for all σ≥ 1/2. If suffices to show this claim for σ = 1/2, since y(y-1) ≥ 0 for all y ∈. We have

    y + 1/2 y(y-1) - xy + x(x-1) = 1/2[ (x - y - 1/2)^2 - 1/4 + x(x-1)]

and this last expression is clearly non-negative for all x,y ∈ (since the quadratic term is always at least 1/4). 

It now suffices to show (<ref>) for ρ = 2σ, since we have shown that the expression is a non-decreasing affine function of ρ, for every fixed σ≥ 1/2. Substituting ρ = 2σ and dividing (<ref>) by σ, we get the equivalent statement

    2 [ y + σ y(y-1) - xy + x(x-1)] + [y(y-1) - x(x-1)] ≥ 0

which we will show to be non-negative for all non-negative integers x and y and σ≥ 1/2. Again, it suffices to show the statement for σ = 1/2. The statement in (<ref>) is then equivalent to

    (x - y - 1/2)^2 - 1/4 + y(y-1)

which is clearly non-negative for all x, y ∈. 

The tightness can be obtained by considering the following game on four resources with two players. Player A has strategies {{1},{2,4}} and player B has strategies {{2},{1,3}}. Resources e = 1,2 have cost function c_e(x) = x and resources e = 3,4 have cost function c_e(x) = ρ x. The optimum s^* = ({1},{2}) has cost 2, whereas the Nash equilibrium s = ({2,4},{1,3} has cost 2(1+ρ).  




§ OMITTED MATERIAL OF SECTION <REF>

Lemma <ref>.
For all non-negative integers x and y, and σ≥ 0, we have

    (x - y + 1/2)^2- 1/4 + 2σ x(x - 1) + (√(σ(σ+2)) + σ)[y(y-1) - x(x-1)] ≥ 0.


The inequality is clearly true for all y ≥ x, so we assume that y < x.
Rewriting the expression gives

    (1 + σ + √(σ(σ+2)))y^2 - 2xy + (1 + σ - √(σ(σ+2)))x^2 - (1 + σ + √(σ(σ+2)))y + (1 - σ + √(σ(σ+2)))x ≥ 0.

Multiplying with 1 + σ - √(σ(σ+2)), which is non-negative for all σ≥ 0, gives

    y^2 - 2(1 + σ - √(σ(σ+2)))xy + (1 + σ - √(σ(σ+2)))^2x^2 - y


    +   (1 + σ - √(σ(σ+2)))(1 - σ + √(σ(σ+2)))x  ≥ 0,

using the fact that (1+σ + √(σ(σ+2)))(1 + σ - √(σ(σ+2))) = 1. This is equivalent to

    ((1+σ - √(σ(σ+2)))x - y + 1/2)^2 + (1+σ - √(σ(σ+2)))([1+σ - √(σ(σ+2))] - 1)x - 1/4≥ 0.

We now substitute c = 1 + σ - √(σ(σ+2))≥ 0 in order to obtain the equivalent formulation

    (c · x - y + 1/2)^2 + c(1-c)x - 1/4≥ 0

for 0 ≤ c < 1, since the function c(σ) = 1 + σ - √(σ(σ+2)) is  bijective from  to [0,1). For x = 0, the inequality reduces to (1/2 - y)^2 - 1/4 ≥ 0 which is true for all y ∈. For x = 1, we get the equivalent formulation

    (y-1)(y - 2c) ≥ 0,

which is clearly true for y = 1. For y = 0, it follows from the fact that c ≥ 0. For y ≥ 2 if follows from the fact that y - 2c ≥ 0 for all y ≥ 2, since 0 ≤ c < 1. This completes the case x = 1. 

For x ≥ 2, we rewrite the expression (<ref>) to

    x(x - 1)c^2 + 2x(1 - y)c + y(y-1) ≥ 0

If y = 0, the expression in (<ref>) is clearly non-negative for all x ≥ 2 and 0 ≤ c < 1. For y ≥ 1, note that g(c) = x(x - 1)c^2 + 2x(1 - y)c + y(y-1) is a quadratic and convex function for all fixed x and y. Therefore, in particular, for any x and y fixed, it suffices to show that the inequality holds for the minimizer of g, which is c^* = (y-1)/(x-1) (which can be found by differentiating with respect to c). Note that 0 ≤ c^* < 1 by our assumption that y ≥ 1 and y < x (made in the beginning of the proof). Substituting implies that it suffices to show that

    x(x-1)(y-1)^2/(x-1)^2 + 2x(1-y)(y-1)/x-1 + y(y-1) ≥ 0.

Multiplying the expression with (x-1) implies that it now suffices to show that

    x(y-1)^2 - 2x(y-1)^2 + y(y-1)(x-1)  ≥ 0

for all 1 ≤ y < x. This is always true since

    x(y-1)^2 - 2x(y-1)^2 + y(y-1)(x-1)     =     -x(y-1)^2 + y(y-1)(x-1) 
        =     (y-1) [-x(y-1) + y(x-1)] 
        =     (y-1) (x - y) 
       ≥    0

whenever 1 ≤ y < x. This completes the proof. 


The bound of 2 on the price of stability for generalized affine congestion games requires some additional arguments: 
The bound in  Theorem <ref> with ρ = σ is only valid for σ≥ 1/4 (because otherwise the lower bound on ρ is not satisfied). Nevertheless for 0 ≤σ≤ 1/4, the corresponding cost functions c_e(x) = σ x + (1-σ) have non-negative constants and thus the price of stability for classical congestion games applies here. That is, we have

    PoS(𝒜') = max{1.577,  sup_σ≥ 1/4{1 + √(σ/(σ+2))}} = 2.
 




§ OMITTED MATERIAL OF SECTION <REF>


Theorem<ref>
Let ℋ be a collection of congestion games. If PoA(ℋ,1,2) = 1, then PoA(ℋ,1,ρ) is non-increasing function for 1 ≤ρ≤ 2.


Let α = ρ - 1. Suppose that PoA(ℋ,1,α) =: PoA(α) is not non-increasing, then there exist x < y ∈ [0,1] such that PoA(y) > PoA(x). We also know, by assumption, that PoA(x) ≥PoA(1) = 1, since the price of anarchy is always lower bounded by 1 (note that this also implies that y ≠ 1). This means that

    max{PoA(x), PoA(1)} < PoA(y).
 
However, if we write y = γ· x + (1- γ)· 1 for some γ∈ [0,1], then Theorem 10.2 <cit.> implies that 

    PoA(y) ≤max{PoA(x),PoA(1)}

which is a contradiction.  




§ OMITTED MATERIAL OF SECTION <REF>


Theorem<ref>
Let Γ be a symmetric network congestion game with linear cost functions, then 

    PoS(Γ, ρ, 1) ≤{[     4/(ρ(4-ρ))   if  0  ≤ρ≤ 1;        4/(2+ρ)   if  1  ≤ρ≤ 2;        (2+ρ)/4 if  2  ≤ρ  < ∞ ].

In particular, if Γ is a symmetric congestion game on an extenstion-parallel [A graph G is extension parallel if it consists of either (i) a single edge, (ii) a single edge and an extension-parallel graph composed in series, (iii) two extension-parallel graphs composed in parallel.] graph G, then the upper bounds even hold for the price of anarchy. All bounds are tight.
 

The remainder of this section is dedicated to the proof of Theorem <ref>. 
We will refer to strategy profiles as flows, since we can interpret symmetric network congestion games as a flow problem in which players each have to route one unit of unsplittable flow from a given source to a given target. To be precise, for a graph G = (V,E) and given s,t ∈ V, we write 𝒫 for the set of all simple s,t-paths (the common strategy set of the players). We denote f_P as the number of players using path P ∈𝒫. We call f a feasible (unsplittable) flow if ∑_P ∈𝒫 f_P = N, and with f_e we denote the number of players using edge e ∈ E, that is, f_e = ∑_P ∈𝒫 : e ∈ P f_P.

We use the following result due to Fotakis <cit.>.
 Let Γ be a congestion game with cost functions d_e, and let Φ be an exact potential for Γ. An acyclic flow f minimizes the potential function Φ if and only if

    ∑_e : f_e > g_e (f_e - g_e)d_e(f_e) - ∑_e:f_e < g_e (g_e - f_e)d_e(f_e + 1) ≤ 0

for every feasible flow g. 


The following lemma gives inefficiency results for global minima of the potential function Φ (compared to any feasible flow). Since the local minima of Φ correspond to the Nash equilibria of the game Γ, it follows that the global minima of Φ are Nash equilibria. Furthermore,  Fotakis <cit.> shows that every Nash equilibrium of a symmetric congestion game on an extension-parallel graph is a global minimum of the potential function Φ. In particular, this means that the ineffiency results in Lemma <ref> hold for the price of stability of symmetric network congestion games, and the price of anarchy of symmetric extension-parallel congestion games.



  
Let Γ be a congestion game with cost functions d_e(x) = a_e (1 + ρ(x - 1)), and let Φ be an exact potential for Γ. Let f be an acyclic flow minimizing the potential function Φ, then

    C^σ(f)    ≤   ∑_f_e > g_e a_e[ (f_e - 1)(ρ g_e + (σ - ρ)f_e) + g_e] 
            + ∑_f_e ≤ g_e a_e [ (f_e - 1)(ρ g_e + (σ - ρ)f_e) + (1+ρ)g_e - ρ f_e ].

Furthermore, if h(ρ,σ) < 1 satisfies, 

    (x - 1)(ρ y + (σ - ρ)x) + y ≤ h(ρ,σ) · x[1 + σ(x-1)] + g(ρ,σ) · y[1 + σ(y-1)]

for all non-negative integers x > y, and

    (x - 1)(ρ y + (σ - ρ)x) + (1+ρ)y - ρ x ≤ h(ρ,σ) ·  x[1 + σ(x-1)] + g(ρ,σ) · y[1 + σ(y-1)]

for all non-negative integers x ≤ y, then C^σ(f)/C^σ(g) ≤ g(ρ,σ) / (1 - h(ρ,σ)). 
 


We write d_e(x) = a_e[1 + σ(x - 1)] +  a_e[(ρ - σ)(x - 1)] in the left summation, and obtain, using Lemma <ref>,

    ∑_f_e > g_e f_e a_e[1 + σ(f_e - 1)]    ≤   ∑_f_e > g_e a_e( g_e[1 + ρ(f_e - 1)] + f_e(σ - ρ)(f_e - 1))  
           +∑_f_e < g_e (g_e - f_e) a_e(1+ρ f_e).

Applying the inequality, we find

    C^σ(f)    =   ∑_f_e > g_ef_e a_e[1 + σ(f_e - 1)] + ∑_f_e < g_ef_e a_e[1 + σ(f_e - 1)] + ∑_f_e = g_ef_e a_e[1 + σ(f_e - 1)] 
       ≤   ∑_f_e > g_e a_e[ (f_e - 1)(ρ g_e + (σ - ρ)f_e) + g_e] 
           +∑_f_e < g_e a_e [ (f_e - 1)(ρ g_e + (σ - ρ)f_e) + (1+ρ)g_e - ρ f_e ]+ ∑_f_e = g_ef_e a_e[1 + σ(f_e - 1)] 
        =    ∑_f_e > g_e a_e[ (f_e - 1)(ρ g_e + (σ - ρ)f_e) + g_e] 
           +∑_f_e ≤ g_e a_e [ (f_e - 1)(ρ g_e + (σ - ρ)f_e) + (1+ρ)g_e - ρ f_e ]

This completes the proof. 

We continue the proof of the upper bounds in Theorem <ref> by showing the result in the statement for 0 < ρ≤ 1, that is, we define 

    h(ρ,1) = 1 - ρ + ρ^2/4       and     g(ρ,1) = 1

and prove the correctness of the resulting inequalities in (<ref>) and (<ref>) (see Lemma <ref>). The cases 1 ≤ρ≤ 2 and 2 ≤ρ≤∞ follow (indirectly) from Caragiannis et al. <cit.>.[The model of Carigiannis et al. <cit.> is equivalent to our model under the transformation ρ = 1/(1 - ζ), where ζ is the model parameter of <cit.>. That is, the range 1 ≤ρ≤ 2 corresponds to ζ∈ [0,1/2], and the range 2 ≤ρ≤∞ to ζ∈ [1/2,1).] The authors use a similar approach as here, but only show the inequality in Lemma <ref> for Nash equilibria of symmetric singleton congestion games. Nevertheless, the remainder of the analysis carries over  to our model.


For any integers x,y ≥ 0 and any ρ∈ (0,1] we have, when x < y,

    ρ· xy + (y - x) ≤ρ^2/4x^2 + y^2,

and, when x ≥ y,

    ρ· xy + (1 - ρ)(y - x) + (1- ρ)x^2 ≤(1 - ρ + ρ^2/4)x^2 + y^2.



Let y = x + z, where z is a positive integer. Then we have

    f(x,y)    =    ρ^2/4x^2 + y^2 - ρ xy - (y - x) 
       =   ρ^2/4x^2 + (x^2 + 2xz + z^2) - ρ x(x+z) - z 
       =   (ρ^2/4 + 1 - ρ)x^2 + (2 - ρ)xz + z(z-1) 
       ≥    0,

since ρ∈ (0,1], x ≥ 0 and z > 0. 

For the second inequality, it suffices to show that

    g(x,y) = ρ^2/4x^2 + y^2 - ρ xy  - (ρ - 1)(x - y) ≥ 0

which can be seen by leaving out the term (1-ρ)x^2 on both sides of the inequality.
We first treat the case y = 0. Then 

    g(x,0) = ρ^2/4x^2 + (1-ρ)x ≥ 0

since x ≥ 0 and ρ∈ (0,1]. For y ≥ 1, we write a = x/y (for sake of notation). We have

    g(x,y)   =    ρ^2/4x^2 + y^2 - ρ xy - (ρ - 1)(x - y)  
       =   ρ^2/4a^2y^2 + y^2 - ρ a y^2 + (1- ρ)(ay - y) 
       =   [(ρ a)^2/4 - ρ a + 1]y^2 + (1 - ρ)(a - 1)y 
       =   [ρ a/2 -1]^2y^2 +  (1-ρ)(a-1)y 
       =   [ρ x/2y -1]^2y^2 +  (1-ρ)(x/y-1)y 
       ≥    0,

since ρ∈ (0,1], y ≥ 1 and a ≥ 1. 

It remains to show tightness of the resulting bounds. For 1 ≤ρ≤ 2, consider an instance with two players and two resources with resp. cost functions c_1(x) = x and c_2(x) = (1 + ρ + ϵ) x where 0 < ϵ≪ρ. Then the unique Nash equilibrium is given by (x_1,x_2) = (2,0), and the social optimum by (x_1^*,x_2^*) = (1,1). Sending ϵ→ 0 gives the desired bound of 4/(2+ρ).

For 2 ≤ρ≤∞, we can use the same instance as the for 1 ≤ρ≤ 2, with the only difference that c_2(x) = (1 + ρ - ϵ)x. Then the social optimum is given by (x_1^*,x_2^*) = (2,0) and the unique Nash equilibrium by (x_1,x_2) = (1,1).

For the case 0 < ρ≤ 1, the lower bound is technically more involved.


For every fixed (rational) 0 < ρ≤ 1, and ϵ > 0, there exists a symmetric singleton congestion game for which the price of stability is greater than 4/(ρ(4 - ρ)) - ϵ.


 We choose values of n and i so that

    ρ = i/n-1

where, without loss of generality, we may assume that i is even. We will construct a congestion game with n agents and 1 + (n - i/2) resources. We let c_0(x) = x and for e ∈{1,…,n-i/2} we define 

    c_e(x) = [(1-ρ) + ρ n + ϵ]x = [1 + i + ϵ]x,      with  0 < ϵ≪ρ.

A socially optimal profile s^* is given by x_0^* = i/2 and x_e^* = 1 for e ∈{1,…,n-i/2}, resulting in

    SC(s^*)    =   (i/2)^2 + (n - i/2)(1 + i + ϵ) 
        =    ρ^2/4(n - 1)^2 + (n - 1/2ρ(n-1))[(1-ρ) + ρ n + ϵ] 
        =    ρ^2/4(n^2 - 2n + 1) + ( (1 - ρ/2 )n + ρ/2)[(1-ρ) + ρ n + ϵ] 
        =    [ρ^2/4 + ρ(1 - ρ/2)]n^2 + [-ρ^2/2 + (1-ρ + ϵ)(1 - ρ/2) + ρ^2/2]n + ρ^2/4 + ρ/2(1-ρ + ϵ) 
       =   [ρ(1 - ρ/4)]n^2 + [(1-ρ + ϵ)(1 - ρ/2)]n + ρ/2(1 - ρ/2 + ϵ)


The unique Nash equilibrium is given by the strategy profile s for which x_0 = n and x_e = 0 for e ∈{1,…,n-i/2}, since the perceived cost on resource e = 0 is then precisely (1-ρ) + ρ n, so no player can strictly improve its (perceived) cost by deviating to one of the other resources, which have cost (1-ρ) + ρ n + ϵ. The social cost of this equilibrium is n^2, which implies that

    C^1(s)/C^1(s^*) = n^2/[ρ(1 - ρ/4)]n^2 + [(1-ρ)(1 - ρ/2 + ϵ)]n + ρ/2(1 - ρ/2 + ϵ)→1/ρ(1 - ρ/4)

as n →∞ (note that this also means that i →∞ since ρ is fixed). 



