A Unifying Tool for Bounding the Quality of Non-Cooperative Solutions in Weighted Congestion Games

Abstract

We present a general technique, based on a primal-dual formulation, for analyzing the quality of self-emerging solutions in weighted congestion games. With respect to traditional combinatorial approaches, the primal-dual schema has at least three advantages: first, it provides an analytic tool which can always be used to prove tight upper bounds for all the cases in which we are able to characterize exactly the polyhedron of the solutions under analysis; secondly, in each such a case, the complementary slackness conditions give us a hint on how to construct matching lower bounding instances; thirdly, proofs become simpler and easy to check. For the sake of exposition, we first apply our technique to the problems of bounding the price of anarchy and stability of exact and approximate pure Nash equilibria, as well as the approximation ratio of the strategy profiles achieved after a one-round walk starting from the empty state, in the case of affine latency functions and we show how all the known upper bounds for these measures (and some of their generalizations) can be easily reobtained under a unified approach. Then, we use the technique to attack the more challenging setting of polynomial latency functions. In particular, we obtain the first known upper bounds on the price of stability of pure Nash equilibria and on the approximation ratio of the strategy profiles achieved after a one-round walk starting from the empty state for unweighted players in the cases of quadratic and cubic latency functions.

1 Introduction

Characterizing the quality of self-emerging solutions in non-cooperative systems is one of the leading research directions in Algorithmic Game Theory. Given a game $\mathcal G$, a social function $\mathcal F$ measuring the quality of any strategy profile which can be realized in $\mathcal G$, and the definition of a set $\mathcal E$ of certain self-emerging solutions, we are asked to bound the ratio ${\mathcal Q}({\mathcal G},{\mathcal E},{\mathcal F}):={\mathcal F}(K)/{\mathcal F}(O)$, where K is some solution in ${\mathcal E}({\mathcal G})$ (usually either the worst or the best one with respect to $\mathcal F$) and O is the strategy profile optimizing $\mathcal F$.

In such a setting, Roughgarden [40] proposes the so-called “smoothness argument” as a unifying technique for proving tight upper bounds on ${\mathcal Q}({\mathcal G},{\mathcal E},{\mathcal F})$ for several notions of self-emerging solutions $\mathcal E$, when $\mathcal G$ satisfies some general properties, K is the worst solution in $\mathcal E(\mathcal G)$ and $\mathcal F$ is sum-bounded, that is, upper bounded by the sum of the players’ payoffs. He also gives a more refined interpretation of this argument and stresses also its intrinsic limitations, in a subsequent work with Nadav [37], by means of a primal-dual characterization which shares lot of similarities with the primal-dual framework we provide in this paper. Anyway, there is a subtle, yet substantial, difference between the two approaches and we believe that the one we propose is more general and powerful. Both techniques formulate the problem of bounding ${\mathcal Q}({\mathcal G},{\mathcal E},{\mathcal F})$ via a (primal) linear program and, then, an upper bound is achieved by providing a feasible solution for the related dual program. But, while in [37] the variables defining the primal formulation are yielded by the strategic choices of the players in both K and O (as one would expect), in our technique the variables are the parameters defining the players’ payoffs in $\mathcal G$, while K and O play the role of fixed, but arbitrary, constants.

As it will be clarified later, such an approach, although preserving the same degree of generality, applies to a broader class of games and allows for a simple analysis facilitating the proof of tight results. In fact, as already pointed out in [37], the Strong Duality Theorem assures that each primal-dual framework can always be used to derive the exact value of ${\mathcal Q}({\mathcal G},{\mathcal E},{\mathcal F})$ provided that, for any strategy profile S which can be realized in $\mathcal G$, ${\mathcal F}(S)$ can be expressed through linear programming and

• (i) the polyhedron defining $\mathcal E(\mathcal G)$ can be expressed through linear programming, when K is the worst solution in $\mathcal E(\mathcal G)$ with respect to $\mathcal F$,

• (ii)the polyhedron defining K can be expressed through linear programming, when K is the best solution in $\mathcal E(\mathcal G)$ with respect to $\mathcal F$.

Moreover, in all such cases, by applying the “complementary slackness conditions”, we can figure out which pairs of strategy profiles (K,O) yield the exact value of ${\mathcal Q}({\mathcal G},{\mathcal E},{\mathcal F})$, thus being able to construct quite systematically matching lower bounding instances.

In this work, we consider three sets of solutions $\mathcal E$ (see Section 2 for their formal definitions), namely,

• (i) (1 + 𝜖)-approximate pure Nash equilibria (P N E _𝜖 ), that is, outcomes in which no player can improve her situation by a factor of more than 𝜖 by unilaterally changing the adopted strategy (i.e., no player possesses an 𝜖-approximate improving deviation). In this case, ${\mathcal Q}({\mathcal G},{\mathcal E},{\mathcal F})$ is called the 𝜖-approximate price of anarchy of $\mathcal G$, denoted as $\mathsf {PoA}_{\epsilon }(\mathcal G)$, when K is the worst strategy profile in $\mathcal E(\mathcal G)$, while it is called the 𝜖-approximate price of stability of $\mathcal G$, denoted as $\mathsf {PoS}_{\epsilon }(\mathcal G)$, when K is the best strategy profile in $\mathcal E(\mathcal G)$;

• (ii) pure Nash equilibria (P N E), that is, the set of outcomes in which no player can improve her situation by unilaterally changing the adopted strategy (i.e., no player possesses an improving deviation). By definition, each P N E ₀ is a P N E and the terms price of anarchy (P oA$(\mathcal G)$) and price of stability (P oS$(\mathcal G)$) are used in this case;

• (iii) strategy profiles achieved after a one-round walk starting from the empty state [36], that is, the set of outcomes which arise when, starting from an initial configuration in which no player has done any strategic choice yet, each player is asked to select, sequentially and according to a given ordering, her best possible current strategy. In this case, K is always defined as the worst strategy profile in $\mathcal E(\mathcal G)$ and ${\mathcal Q}({\mathcal G},{\mathcal E},{\mathcal F})$ is denoted as A px$_{\emptyset }^{1}(\mathcal G)$.

We observe that approximate pure Nash equilibria (resp. pure Nash equilibria) can also be intended as the output of an algorithm which repeatedly allows players to perform approximate improving deviations (resp. improving deviations) until a steady state is finally reached. Similarly, strategy profiles achieved after a one-round walk starting from the empty state can be seen as the output of a greedy-like online algorithm which aims at minimizing $\mathcal F$ by assigning to each player, upon her arrival, the strategy currently minimizing her cost. These relationships are at the basis of our approach: to exploit linear programming, and in particular the duality theory, to bound the efficiency of self-emerging solutions, in the same spirit as for the approximation ratio of polynomial time algorithms and for the competitive ratio of online algorithms.

1.1 Our Contribution

Our method reveals to be particularly powerful when applied to the class of weighted congestion games. In these games, there are n weighted players competing for a set of resources. Each resource has a latency function which only depends on its congestion, i.e., the sum of the weights of its users. These games have a particular appeal since, from the one hand, they are general enough to model a variety of situations arising in real life applications and, from the other one, they are structured enough to allow a systematic theoretical study. For example, for the case in which all players have the same weight (unweighted players), Rosenthal [41] proved through a potential function argument that P N E are always guaranteed to exist, while, in general, weighted congestion games are guaranteed to possess P N E if and only if the latency functions are either affine or exponential [29,30,31, 39].

In order to illustrate the versatility and usefulness of our technique, we first consider the well-known and studied case in which the latency functions are affine and $\mathcal F$ is the sum of the players’ payoffs and show how all the known results (as well as some of their generalizations) can be easily reobtained under a unifying approach. For the P o A _𝜖 and the P o S _𝜖 in the unweighted case and for the $\mathsf {Apx}_{\emptyset }^{1}$ in the weighted case, we reobtain the known upper bounds given in [4, 23, 25, 26] with significatively shorter and simpler proofs (where, by simple, we mean that only basic notions of calculus are needed in the arguments), while for the generalizations of the P o A _𝜖 and the P o S _𝜖 in the weighted case, we give the first upper bounds known in the literature.

After having introduced the technique, we show how it can be used to attack the more challenging case of polynomial latency functions. In such a scenario, the P o A and the P o A _𝜖 were already studied and characterized in [1] and [25], respectively, and both papers pose the achievement of upper bounds on the P o S and the P o S _𝜖 as a major open problem in the area. For unweighted players, we show that, for any congestion game $\mathcal G$ with quadratic latency functions, $2.1859\leq \mathsf {PoS}({\mathcal G})\leq 2.362$ and $\mathsf {Apx}^{1}_{\emptyset }({\mathcal G})\leq 37.5888$ and that, for any congestion game $\mathcal G$ with cubic latency functions, $2.7558\leq \mathsf {PoS}({\mathcal G})\leq 3.322$ and $\mathsf {Apx}^{1}_{\emptyset }({\mathcal G})\leq 527.323$. Recently, and after the publication of the conference version of this paper, Christodoulou and Gairing [22] gave an exact characterization of the Po S for polynomial latency functions of maximum degree equal to d. In particular, they showed that the two upper bounds we give in this paper for the cases of d = 2,3 are tight.

What we would like to stress here is that, rather than the novelty of the results achieved in this paper, what makes our method interesting is its capability of being easily adapted to a variety of particular situations and we are more than sure of the fact that it will prove to be a powerful tool to be exploited in the analysis of the efficiency achieved by different classes of self-emerging solutions in other contexts as well (see, Section 1.3 for a discussion on some recent application of our technique). To this aim, we show how the method applies also to other social functions, such as the maximum of the players’ payoffs, where the smoothness argument cannot even be applied. Moreover, in the case of polynomial latency functions, the primal-dual technique proposed in [37] cannot be used, since the players’ costs are not linear in the variables of the problem.

Although most of the times our method may look like a reinterpretation of known techniques (as the use of Nash inequalities and potential inequalities), there is a feature that makes it preferable to classical combinatorial approaches: once the properties possessed by the target solution are suitably modeled as linear constraints and embedded within the formulation, then, by computing its optimal solution, we are guaranteed to determine the best possible upper bound on the worst-case efficiency of the target solution which can be obtained by making use of these properties. Put in other words, we do not need to “optimize” the proof of the upper bound: the method does it all for us, all we need to do is to find the optimal solution of the formulation. Not by chance, in fact, after the publication of the conference version of this paper [7], the primal-dual method has been exploited to provide the exact solution to some open problems in this research field (see, Section 1.3 for a detailed discussion).

1.2 Related Work

The study of the quality of self-emerging solutions in non-cooperative systems initiated with the seminal papers of Koutsoupias and Papadimitriou [32] and Anshelevich et al. [2] which introduced, respectively, the notions of price of anarchy and price of stability.

A lot of results have been achieved since then and we recall here only the ones which are closely related to our scenario of application, that is, weighted congestion games with polynomial latency functions.

For affine latency functions and $\mathcal F$ defined as the sum of the players’ payoffs, Christodoulou and Koutsoupias [23] show that the P o A is exactly 5/2 for unweighted players, while Awerbuch, Azar and Epstein [4] show that it rises to exactly $(3+\sqrt {5})/2$ in the weighted case. These bounds keep holding also when considering the price of anarchy of generalizations of P N E such as mixed Nash equilibria and correlated equilibria, as shown by Christodoulou and Koutsoupias in [24]. Similarly, for polynomial latency functions with maximum degree equal to d, Aland et al. [1] prove that the price of anarchy of all these equilibria is exactly ${\Phi }_{d}^{d + 1}$ in the weighted case and exactly $\frac {(k + 1)^{2d + 1}-k^{d + 1}(k + 2)^{d}}{(k + 1)^{d + 1}-(k + 2)^{d}+(k + 1)^{d}-k^{d + 1}}$ in the unweighted case, where Φ _d is the unique non-negative real solution to (x + 1)^d = x ^d+ 1 and k = ⌊Φ _d ⌋. These interdependencies have been analyzed by Roughgarden [40], who proves that unweighted congestion games with non-negative and non-decreasing latency functions belong to the class of games for which a so-called “smoothness argument” applies and that such a smoothness argument directly implies that, when $\mathcal F$ is the sum of the players’ payoffs, the price of anarchy stays the same, independently of which solution concept among P N E, mixed Nash equilibria, correlated equilibria and coarse correlated equilibria is adopted. Such a result has been extended also to the weighted case by Bhawalkar, Gairing and Roughgarden in [6]. For the alternative model in which $\mathcal F$ is defined as the maximum of the players’ payoffs, Christodoulou and Koutsoupias [23] show a P o A of ${\Theta }(\sqrt {n})$ in the case of affine latency functions.

For the P o S, only the case of unweighted players, affine latency functions and $\mathcal F$ defined as the sum of the players’ payoffs, has been considered so far. The upper and lower bounds achieved by Caragiannis et al. [20] and by Christodoulou and Koutsoupias [24], respectively, set the P o S to exactly $1 + 1/\sqrt {3}$.

As to the P N E _𝜖 , in the case of unweighted players, polynomial latency functions and $\mathcal F$ defined as the sum of the players’ payoffs, Christodoulou, Koutsoupias and Spirakis [25] show that the P o A _𝜖 is exactly $\frac {(1+\epsilon )((z + 1)^{2d + 1}-z^{d + 1}(z + 2)^{d})}{(z + 1)^{d + 1}-z^{d + 1}-(1+\epsilon )((z + 2)^{d}-(z + 1)^{d})}$, where z is the maximum integer satisfying $\frac {z^{d + 1}}{(z + 1)^{d}}<1+\epsilon$, and that, for affine latency functions, the P o S _𝜖 is at least $\frac {2(3+\epsilon +\theta \epsilon ^{2}+ 3\epsilon ^{3}+ 2\epsilon ^{4}+\theta +\theta \epsilon )} {6 + 2\epsilon + 5\theta \epsilon + 6\epsilon ^{3}+ 4\epsilon ^{4}-\theta \epsilon ^{3}+ 2\theta \epsilon ^{2}}$, where $\theta =\sqrt {3\epsilon ^{3}+ 3+\epsilon + 2\epsilon ^{4}}$, and at most $(1+\sqrt {3})/(\epsilon +\sqrt {3})$.

Finally, for affine latency functions and $\mathcal F$ defined as the sum of the players’ payoffs, the $\mathsf {Apx}^{1}_{\emptyset }$ has been shown to be exactly $2+\sqrt {5}$ in the unweighted case as a consequence of the upper and lower bounds provided, respectively, by Christodoulou, Mirrokni and Sidiropoulos [26] and by Bilò et al. [10], while, for weighted players, Caragiannis et al. [20] give a lower bound of $3 + 2\sqrt {2}$ and Christodoulou, Mirrokni and Sidiropoulos [26] give an upper bound of $4 + 2\sqrt {3}$. For $\mathcal F$ being the maximum of the players’ payoffs, Bilò et al. [10] show that the $\mathsf {Apx}^{1}_{\emptyset }$ is ${\Theta }(\sqrt [4]{n^{3}})$ in the unweighted case and affine latency functions.

Strategy profiles realized after a one-round walk starting from the empty state can be reinterpreted as the output of an online greedy algorithm for the problem of minimizing the social function $\mathcal F$. Under this perspective, the bounds given by Awerbuch et al. [5], Caragiannis et al. [20] and Suri, Tóth, and Zhou [42] on the competitive ratio of greedy algorithms for the problem of minimizing the total latency in online load balancing can be seen as bounds for the $\mathsf {Apx}^{1}_{\emptyset }$ in the special case of affine congestion games in which the strategies of all players are singleton sets.

The use of primal-dual analysis, and in particular of factor-revealing linear programs, for bounding the performance of greedy-like algorithms has been introduced in the seminal paper by Jain et al. [33] and later exploited by Athanassopoulos et al. [3] for variants of set cover, by Mahdian and Yan [34] for online matching, by Feige and Jozeph [27] for maximum directed cut, and by Caragiannis [17] for wavelength routing.

1.3 Subsequent Work

After the publication of the conference version of this paper [7], the primal-dual method has been fruitfully used in a variety of situations.

Bilò, Flammini and Gallotti [12] consider congestion games with affine latency functions under the assumption that the players’ knowledge is restricted by the presence of an underlying social knowledge graph. In particular, each player is only aware of her choice and of the choices of all the players representing her neighborhood in the social knowledge graph, whereas in the traditional model each player has full knowledge of the strategic choices of all the other players in the game. By exploiting the primal-dual method, tight bounds on the price of anarchy and almost tight bounds on the price of stability are determined for the case in which the social knowledge graph has a special topology allowing for a “bidimensional” reinterpretation of congestion games with restricted social knowledge.

Bilò et al. [13] exploit the primal-dual method to extrapolate a matching (and unexpected) lower bounding instance for the sequential price of anarchy, that is the price of anarchy of subgame perfect equilibria in sequential games [38], of cut games. This contribution, in particular, illustrates an application of our method to a class of self-emerging solutions not considered in this paper.

The primal-dual method has been used by Bilò [8] to derive tight bounds on the worst-case price of stability of pure Nash equilibria in congestion games with affine latency functions and altruistic players, thus solving an open problem risen by Caragiannis et al. [19]; by Bilò and Paladini [14] to derive tight bounds on the approximation ratio of the strategy profiles achieved after a one-round walk of (1 + 𝜖)-approximate best-responses starting from any initial strategy profile in cut games, for any 𝜖 ≥ 0, thus solving an open problem left by Christodoulou, Mirrokni and Sidiropoulos [26]; by Bilò, Fanelli and Moscardelli [11] to derive significant upper bounds on the price of anarchy of lookahead equilibria in congestion games with affine latency functions, thus improving on a previous result by Mirrokni, Thain and Vetta [35]; and by Bilò and Vinci [15] to obtain exact bounds on the price of anarchy of Stackelberg strategies in congestion games with affine latency functions, thus solving an open problem left by Fotakis [28].

Recently, building on the primal-dual method, Bilò and Vinci [16] design efficient tax functions for weighted congestion games with polynomial latency functions, thus generalizing and extending previous results achieved by Caragiannis et al. [18].

Moreover, very recently, Bilò [9] used the primal-dual method to show that, for a variety of (even non-sum-bounded) social functions and for a broad generalization of the class of weighted congestion games with non-negative (and possibly decreasing) latency functions, the worst-case price of anarchy of (1 + 𝜖)-approximate coarse correlated equilibria still coincides with that of (1 + 𝜖)-approximate pure Nash equilibria, for any 𝜖 ≥ 0, thus significantly generalizing the tightness result obtained by Bhawalkar, Gairing and Roughgarden in [6] by making use of the smoothness argument (delving into a detailed discussion about differences and similarities between the smoothness argument and the primal-dual method is, in our opinion, beyond the scope of this paper; however, the interested reader can fully satisfy his/her curiosity by looking at [9]).

1.4 Paper Organization

In the next section, we give all the necessary definitions and notation, while, in Section 3, we briefly outline the primal-dual method. Then, in Section 4, we illustrate how it applies to affine latency functions and, in Section 5, we use it to address the case of quadratic and cubic latency functions. In Section 6, we show how the method applies to the social function defined as the maximum of the players’ payoffs. Finally, in the last section, we discuss further research and open problems.

2 Definitions

For a given integer n > 0, we denote as [n] the set {1,…,n}.

A weighted congestion game ${\mathcal G} = \left ([n], E, ({\mathsf {\Sigma }}_{i})_{i \in [n]}, (\ell _{e})_{e \in E}, (w_{i})_{i \in [n]}\right )$ is a non-cooperative strategic game in which there is a set E of m resources to be shared among the players in [n], where n ≥ 2. Each player i has an associated weight w _i ≥ 0 and the special case in which w _i = 1 for any i ∈ [n] is called the unweighted case. The strategy set # #Σ# # _i , for any player i ∈ [n], is a non-empty subset of resources, i.e., # #Σ# # _i ⊆ 2^E ∖{∅}. The set # #Σ# # = × _i∈[n] # #Σ# # _i is called the set of strategy profiles (or strategy profiles) which can be realized in ${\mathcal G}$. Given a strategy profile s = (s ₁,s ₂,…,s _n ) ∈# #Σ# # and a resource e ∈ E, the sum of the weights of all the players using e in s, called the congestion of e in s, is denoted by ${\mathcal L}_{e}({s})={\sum }_{i\in [n]:e\in s_{i}}w_{i}$. A latency function $\ell _{e} : \mathbb {R}_{\geq 0} \mapsto \mathbb {R}_{\geq 0}$ associates each resource e ∈ E with a latency depending on the congestion of e in s. The cost of player i in the strategy profile s is given by $c_{i}({s})={\sum }_{e \in s_{i}}\ell _{e}({\mathcal L}_{e}({s}))$. This work is concerned only with polynomial latency functions of maximum degree d, i.e., the case in which $\ell _{e}(x) = {\sum }_{i = 0}^{d}\alpha _{e,i}x^{i}$ with $\alpha _{e,i}\in \mathbb {R}_{\geq 0}$, for any e ∈ E and 0 ≤ i ≤ d. We denote as $\mathcal WCG$ and $\mathcal UCG$ the class of weighted and unweighted congestion games, respectively.

Given a strategy profile s ∈# #Σ# # and a strategy t ∈# #Σ# # _i for player i, we denote with s _−i ◇ t = (s ₁,…,s _i− 1,t,s _i+ 1,…,s _n ) the strategy profile obtained from s when player i changes unilaterally her strategy from s _i to t. A strategy t ∈# #Σ# # _i is an improving deviation for player i in s, if c _i (s _−i ◇ t) < c _i (s).

Definition 1

Given an 𝜖 ≥ 0, a strategy profile s is a (1 + 𝜖)-approximatepure Nash equilibrium (N E _𝜖 ) if, for any i ∈ [n] and t ∈# #Σ# # _i , c _i (s) ≤ (1 + 𝜖)c _i (s _−i ◇ t).

Note that the set of 1-approximate pure Nash equilibria collapses to that of pure Nash equilibria (P N E), that is, the set of strategy profiles in which no player possesses an improving deviation.

Consider the social function $\mathrm {S}\textsc {um}:{\mathsf {\Sigma }}\mapsto \mathbb {R}_{\geq 0}$ defined as the sum of the players’ costs, that is, $\mathrm {S}\textsc {um}({s})={\sum }_{i\in [n]}c_{i}({s})$ and let s ^∗ be the strategy profile minimizing it. Given an 𝜖 ≥ 0 and a weighted congestion game ${\mathcal G}$, let ${\mathcal E}_{\epsilon }({\mathcal G})$ be the set of (1 + 𝜖)-approximate Nash equilibria of ${\mathcal G}$.

Definition 2

The 𝜖-approximateprice of anarchy of ${\mathcal G}$ is defined as $\mathsf {PoA}_{\epsilon }({\mathcal G})=\max _{{s}\in {\mathcal E}_{\epsilon }({\mathcal G})}\left \{\frac {\mathrm {S}\textsc {um}({ s})}{\mathrm {S}\textsc {um}({s}^{*})}\right \}$, while the 𝜖-approximateprice of stability of ${\mathcal G}$ is defined as $\mathsf {PoS}_{\epsilon }({\mathcal G})=\min _{{s}\in {\mathcal E}_{\epsilon }({\mathcal G})}\left \{\frac {\mathrm {S}\textsc {um}({s})}{\mathrm {S}\textsc {um}({s}^{*})}\right \}$.

Definition 3

Given a strategy profile s and a player i ∈ [n], a strategy t ^∗∈# #Σ# # _i is a best-response for player i in s if c _i (s _−i ◇ t ^∗) ≤ c _i (s _−i ◇ t) for any t ∈# #Σ# # _i .

Let s ^∅ be the empty state, i.e., the profile in which no player has performed any strategic choice yet.

Definition 4

A one-round walk starting from the empty state is an (n + 1)-tuple of strategy profiles $W=({s}^{W}_{0},{ s}^{W}_{1},\ldots ,{s}^{W}_{n})$ such that ${s}^{W}_{0}={s}^{\emptyset }$ and, for any i ∈ [n], ${ s}^{W}_{i}={s}^{W}_{i-1}\diamond t^{*}$, where t ^∗ is a best-response for player i in ${s}^{W}_{i-1}$. The profile ${s}^{W}_{n}$ is called the strategy profile achieved after the one-round walk W.

Clearly, depending on how the players are ordered from 1 to n and on which best-response is selected at step i when more than one best-response is available to player i in ${s}^{W}_{i-1}$, different one-round walks can be generated. Let ${\mathcal W}({\mathcal G})$ denote the set of all possible one-round walks which can be generated in game ${\mathcal G}$.

Definition 5

The approximation ratio of the strategy profiles achievedafter a one-round walk starting from the empty state in ${\mathcal G}$ is defined as $\mathsf {Apx}^{1}_{\emptyset }({\mathcal G})=\max _{W\in {\mathcal W}({\mathcal G})}\left \{\frac {\mathrm {S}\textsc {um}({s}^{W}_{n})}{\mathrm {S}\textsc {um}({s}^{*})}\right \}$.

3 The Primal-Dual Technique

Fix a weighted congestion game ${\mathcal G}$, a social function $\mathcal F$ and a class of self-emerging strategy profiles $\mathcal E$. Let ${s}^{*}=(s_{1}^{*},\ldots ,s_{n}^{*})$ be the strategy profile optimizing $\mathcal F$ and ${s}=(s_{1},\ldots ,s_{n})\in \mathcal E({\mathcal G})$ be the worst-case strategy profile in $\mathcal E({\mathcal G})$ with respect to $\mathcal F$. For any e ∈ E, we set, for the sake of brevity, $O_{e}={\mathcal L}_{e}({s}^{*})$ and $K_{e}={\mathcal L}_{e}({s})$. Note that both O _e and K _e belong to the set of non-negative integers when ${\mathcal G}$ is unweighted, while, otherwise, they belong to the set of non-negative reals.

Since s ^∗ and s are fixed, we can maximize the inefficiency yielded by the pair of profiles (s,s ^∗) by suitably choosing the coefficients α _e,i , for each e ∈ E and 0 ≤ i≤ d, so that ${\mathcal F}({s})$ is maximized, ${\mathcal F}({s})$ is normalized to one¹ and s meets all the constraints defining the set $\mathcal E(\mathcal G)$. For the sets $\mathcal E$ and social functions $\mathcal F$ considered in this paper, this task can be easily achieved by creating a suitable linear program L P(s,s ^∗), (see, for instance, the linear program L P(s,s ^∗) defined at page 9 for bounding P o A _𝜖 , or the linear program L P(s,s ^∗) defined at page 16 for bounding $\mathsf {Apx}^{1}_{\emptyset }$).

By providing a feasible solution for the dual program D L P(s,s ^∗), we can obtain an upper bound on the optimal solution of L P(s,s ^∗). Our task is to uncover, among all possibilities, the pair $(\overline {{s}},\overline {{s}}^{*})$ yielding the highest possible optimal solution for L P(s,s ^∗). To this aim, the study of the dual formulation plays a crucial role. Since the set of variables of L P(s,s ^∗) is given by the set of coefficients α _e,i , for each e ∈ E and 0 ≤ i ≤ d, we shall have a dual constraint for each e ∈ E and 0 ≤ i ≤ d. Any such constraint will depend on the identities of the players using e in both s and s ^∗ (see, for instance, the linear program D L P(s,s ^∗) defined at page 10 for bounding P o A _𝜖 , or the linear program D L P(s,s ^∗) defined at page 16 for bounding $\mathsf {Apx}^{1}_{\emptyset }$). Since the power set of a set of n elements has cardinality 2ⁿ, and we have two possible subsets of users (the one in s and the one in s ^∗), for a game with n players, we can have up to 4ⁿ different dual constraint for each fixed e ∈ E and 0 ≤ i ≤ d, some of which might be “harder” to satisfy than the others. Hence, if we are able to detect the nature of the “worst-case” dual constraints, then we can easily figure out the form of the pair $(\overline {{s}},\overline {{s}}^{*})$ maximizing the inefficiency of the class of strategy profiles $\mathcal E$. Put in other words, our task is to determine suitable dual variables, in particular the ones minimizing the dual objective function, which are able to satisfy each of the infinitely many dual constraints (obtained by considering all possible values for the number of players n) that can be generated by our formulation, when varying the pair (s,s ^∗). The worst-case dual constraints we are looking for, then, will be the ones which are tight, i.e., satisfied at equality.

Clearly, by the complementary slackness conditions, if we find the optimal dual solution, then we can quite systematically construct the matching primal instance by choosing a suitable set of players and resources so as to implement all the tight dual constraints. This task is much more complicated to be achieved in the weighted case, because, once established the congestion values K _e and O _e for any e ∈ E, there are still infinitely many ways to split them among the players using resource e in both s and s ^∗, whereas, in the unweighted case, such a splitting is univocal.

4 Application to Affine Latency Functions

In order to easily illustrate our primal-dual technique, in this section we consider the well-known and studied case of affine latency functions and social function Sum and show how the results for the P o A _𝜖 , the P o S _𝜖 and the $\mathsf {Apx}^{1}_{\emptyset }$ already known in the literature can be reobtained in a unified manner for both weighted and unweighted players. Before proceeding with the application of the primal-dual method, we show how to simplify the parameters defining the general expression of affine latency functions without losing in generality.

Game ${\mathcal G}^{\prime }=([n],E^{\prime },({\mathsf {\Sigma }}^{\prime }_{i})_{i\in [n]},(\ell ^{\prime }_{e})_{e\in E},(w_{i})_{i\in [n]})$ is equivalent to game ${\mathcal G}=([n],E,({\mathsf {\Sigma }}_{i})_{i\in [n]},(\ell _{e})_{e\in E},(w_{i})_{i\in [n]})$ if there exist n bijections φ _i :# #Σ# # _i ↦# #Σ# # i′, one for each i ∈ [n], such that, for any strategy profile s = (s ₁,…,s _n ) ∈# #Σ# #, it holds that c _i (s) = c _i (φ ₁(s ₁),…,φ _n (s _n )) for any i ∈ [n].

Lemma 1

For each weighted congestion game with affine latency functions ${\mathcal G}=([n],E,({\mathsf {\Sigma }}_{i})_{i\in [n]},(\ell _{e})_{e\in E},(w_{i})_{i\in [n]})$ there always exists an equivalent weighted congestion game with linear latency functions ${\mathcal G}^{\prime }=([n],E^{\prime },({\mathsf {\Sigma }}^{\prime }_{i})_{i\in [n]}, (\ell ^{\prime }_{e})_{e\in E},$(w _i ) _i∈[n]), i.e., such that ℓ e′(x) = α _e,1 x := α _e x for any e ∈ E ^′ .

Proof

Consider the weighted congestion game ${\mathcal G}=([n],E,({\mathsf {\Sigma }}_{i})_{i\in [n]}, (\ell _{e})_{e\in E},$(w _i ) _i∈[n]) with latency functions ℓ _e (x) = α _e x + β _e for any e ∈ E. For each $\widetilde {e}\in E$ such that $\beta _{\widetilde {e}} > 0$, let $N_{\widetilde {e}}$ be the set of players who can choose $\widetilde {e}$, that is, $N_{\widetilde {e}}=\{i\in [n]:\exists s\in {\Sigma }_{i}: \widetilde {e}\in s\}$. The set of resources E ^′ is obtained by replicating all the resources in E and adding a new resource $e_{\widetilde {e}}^{i}$ for any $\widetilde {e}\in E$ and any $i\in N_{\widetilde {e}}$, that is, $E^{\prime }=E\cup \bigcup _{\widetilde {e}\in E,i\in N_{\widetilde {e}}}\{e_{\widetilde {e}}^{i}\}$. The latency functions are defined as $\ell ^{\prime }_{e}(x)=\alpha _{e} x$ for any e ∈ E ^′∩ E and $\ell ^{\prime }_{e_{\widetilde {e}}^{i}}(x)=\frac {\beta _{\widetilde {e}}}{w_{i}} x$ for any $\widetilde {e}\in E$ and any $i\in N_{\widetilde {e}}$. Finally, for each i ∈ [n], the bijection φ _i is defined as follows: $\varphi _{i}(s)=s\cup \bigcup _{\widetilde {e}\in s}\{e^{i}_{\widetilde {e}}\}$. It is not difficult to see that for any s = (s ₁,…,s _n ) ∈# #Σ# # and for any i ∈ [n], it holds that c _i (s) = c _i (φ ₁(s ₁),…,φ _n (s _n )). □

As a consequence of Lemma 1, throughout this section, we restrict to latency functions of the form ℓ _e (x) = α _e x, for any e ∈ E. In such a setting, we can rewrite the social value of a strategy profile as $\mathrm {S}\textsc {um}({s})={\sum }_{e\in E}(\alpha _{e} {\mathcal L}_{e}({s})^{2})$.

4.1 Bounding the Approximate Price of Anarchy

Since s is a P N E _𝜖 , it follows that, for any i ∈ [n],

$$c_{i}({s})=\sum\limits_{e\in s_{i}}(\alpha_{e} K_{e})\leq (1+\epsilon)c_{i}({s}_{-i}\diamond s_{i}^{*})\leq(1+\epsilon)\sum\limits_{e\in s_{i}^{*}}(\alpha_{e}(K_{e}+w_{i})).$$

Thus, the primal formulation L P(s,s ^∗) assumes the following form.

$$\begin{array}{@{}rcl@{}} \begin{array}{ll} maximize \displaystyle\sum\limits_{e\in E}\left( \alpha_e K_e^2\right)\\\vspace{0.1cm} subject\ to\\\vspace{0.1cm} \displaystyle\sum\limits_{e\in s_i}\left( \alpha_e K_e\right)-(1+\epsilon)\sum\limits_{e\in s_i^{*}}\left( \alpha_e (K_e+w_i)\right)\leq 0, & \ \ \forall i\in [n]\\\vspace{0.1cm} \displaystyle\sum\limits_{e\in E}\left( \alpha_e O_e^2\right) = 1,\\\vspace{0.1cm} \alpha_e\geq 0, & \ \ \forall e\in E \end{array} \end{array} $$

The dual program D L P(s,s ^∗) is

$$\begin{array}{@{}rcl@{}} \begin{array}{ll} minimize\ \gamma\\\vspace{0.1cm} subject\ to\\\vspace{0.1cm} \displaystyle\sum\limits_{i:e\in s_i}\left( y_i K_e\right)-(1+\epsilon)\sum\limits_{i:e\in s_i^{*}}\left( y_i (K_e+w_i)\right)+\gamma O_e^2 \geq K_e^2, & \ \ \forall e\in E\\\vspace{0.1cm} y_i\geq 0, & \ \ \forall i\in [n] \end{array} \end{array} $$

Define $\psi =\frac {1+\epsilon +\sqrt {\epsilon ^{2}+ 6\epsilon + 5}}{2}$ and z = ⌊ψ⌋. For unweighted players, we reobtain the upper bound proved by Christodoulou, Koutsoupias and Spirakis in [25] with a much simpler and shorter proof, while, for the weighted case, we give the first known upper bound.

Theorem 1

For any fixed 𝜖 ≥ 0, $\mathsf {PoA}_{\epsilon }({\mathcal G})\leq \frac {(1+\epsilon )(z^{2}+ 3z + 1)}{2z-\epsilon }$ for any $\mathcal G\in \mathcal UCG$ and $\mathsf {PoA}_{\epsilon }({\mathcal G})\leq \psi ^{2}$ for any $\mathcal G\in \mathcal WCG$ .

Proof

For $\mathcal G\in \mathcal UCG$, since w _i = 1 for each i ∈ [n], by choosing $y_{i}=\frac {2z + 1}{2z-\epsilon }$ for any i ∈ [n] and $\gamma =\frac {(1+\epsilon )(z^{2}+ 3z + 1)}{2z-\epsilon }$ (note that the definition of z guarantees that 2z − 𝜖 > 0, so that y _i ≥ 0 for each i ∈ [n]), the first dual constraint becomes of the form

$$\frac{2z + 1}{2z-\epsilon}\left( {K_{e}^{2}}-(1+\epsilon)(K_{e}+ 1)O_{e}\right)+\frac{(1+\epsilon)(z^{2}+ 3z + 1)}{2z-\epsilon} {O_{e}^{2}}\geq {K_{e}^{2}} $$

which is equivalent to

$$\begin{array}{@{}rcl@{}} {K_{e}^{2}}-(2z + 1)(K_{e} O_{e}+O_{e})+(z^{2}+ 3z + 1){O_{e}^{2}} & \geq & 0. \end{array} $$

(1)

Easy calculations show that this is always satisfied for any pair of non-negative integers(K _e ,O _e ). In fact, for O _e = 0, inequality (1) becomes ${K_{e}^{2}}\geq 0$ which is always true. For O _e = 1, inequality (1) becomes ${K_{e}^{2}}-(2z + 1)K_{e}+z^{2}+z\geq 0$ which is always satisfied for any K _e ≤ z and K _e ≥ z + 1 and, since z is a positive integer, it follows that inequality (1) is satisfied for any integer K _e . Finally, for O _e ≥ 2, the equation associated with inequality (1) has no real solution when solved for K _e (its discriminant is negative), which implies that inequality (1) is satisfied for any value of K _e . For an illustration on how the dual variables can be computed, see Section I in the Appendix.

For $\mathcal G\in \mathcal WCG$, by choosing $y_{i}=\left (1+\frac {\sqrt {1+\epsilon }}{\sqrt {5+\epsilon }}\right )w_{i}$ for any i ∈ [n] and γ = ψ ², the first dual constraint is satisfied when

$$\left( 1+\frac{\sqrt{1+\epsilon}}{\sqrt{5+\epsilon}}\right)\left( {K_{e}^{2}}-(1+\epsilon)\left( K_{e} O_{e}+{O_{e}^{2}}\right)\right)+\psi^{2} {O_{e}^{2}}\geq {K_{e}^{2}} $$

which is equivalent to

$$\begin{array}{@{}rcl@{}} \frac{\sqrt{1+\epsilon}}{\sqrt{5+\epsilon}}{K_{e}^{2}}-\left( 1+\frac{\sqrt{1+\epsilon}}{\sqrt{5+\epsilon}}\right)(1+\epsilon)(K_{e} O_{e}+{O_{e}^{2}})+\psi^{2} {O_{e}^{2}} & \geq & 0. \end{array} $$

(2)

Note that, since $\frac {\sqrt {1+\epsilon }}{\sqrt {5+\epsilon }}\left (1+\frac {\sqrt {1+\epsilon }}{\sqrt {5+\epsilon }}\right )(1+\epsilon )= 2\psi$ and $\frac {\sqrt {1+\epsilon }}{\sqrt {5+\epsilon }}\psi ^{2}-2\psi =\psi$, inequality (2) can be rewritten as ${K_{e}^{2}}-2\psi K_{e} O_{e}+\psi ^{2} {O_{e}^{2}}=(K_{e}-\psi O_{e})^{2}\geq 0$ which is always satisfied for any pair of reals(K _e ,O _e ). □

When 𝜖 = 0, we reobtain the well-known price of anarchy of 5/2 and $(3+\sqrt {5})/2$ which hold for P N E in the unweighted and weighted case, respectively. Note that, when ψ = z, it holds that $\psi ^{2}=\frac {(1+\epsilon )(z^{2}+ 3z + 1)}{2z-\epsilon }$. Hence, interestingly enough, the P o A _𝜖 in the weighted and unweighted cases coincide for all 𝜖 ≥ 0 such that $\frac {1+\epsilon +\sqrt {\epsilon ^{2}+ 6\epsilon + 5}}{2}$ is a natural number.

4.1.1 Analysis of the Dual Constraints

We now illustrate how the dual formulation can be also used to discover a matching lower bounding instance or to figure out its general structure.

Unweighted case

For P N E, that is the case of 𝜖 = 0, the dual constraints (1) get tight only for pairs (K _e ,O _e ) of the form (1,1) and (2,1). Thus, if the 5/2 upper bound is tight, the complementary slackness conditions assure us that, in the matching lower bounding instance, only resources implementing the pairs (1,1) and (2,1) are needed. This can be easily achieved through a game using 3 players and 3 resources and defined as follows: # #Σ# # ₁ = {{e ₁,e ₂},{e ₃}}, # #Σ# # ₂ = {{e ₁},{e ₂,e ₃}}, # #Σ# # ₃ = {{e ₂},{e ₃}} and α ₁ = 5, α ₂ = 2, α ₃ = 3. For such an instance, we have s = ({e ₁,e ₂},{e ₂,e ₃},{e ₃}) and s ^∗ = ({e ₃},{e ₁},{e ₂}) for a price of anarchy of 5/2. Clearly, this instance can be extended to any number of players n > 3 by adding a fourth resource e ₄ with α ₄ = 0 and setting # #Σ# # _i = {e ₄} for any i ∈ [n] with i ≥ 4. Note that these are minimal lower bounding instances (the previous known lower bounding instances presented by Christodoulou and Koutsoupias in [23] used 2n resources for any n ≥ 3).

More generally, for P N E _𝜖 , the dual constraints (1) get tight only for pairs of the form (z,1) and (z + 1,1). Thus, in order to obtain a matching lower bounding instance, we only need to implement this family of dual constraints, that is, we need an instance with at least z + 2 players and a set of resources such that O _e = 1 and K _e ∈{z,z + 1} for any e ∈ E. In fact, the matching lower bounding instances given by Christodoulou, Koutsoupias and Spirakis in [25] use z + 2 players and 2z + 4 resources, half of which has K _e = z and the other half has K _e = z + 1. It is easy to see that these instances are not minimal. In fact, they produce a dual program with z + 3 variables and 2z + 4 constraints, where only z + 3 constraints are sufficient to exactly characterize the optimal dual solution. Unfortunately, this set of constraints changes as a function of 𝜖 and so it is not easy to achieve a general scheme of minimal lower bounding instances.

Weighted case

The dual constraints (2) get tight only for pairs (K _e ,O _e ) such that K _e = ψ O _e . For P N E, that is the case 𝜖 = 0, consider the game with 3 players and 3 resources with w ₁ = 1, $w_{2}=w_{3}=(1+\sqrt {5})/2$, # #Σ# # ₁ = {{e ₁},{e ₂,e ₃}}, # #Σ# # ₂ = {{e ₂},{e ₁,e ₃}}, # #Σ# # ₃ = {{e ₃},{e ₂}}, α ₁ = 2, $\alpha _{2}=\sqrt {5}-1$ and $\alpha _{3}= 3-\sqrt {5}$. We have s = ({e ₂,e ₃},{e ₁,e ₃},{e ₂}) and s ^∗ = ({e ₁},{e ₂},{e ₃}) for a price of anarchy equal to $(3+\sqrt {5})/2$. Again, we have identified a minimal lower bounding instance which is slightly simpler than the previous one given by Awerbuch, Azar and Epstein in [4] which used 4 players and 3 resources.

For general values of 𝜖, we are able to provide tight lower bounds only for a subset, although having infinite cardinality, of values of 𝜖. Let t and y be two positive integers such that 1 ≤ y ≤ t + 1. We set $\epsilon (t,y)=\frac {(t-1)\sqrt {t^{2}+ 4y}+ 2y+t^{2}-t-2}{\sqrt {t^{2}+ 4y}+t + 2}$, which is always non-negative since y ≥ 1 and yields $\psi =\frac {t+\sqrt {t^{2}+ 4y}}{2}>t$. We create an instance with t + 2 players and 2(t + 1) resources, where w _i = 1 for any i ∈ [t + 1] and w _t+ 2 = ψ − t. The first t + 1 resources (e _j ) _j∈[t+ 1] have latency ℓ(x) = x, while the last t + 1 resources (e j′) _j∈[t+ 1] have latency ℓ(x) = x/y. The set of strategies for each player i ∈ [t + 1] is ${\mathsf {\Sigma }}_{i}=\{\{e_{i}\},\bigcup _{j\in [t]}\{e_{i+j}\}\cup \bigcup _{j\in [y]}\{e^{\prime }_{i+j}\}\}$, with the sum of the indices taken circularly, while ${\mathsf {\Sigma }}_{t + 2}=\{\bigcup _{j\in [t + 1]}\{e^{\prime }_{j}\},\bigcup _{j\in [t + 1]}\{e_{j}\}\}$. The first strategy of each player is the optimal one, while the second strategy is the one played at the P N E _𝜖(t,y). Note that, for any e, we have K _e = ψ O _e , thus implying P o A _𝜖 = ψ ². It is not difficult to show that s is a (1 + 𝜖(t,y)) −P N E by exploiting the equality $2\psi =t+\sqrt {t^{2}+ 4y}$.

Deriving a tight lower bound for any possible value of 𝜖 remains an interesting open problem.

4.2 Bounding the Approximate Price of Stability

In this case, we have two different approaches for unweighted and weighted games, respectively.

4.2.1 Unweighted Case

Recall that, since the P o S _𝜖 is a best-case measure, the primal-dual approach guarantees a tight analysis only if we are able to exactly characterize the polyhedron defining the set of the best quality P N E _𝜖 . It is not known how to do this at the moment, thus all the approaches used so far in the literature approximate the best quality P N E _𝜖 with a P N E _𝜖 minimizing a certain potential function. Christodoulou, Koutsoupias and Spirakis [25] showed that, for unweighted players, any strategy profile s which is a local minimum of the function

$${\Phi}_{\epsilon}({s})=\frac 1 2 \sum\limits_{e\in E}\left( \alpha_{e}\left( {\mathcal L}_{e}({s})^{2}+\frac{1-\epsilon}{1+\epsilon}{\mathcal L}_{e}({s})\right)\right), $$

called 𝜖-approximate potential, is a P N E _𝜖 . Thus, it is possible to get an upper bound on the P o S _𝜖 by bounding the P o A _𝜖 of the global minimum of Φ _𝜖 .

We now illustrate our approach which yields the same $\frac {1+\sqrt {3}}{\epsilon +\sqrt {3}}$ upper bound achieved by Christodoulou, Koutsoupias and Spirakis in [25]. Assume that s is the global minimum of Φ _𝜖 . We can use the inequality Φ _𝜖 (s) ≤Φ _𝜖 (s ^∗) which results in the constraint

$$ \sum\limits_{e\in E}\left( \alpha_{e} \left( {K^{2}_{e}}+\frac{1-\epsilon}{1+\epsilon}K_{e}-{O^{2}_{e}}-\frac{1-\epsilon}{1+\epsilon}O_{e}\right)\right)\leq 0. $$

(3)

Moreover, it also holds that ${\sum }_{i\in [n]}\left ({\Phi }_{\epsilon }({s})-{\Phi }_{\epsilon }({s}_{-i}\diamond s_{i}^{*})\right )\leq 0$. Such an inequality can be expressed as a function of K _e , O _e and 𝜖 as follows:

$$\begin{array}{@{}rcl@{}} & & {\Phi}_{\epsilon}({s})-{\Phi}_{\epsilon}({s}_{-i}\diamond s_{i}^{*})\\ & = & \frac 1 2 \displaystyle\sum\limits_{e\in s_{i}\setminus s_{i}^{*}}\left( \alpha_{e}\left( {K_{e}^{2}}+\frac{1-\epsilon}{1+\epsilon}K_{e}-(K_{e}-1)^{2}-\frac{1-\epsilon}{1+\epsilon}(K_{e}-1)\right)\right)\\ & & + \frac 1 2 \displaystyle\sum\limits_{e\in s_{i}^{*}\setminus s_{i}}\left( \alpha_{e}\left( {K_{e}^{2}}+\frac{1-\epsilon}{1+\epsilon}K_{e}-(K_{e}+ 1)^{2}-\frac{1-\epsilon}{1+\epsilon}(K_{e}+ 1)\right)\right)\\ & = & \displaystyle\sum\limits_{e\in s_{i}\setminus s_{i}^{*}}\left( \alpha_{e}\left( K_{e}-\frac{\epsilon}{1+\epsilon}\right)\right)-\displaystyle\sum\limits_{e\in s_{i}^{*}\setminus s_{i}}\left( \alpha_{e}\left( K_{e}+\frac{1}{1+\epsilon}\right)\right). \end{array} $$

Now, for each e ∈ E, define ${\Delta }_{e}=|\left \{i\in [n]:e\in s_{i}\cap s_{i}^{*}\right \}|$. By summing up for each i ∈ [n], we obtain

$$\begin{array}{@{}rcl@{}} & & \displaystyle\sum\limits_{i\in [n]}\left( {\Phi}_{\epsilon}({s})-{\Phi}_{\epsilon}({s}_{-i}\diamond s_{i}^{*})\right)\\ & = & \displaystyle\sum\limits_{i\in [n]}\left( \displaystyle{\sum}_{e\in s_{i}\setminus s_{i}^{*}}\left( \alpha_{e}\left( K_{e}-\frac{\epsilon}{1+\epsilon}\right)\right)-\displaystyle{\sum}_{e\in s_{i}^{*}\setminus s_{i}}\left( \alpha_{e}\left( K_{e}+\frac{1}{1+\epsilon}\right)\right)\right)\\ & = & \displaystyle\sum\limits_{e\in E}\left( \alpha_{e} \left( \left( K_{e}-\frac{\epsilon}{1+\epsilon}\right)(K_{e}-{\Delta}_{e})-\left( K_{e} +\frac{1}{1+\epsilon}\right)(O_{e}-{\Delta}_{e})\right)\right)\\ & \geq & \displaystyle\sum\limits_{e\in E}\left( \alpha_{e} \left( {K^{2}_{e}}-\frac{\epsilon}{1+\epsilon}K_{e}-K_{e} O_{e}-\frac{1}{1+\epsilon}O_{e}\right)\right), \end{array} $$

which implies

$$ \sum\limits_{e\in E}\left( \alpha_{e} \left( {K^{2}_{e}}-\frac{\epsilon}{1+\epsilon}K_{e}-K_{e} O_{e}-\frac{1}{1+\epsilon}O_{e}\right)\right)\leq 0. $$

(4)

Thanks to (3) and (4), the dual formulation becomes:

$$\begin{array}{@{}rcl@{}} \begin{array}{ll} minimize\ \gamma\\\vspace{0.1cm} subject\ to\\\vspace{0.1cm} K_e^2(y+z)+\frac{K_e}{1+\epsilon}(y(1-\epsilon)-z\epsilon)\\ -\left( y O_e^2+z K_e O_e+\frac{O_e}{1+\epsilon}(y(1-\epsilon)+z)\right)+\gamma O_e^2 \geq K_e^2, & \ \ \forall e\in E\\\vspace{0.1cm} y,z \geq 0 \end{array} \end{array} $$

Thus, for unweighted players, we obtain the following result for any 𝜖 ∈ [0,1) (this is the only interesting case, since Christodoulou, Koutsoupias and Spirakis [25] show that, for any 𝜖 ≥ 1, $\mathsf {PoS}_{\epsilon }({\mathcal G})= 1$ for any $\mathcal G$).

Theorem 2

For any fixed 𝜖 ∈ [0,1), $\mathsf {PoS}_{\epsilon }({\mathcal G})\leq \frac {1+\sqrt {3}}{\epsilon +\sqrt {3}}$ for any $\mathcal G\in \mathcal UCG$ .

Proof

By choosing $y=\frac {2\epsilon +\sqrt {3}(1+\epsilon )}{2(\epsilon +\sqrt {3})}$, $z=\frac {1-\epsilon }{\epsilon +\sqrt {3}}$ and $\gamma =\frac {1+\sqrt {3}}{\epsilon +\sqrt {3}}$, the first dual constraint becomes of the form

$$\begin{array}{@{}rcl@{}} (\epsilon-1)((\sqrt{3}-2){K_{e}^{2}}+(2O_{e}-\sqrt{3})K_{e}+(2+\sqrt{3})(O_{e}-{O_{e}^{2}}))\geq 0. \end{array} $$

(5)

Easy calculations show that this is always satisfied for any pair of non-negative integers (K _e ,O _e ). In fact, for O _e = 0, inequality (5) becomes $K_{e}((2-\sqrt {3})K_{e}+\sqrt {3})(1-\epsilon )\geq 0$ which is always satisfied for any non-negative integer K _e since 𝜖 < 1. For O _e = 1, inequality (5) becomes K _e (K _e − 1)(1 − 𝜖) ≥ 0 which is always satisfied for any non-negative integer K _e since 𝜖 < 1. Finally, for any O _e ≥ 2, the equation associated with inequality (5) has no real solution when solved for K _e (its discriminant is negative), which implies that inequality (5) is satisfied for any value of K _e . □

Analysis of the Dual Constraints

The dual constraint (5) gets tight only for pairs (K _e ,O _e ) of the form (0,1) and (1,1) which are clearly insufficient to achieve a P o S _𝜖 greater than 1, since K _e ≤ O _e for any e ∈ E. What is going on here? The answer is that the lower bound on the P o S _𝜖 can be achieved only asymptotically, that is, when n tends to infinity. Thus, we must also check what happens when both K _e and O _e goes to infinity and their ratio remains constant. We obtain that the dual constraint (5) is asymptotically tight for pairs of the form (K _e ,O _e ) such that $K_{e}=(2+\sqrt {3})O_{e}$ and O _e goes to infinity. The lower bounding instances proposed by Christodoulou, Koutsoupias and Spirakis in [25] have n ₁ resources of type (0,1), n ₁(n ₁ − 1) resources of type (1,1) and one resource of type $\left (n_{1},\frac {\sqrt {2\epsilon ^{4}+ 3\epsilon ^{3}+\epsilon + 3}+ 2\epsilon ^{2}+ 2\epsilon -1}{\sqrt {2\epsilon ^{4}+ 3\epsilon ^{3}+\epsilon + 3}+\epsilon ^{2}+\epsilon + 1}n_{1}\right )$ with n ₁ going to infinity. Thus, such lower bounding instances possess all the combinatorics needed to implement the worst-case dual constraints, but still there is a remarkable gap between upper and lower bounds. Hence, the intuition should suggest that the upper bound is not tight and that additional constraints should be used in the primal formulation so as to better characterize the polyhedron defining the best P N E _𝜖 . Note that the inequalities stating the s is a P N E _𝜖 is of no use here since they are dominated by the inequality ${\sum }_{i\in [n]}\left ({\Phi }_{\epsilon }({s})-{\Phi }_{\epsilon }({s}_{-i}\diamond s_{i}^{*})\right )\leq 0$.

4.2.2 Weighted Case

In order to deal with the weighted case, it is possible to rephrase the approach of Christodoulou, Koutsoupias and Spirakis [25] to turn the potential given by Fotakis, Kontogiannis and Spirakis in [29] for weighted linear congestion games into an 𝜖-potential function for this class of games so as to use the same approach as in the unweighted case.

We define the following 𝜖-potential function.

$${\Phi}_{\epsilon}({s})=\frac 1 2 \sum\limits_{e\in E}\left( \alpha_{e} {\mathcal L}_{e}({ s})^{2}\right)+\frac{1-\epsilon}{2(1+\epsilon)}\sum\limits_{e\in E}\sum\limits_{i:e\in s_{i}}\left( \alpha_{e} {w_{i}^{2}}\right). $$

Lemma 2

Any profile which is a local minimum ofΦ _𝜖 is a P N E _𝜖 .

Proof

Consider a profile s = (s ₁,…,s _n ). We want to compute the change in the 𝜖-potential function when player i changes her strategy from s _i to t. The resulting profile s _−i ◇ t has

$$\begin{array}{@{}rcl@{}} {\mathcal L}_e({s}_{-i}\diamond t) =\left\{ \begin{array}{lc} {\mathcal L}_e({s})-w_i, & \ \ e\in s_i\setminus t,\\ {\mathcal L}_e({s})+w_i, & \ \ e\in t\setminus s_i,\\ {\mathcal L}_e({s}), & \ \ otherwise. \end{array}\right. \end{array} $$

From this we can compute the difference

$$\begin{array}{@{}rcl@{}} & & {\Phi}_{\epsilon}({s}_{-i}\diamond t)-{\Phi}_{\epsilon}({s})\\ & = & \sum\limits_{e\in t\setminus s_{i}}\left( \alpha_{e}\left( w_{i} {\mathcal L}_{e}({ s})+\frac{{w_{i}^{2}}}{1+\epsilon}\right)\right)-\sum\limits_{e\in s_{i}\setminus t}\left( \alpha_{e}\left( w_{i} {\mathcal L}_{e}({ s})-\frac{\epsilon {w_{i}^{2}}}{1+\epsilon}\right)\right). \end{array} $$

We can rewrite this as

$$\begin{array}{@{}rcl@{}} & & {\Phi}_{\epsilon}({s}_{-i}\diamond t)-{\Phi}_{\epsilon}({s})\\ & =\! & \sum\limits_{e\in t}\left( \alpha_{e}\!\left( w_{i} {\mathcal L}_{e}({ s})\!+\frac{{w_{i}^{2}}}{1+\epsilon}\right)\right)\,-\,\sum\limits_{e\in t \cap s_{i}}\left( \alpha_{e} {w_{i}^{2}}\right)\,-\,\sum\limits_{e\in s_{i}}\left( \alpha_{e}\!\left( w_{i} {\mathcal L}_{e}({s})\!-\frac{\epsilon {w_{i}^{2}}}{1+\epsilon}\right)\right). \end{array} $$

Suppose now that s is a local minimum of Φ _𝜖 which implies Φ _𝜖 (s) ≤Φ _𝜖 (s _−i ◇ t) for any i ∈ [n] and t ∈Σ _i . The cost of player i before the change is $c_{i}({s})={\sum }_{e\in s_{i}}\left (\alpha _{e} {\mathcal L}_{e}({s})\right )$ and after the change is $c_{i}({s}_{-i}\diamond t)={\sum }_{e\in t}\left (\alpha _{e} {\mathcal L}_{e}({s}_{-i}\diamond t)\right )$. We show that s is a P N E _𝜖 , that is, c _i (s) ≤ (1 + 𝜖)c _i (s _−i ◇ t).

By exploiting the two different parts defining the 𝜖 potential function, we obtain

$$c_{i}({s})=\sum\limits_{e\in s_{i}}\left( \alpha_{e} {\mathcal L}_{e}({s})\right)\leq\sum\limits_{e\in s_{i}}\left( \alpha_{e}(1+\epsilon) \left( {\mathcal L}_{e}({s})-\frac{\epsilon w_{i}}{1+\epsilon}\right)\right)$$

which holds because ${\mathcal L}_{e}({s})\geq w_{i}$ when e ∈ s _i , and

$$\begin{array}{@{}rcl@{}} c_{i}({s}_{-i}\diamond t) & = & \sum\limits_{e\in t}\left( \alpha_{e} ({\mathcal L}_{e}({s}_{-i}\diamond t)+w_{i})\right)-\sum\limits_{e\in t \cap s_{i}}\left( \alpha_{e} w_{i}\right)\\ & \geq & \sum\limits_{e\in t}\left( \alpha_{e} \left( {\mathcal L}_{e}({s})+\frac{w_{i}}{1+\epsilon}\right)\right)-\sum\limits_{e\in t \cap s_{i}}\left( \alpha_{e} w_{i}\right). \end{array} $$

which holds for any 𝜖 ≥ 0.

It follows immediately that c _i (s) ≤ (1 + 𝜖)c _i (s _−i ◇ t), thus s is a P N E _𝜖 . □

Using the constraint Φ _𝜖 (s) −Φ _𝜖 (s ^∗) ≤ 0 in our formulation, we can easily prove the following theorem.

Theorem 3

For any fixed 𝜖 ∈ [0;1], $\mathsf {PoS}_{\epsilon }({\mathcal G})\leq \frac {2}{1+\epsilon }$ for any $\mathcal G\in \mathcal WCG$ .

Proof

In such a case, by choosing y _i = 0 for any i ∈ [n], z = 1 and $y_{n + 1}=\frac {2}{1+\epsilon }$, the first dual constraint becomes of the form

$$\frac{1-\epsilon}{1+\epsilon}K_{e}\geq 0 $$

which is always satisfied for any pair of non-negative reals (K _e ,O _e ). □

In this case, no specific lower bounds are known, besides the ones with unweighted players.

4.3 Bounding the Approximation Ratio of One-Round Walks

For a one-round walk W, we set ${s}={s}_{n}^{W}$. Define K _e (i) as the sum of the weights of the players using resource e in s before player i performs her choice. L P(s,s ^∗) in this case has the following form, where the first constraint comes from the fact that, when player i enters the game and strategy profile ${s}^{W}_{i-1}$ is already constructed, this player chooses s _i instead of $s_{i}^{*}$.

$$\begin{array}{@{}rcl@{}} \begin{array}{ll} maximize \ \displaystyle\sum\limits_{e\in E}\left( \alpha_e K_e^2\right)\\\vspace{0.1cm} subject\ to\\\vspace{0.1cm} \displaystyle\sum\limits_{e\in s_i}\left( \alpha_e (K_e(i)+w_i)\right)-\sum\limits_{e\in s_i^{*}}\left( \alpha_e (K_e(i)+w_i)\right) \leq 0, & \ \ \forall i\in [n]\\\vspace{0.1cm} \displaystyle\sum\limits_{e\in E}\left( \alpha_e O_e^2\right) = 1\\\vspace{0.1cm} \alpha_e \geq 0, & \ \ \forall e\in E \end{array} \end{array} $$

D L P(s,s ^∗) is as follows.

$$\begin{array}{@{}rcl@{}} \begin{array}{ll} minimize \ \gamma\\\vspace{0.1cm} subject\ to\\\vspace{0.1cm} \displaystyle\sum\limits_{i:e\in s_i}\left( y_i (K_e(i)+w_i)\right)-\sum\limits_{i:e\in s_i^{*}}\left( y_i (K_e(i)+w_i)\right)+\gamma O_e^2 \geq K_e^2, & \ \ \forall e\in E\\\vspace{0.1cm} y_i \geq 0, & \ \ \forall i\in [n] \end{array} \end{array} $$

For both unweighted and weighted players we easily reobtain the upper bounds on the $\mathsf {Apx}^{1}_{\emptyset }$ given by Christodoulou, Mirrokni and Sidiropoulos in [26].

Theorem 4

For any $\mathcal G\in \mathcal UCG$ , $\mathsf {Apx}^{1}_{\emptyset }({\mathcal G})\leq 2+\sqrt {5}$ and, for any $\mathcal G\in \mathcal WCG$ , $\mathsf {Apx}^{1}_{\emptyset }({\mathcal G})\leq 4 + 2\sqrt {3}$ .

Proof

For $\mathcal G\in \mathcal UCG$, by choosing $y_{i}= 1+\sqrt {5}$ for any i ∈ [n] and $\gamma = 2+\sqrt {5}$, since for any i such that $e\in s_{i}^{*}$ it holds that K _e (i) ≤ K _e , the first dual constraint is satisfied when

$$\left( 1+\sqrt{5}\right)\left( \frac{K_{e}(K_{e}+ 1)}{2}-(K_{e}+ 1)O_{e}\right)+\left( 2+\sqrt{5}\right){O_{e}^{2}}\geq {K_{e}^{2}} $$

which is equivalent to

$$\begin{array}{@{}rcl@{}} \left( \frac{\sqrt{5}-1}{2}\right){K_{e}^{2}}+\left( 1+\sqrt{5}\right)\left( \frac{K_{e}}{2}-K_{e} O_{e}-O_{e}\right)+(2+\sqrt{5}){O_{e}^{2}} & \geq & 0. \end{array} $$

(6)

Easy calculations show that this is always satisfied for any pair of non-negative integers(K _e ,O _e ). In fact, for O _e = 0, inequality (6) becomes $K_{e}((\sqrt {5}-1)K_{e}+\sqrt {5}+ 1)\geq 0$ which is always satisfied for any non-negative integer K _e . For O _e = 1, inequality (6) becomes $K_{e}((\sqrt {5}-1)K_{e}-\sqrt {5}-1)\geq -2$ which is always satisfied for any integer K _e . Finally, for any O _e ≥ 2, the equation associated with inequality (6) has no real solution when solved for K _e (its discriminant is negative), which implies that inequality (6) is satisfied for any non-negative integer value of K _e .

For $\mathcal G\in \mathcal WCG$, by choosing $y_{i}=\left (2+\frac {2}{\sqrt {3}}\right )w_{i}$ for any i ∈ [n] and $\gamma = 4 + 2\sqrt {3}$, since for any i such that $e\in s_{i}^{*}$ it holds that K _e (i) ≤ K _e , the first dual constraint is satisfied when

$$\left( 2+\frac{2}{\sqrt{3}}\right)\left( \sum\limits_{i\leq j:e\in {s_{i}^{K}}\cap {s_{j}^{K}}}(w_{i} w_{j})-\sum\limits_{i:e\in {s_{i}^{O}}}\left( w_{i}(K_{e}+w_{i})\right)\right)+\left( 4 + 2\sqrt{3}\right){O_{e}^{2}}\geq {K_{e}^{2}} $$

which is true if

$$\begin{array}{@{}rcl@{}} \frac{1}{\sqrt{3}}{K_{e}^{2}}-\left( 2+\frac{2}{\sqrt{3}}\right)K_{e} O_{e}+\left( 2+\frac{4}{\sqrt{3}}\right){O_{e}^{2}}\geq 0. \end{array} $$

(7)

Note that, after rearranging of the terms, inequality (7) becomes $(K_{e}-(1+\sqrt {3})O_{e})^{2}\geq 0$ which is clearly satisfied for any pair of reals(K _e ,O _e ). □

4.3.1 Analysis of the Dual Constraints

For the unweighted case, the dual constraints get tight for pairs of the form (1,1), while the asymptotical dual constraints get tight for pairs of the form $\left (\frac {3+\sqrt {5}}{2}O_{e},O_{e}\right )$. These pairs exactly characterize the structure of the lower bounding instance derived by Bilò et al. in [10]. For the weighted case, the worst case dual constraints occur when all players using resource e in the walk have weight 1, while only one player uses e in the optimal strategy profile. Moreover, the asymptotical dual constraints get tight for pairs of the form $((1+\sqrt {3})O_{e},O_{e})$. In this case, the best known lower bound, equal to $3 + 2\sqrt {2}$, has been given by Caragiannis et al. in [20].

5 Application to Quadratic and Cubic Latency Functions

In this section, we show how to use the primal-dual method to bound the P o S and the $\mathsf {Apx}^{1}_{\emptyset }$ in the case of polynomial latency functions of maximum degree d and unweighted players. We only consider the case d ≤ 3, that is, quadratic and cubic latency functions. As we will see, it is not difficult to extend the approach to any particular value of d, but it is quite hard to obtain a general result as a function of d because we do not have simple closed formulas expressing some of the summations we need in our analysis for any value of d.

First of all note that, by using the same argument exploited in the proof of Lemma 1, we can assume without loss of generality that, in all games we will consider throughout this section, the latency functions are of the form $\ell _{e}(x)={\sum }_{i = 1}^{d}\alpha _{e,i}x^{i}$, that is, without the term α _e,0.

5.1 Bounding the Price of Stability

Recall that, for any $\mathcal G\in \mathcal UCG$, Rosenthal [41] shows that any strategy profile s which is a local minimum of the potential function

$${\Phi}({s})=\sum\limits_{e\in E}\sum\limits_{x = 1}^{{\mathcal L}_{e}({s})}\ell_{e}(x)=\sum\limits_{e\in E}\sum\limits_{x = 1}^{{\mathcal L}_{e}({ s})}\sum\limits_{i = 1}^{d}(\alpha_{e,i} x^{i}) $$

is a P N E.

Let us denote with ${\Phi }_{i}({s})={\sum }_{e\in E}{\sum }_{x = 1}^{{\mathcal L}_{e}({s})}(\alpha _{e,i} x^{i})$ the contribution of the term α _e,i x ⁱ to Φ(s). We have already seen in the previous section that

$${\Phi}_{1}({s})=\frac 1 2\sum\limits_{e\in E}\left( \alpha_{e,1}({\mathcal L}_{e}({s})^{2}+{\mathcal L}_{e}({s}))\right). $$

Moreover,

$${\Phi}_{2}({s})=\frac 1 6\sum\limits_{e\in E}\left( \alpha_{e}{\mathcal L}_{e}({s})({\mathcal L}_{e}({s})+ 1)(2{\mathcal L}_{e}({s})+ 1)\right) $$

and

$${\Phi}_{3}({s})=\frac 1 4\sum\limits_{e\in E}\left( \alpha_{e}\left( {\mathcal L}_{e}({s})({\mathcal L}_{e}({s})+ 1)\right)^{2}\right). $$

According to this decomposition of Φ(s), the constraint Φ(s) ≤ Φ(s ^∗) becomes

$$\sum\limits_{i = 1}^{d}{\Phi}_{i}({s})\leq\sum\limits_{i = 1}^{d}{\Phi}_{i}({s}^{*}) $$

and the constraint ${\sum }_{i\in [n]}\left ({\Phi }({s})-{\Phi }({s}_{-i}\diamond s_{i}^{*})\right )\leq 0$ becomes

$$\sum\limits_{i = 1}^{d}\left( \sum\limits_{j\in [n]}\left( {\Phi}_{i}({s})-{\Phi}_{i}({s}_{-j}\diamond s_{j}^{*})\right)\right)\leq 0. $$

Again, as shown in the previous section,

$$\sum\limits_{i\in [n]}\left( {\Phi}_{1}({s})-{\Phi}_{1}({s}_{-i}\diamond s_{i}^{*})\right)=\sum\limits_{e\in E}\left( \alpha_{e,1}\left( {K_{e}^{2}}-K_{e} O_{e}-O_{e}\right)\right). $$

Moreover, using the same derivation as in the previous section, we obtain

$$\sum\limits_{i\in [n]}\left( {\Phi}_{2}({s})-{\Phi}_{2}({s}_{-i}\diamond s_{i}^{*})\right)=\sum\limits_{e\in E}\left( \alpha_{e,2}\left( {K_{e}^{3}}-O_{e}(K_{e}+ 1)^{2}\right)\right) $$

and

$$\sum\limits_{i\in [n]}\left( {\Phi}_{3}({s})-{\Phi}_{3}({s}_{-i}\diamond s_{i}^{*})\right)=\sum\limits_{e\in E}\left( \alpha_{e,3}\left( {K_{e}^{4}}-O_{e}(K_{e}+ 1)^{3}\right)\right). $$

Hence, for the case of d = 2, D L P(s,s ^∗) is the following.

$$\begin{array}{@{}rcl@{}} \begin{array}{ll} minimize\ \gamma\\\vspace{0.1cm} subject\ to\\\vspace{0.1cm} K_e^2(\frac y 2+z)+\frac y 2 K_e\\ -\left( \frac y 2 O_e^2+z K_e O_e+O_e\left( \frac y 2+z\right)\right)+\gamma O_e^2 \geq K_e^2, & \ \ \forall e\in E\\\vspace{0.1cm} \frac y 6 (K_e(K_e + 1)(2K_e + 1)-O_e(O_e + 1)(2O_e + 1))\\ +z(K_e^3-O_e(K_e + 1)^2)+\gamma O_e^3\geq K_e^3, & \ \ \forall e\in E\\\vspace{0.1cm} y,z \geq 0 \end{array} \end{array} $$

By analyzing the dual formulation, we obtain the following upper bound on the Po S.

Theorem 5

For any $\mathcal G\in \mathcal UCG$ with quadratic latency functions, $\mathsf {PoS}({\mathcal G})\leq 2.362$ .

Proof

The claim follows by setting y = 1.908, z = 0.453 and γ = 2.362.

Let us denote as f ₁(K _e ,O _e ) and f ₂(K _e ,O _e ), respectively, the first and second constraint of D L P(s,s ^∗).

For the first constraint, $f_{1}(0,O_{e})= 1408{O_{e}^{2}}-1407O_{e}\geq 0$ is always satisfied for any integer O _e ≥ 0, while the equation f ₁(K _e ,O _e ) = 0 has no solution (its discriminant is negative) when K _e ≥ 1. Hence, the first constraint is always satisfied for any pair of non-negative integers (K _e ,O _e ).

For the second constraint, note that $\frac {\delta f_{2}}{\delta O_{e}}(K_{e},O_{e})=-3(151{K_{e}^{2}}+ 302K_{e}-1726{O_{e}^{2}}+ 636O_{e}+ 257)$ implies that, for any fixed value of K _e , f ₂ is increasing in O _e when O _e ≥ 1. Hence, we just need to show that f ₂(K _e ,O _e ) ≥ 0 for O _e ∈{0,1}. It holds that $f_{2}(K_{e},0)= 89{K_{e}^{3}}+ 954{K_{e}^{2}}+ 318K_{e}\geq 0$ which is always satisfied for any K _e ≥ 0 and $f_{2}(K_{e},1)= 89{K_{e}^{3}}+ 501{K_{e}^{2}}-588K_{e}+ 1\geq 0$ which is always satisfied for any non-negative integer. Hence, also the second constraint is always satisfied for any pair of non-negative integers (K _e ,O _e ). □

For the case d = 3, D L P(s,s ^∗) is the following.

$$\begin{array}{@{}rcl@{}} \begin{array}{ll} minimize\ \gamma\\\vspace{0.1cm} subject\ to\\\vspace{0.1cm} K_e^2(\frac y 2+z)+\frac y 2 K_e\\ -\left( \frac y 2 O_e^2+z K_e O_e+O_e\left( \frac y 2+z\right)\right)+\gamma O_e^2 \geq K_e^2, & \ \ \forall e\in E\\\vspace{0.1cm} \frac y 6 (K_e(K_e + 1)(2K_e + 1)-O_e(O_e + 1)(2O_e + 1))\\ +z(K_e^3-O_e(K_e + 1)^2)+\gamma O_e^3\geq K_e^3, & \ \ \forall e\in E\\\vspace{0.1cm} \frac y 4(K_e^2(K_e + 1)^2-O_e^2(O_e + 1)^2)\\ +z(K_e^4-O_e(K_e + 1)^3)+\gamma O_e^4 \geq K_e^4, & \ \ \forall e\in E\\\vspace{0.1cm} y,z \geq 0 \end{array} \end{array} $$

By analyzing the dual formulation, we obtain the following upper bound on the Po S.

Theorem 6

For any $\mathcal G\in \mathcal UCG$ with cubic latency functions, $\mathsf {PoS}({\mathcal G})\leq 3.322$ .

Proof

The claim follows by setting y = 2.99, z = 0.331 and γ = 3.322.

Let us denote as f _i (K _e ,O _e ) the i th constraint of D L P(s,s ^∗).

For the first constraint, $f_{1}(0,O_{e})= 1827{O_{e}^{2}}-1826O_{e}\geq 0$ is always satisfied for any integer O _e ≥ 0, while the equation f ₁(K _e ,O _e ) = 0 has no solution when K _e ≥ 1 (its discriminant is negative). Hence, the first constraint is always satisfied for any pair of non-negative integers (K _e ,O _e ).

For the second constraint, note that $\frac {\delta f_{2}}{\delta O_{e}}(K_{e},O_{e})=-933{K_{e}^{2}}-1986K_{e}+ 20928{O_{e}^{2}}-8970O_{e}-2488$ implies that, for any fixed value of K _e , f ₂ is increasing in O _e when O _e ≥ 1. Hence, we just need to show that f ₂(K _e ,O _e ) ≥ 0 for O _e ∈{0,1}. It holds that $f_{2}(K_{e},0)= 983{K_{e}^{3}}+ 4485{K_{e}^{2}}+ 1495K_{e}\geq 0$ which is always satisfied for any K _e ≥ 0 and $f_{2}(K_{e},1)= 983{K_{e}^{3}}+ 3492{K_{e}^{2}}-491K_{e}+ 3\geq 0$ which is always satisfied for any non-negative integer. Hence, also the second constraint is always satisfied for any pair of non-negative integers (K _e ,O _e ).

For the third constraint, note that $\frac {\delta f_{3}}{\delta O_{e}}(K_{e},O_{e})=-2(331{K_{e}^{3}}+ 993{K_{e}^{2}}+ 933K_{e}-10298{O_{e}^{3}}+ 4485{O_{e}^{2}}+ 1495O_{e}+ 331)$ implies that, for any fixed value of K _e , f ₃ is increasing in O _e when O _e ≥ 1. Hence, we just need to show that f ₃(K _e ,O _e ) ≥ 0 for O _e ∈{0,1}. It holds that $f_{3}(K_{e},0)= 157{K_{e}^{2}}+ 2990K_{e}+ 1495\geq 0$ which is always satisfied for any K _e ≥ 0 and $f_{3}(K_{e},1)= 157{K_{e}^{4}}+ 2328{K_{e}^{3}}-491{K_{e}^{2}}-1986K_{e}+ 2\geq 0$ which is always satisfied for any non-negative integer. Hence, also the third constraint is always satisfied for any pair of non-negative integers (K _e ,O _e ). □

By extending the instance given by Christodoulou, Koutsoupias and Spirakis in [25] for lower bounding the P o S in the case of affine latency functions, the following lower bounds can be easily achieved.

Theorem 7

For any δ > 0, there exist ${\mathcal G}_{1}\in \mathcal UCG$ with quadratic latency functions and ${\mathcal G}_{2}\in \mathcal UCG$ with cubic latency functions such that $\mathsf {PoS}({\mathcal G}_{1})\geq 2.1859-\delta$ and $\mathsf {PoS}({\mathcal G}_{2})\geq 2.7558-\delta$ .

Proof

Consider a game $\mathcal G\in \mathcal UCG$ with n = n ₁ + n ₂ players divided into two sets P ₁ and P ₂ with |P ₁| = n ₁ and |P ₂| = n ₂. Each player i ∈ P ₁ has two strategies s _i and $s_{i}^{*}$, while all players in P ₂ have the same strategy $\overline {s}$.

There are three types of resources:

• n ₁ resources r _i , i ∈ [n ₁], each with latency function $\ell _{r_{i}}(x)=r x^{d}$, where the parameter r will be specified later. Resource r _i belongs only to $s_{i}^{*}$;

• n ₁(n ₁ − 1) resources $r^{\prime }_{i,j}$, i,j ∈ [n ₁] with i≠j, each with latency function $\ell _{r^{\prime }_{ij}}(x)=r^{\prime } x^{d}$, where the parameter r ^′ will be specified later. Resource $r^{\prime }_{ij}$ belongs only to s _i and to $s_{j}^{*}$;

• one resource r ^″ with latency function $\ell _{r^{\prime \prime }}(x)=x^{d}$. Resource r ^″ belongs to s _i for each i ∈ [n ₁] and to $\overline {s}$;

The cost of each player i ∈ P ₁ adopting strategy s _i when there are exactly k players in P ₁ adopting the strategy played in s (and thus there are n ₁ − k players in P ₁ adopting the strategy played in s ^∗) is c o s t _s (k) = (4n ₁ − 3k − 1)r ^′ + (n ₂ + k)² when d = 2 and it is c o s t _s (k) = (8n ₁ − 7k − 1)r ^′ + (n ₂ + k)³ when d = 3. Similarly, the cost of each player i ∈ P ₁ adopting strategy $s_{i}^{*}$ when there are exactly k players in P ₁ adopting the strategy played in s is $cost_{{s}^{*}}(k)=r+(n_{1}+ 3k-1)r^{\prime }$ when d = 2 and it is $cost_{{ s}^{*}}(k)=r+(n_{1}+ 7k-1)r^{\prime }$ when d = 3.

We now want to select the parameters r and r ^′ so that s is the unique P N E of the game. This is true if, for any k ∈ [n ₁], it holds that $cost_{{s}^{*}}(k-1)>cost_{s}(k).$ Such a condition is always satisfied for the following values of r and r ^′:

• $r=\frac {2{n_{2}^{2}}+(n_{1}+ 1)(n_{1}+ 2n_{2})}{2}+\gamma$ and $r^{\prime }=\frac {n_{1}+ 2n_{2}}{6}$, when d = 2,

• $r=\frac {2{n_{2}^{3}}+(n_{1}+ 1)({n_{1}^{2}}+ 3n_{1} n_{2}+ 3{n_{2}^{2}})}{2}+\gamma$ and $r^{\prime }=\frac {{n_{1}^{2}}+ 3n_{1} n_{2}+ 3{n_{2}^{2}}}{14}$, when d = 3,

where γ is an arbitrarily small positive value.

Next step is to select n ₁ and n ₂ so as to maximize the ratio $\frac {\mathrm {S}\textsc {um}({s})}{\mathrm {S}\textsc {um}({ s}^{*})}=\frac {r^{\prime } n_{1}(n_{1}-1)+(n_{1}+n_{2})^{d + 1}}{r n_{1}+r^{\prime } n_{1}(n_{1}-1)+n_{2}^{d + 1}}$ for d = 2,3. By choosing n ₁ = 1.5595n ₂ when d = 2 and n ₁ = 1.0988n ₂ when d = 3 and letting n ₂ go to infinity, we obtain the claim. □

A recent paper by Christodoulou and Gairing [22] shows that P o S = 2.362 when d = 2 and P o S = 3.322 when d = 3, i.e., our upper bounds are tight, while our lower bounds are not. In particular, while our lower bounds hold for the more restricted notion of dominant strategy equilibria, Christodoulou and Gairing construct instances for which there exists a unique PN E which is not a dominant strategy equilibria. Hence, an interesting research problem is that of determine the price of anarchy/stability² of dominant strategy equilibria.

5.2 Bounding the Approximation Ratio of One-Round Walks

For the case d = 2, D L P(s,s ^∗) is defined as follows.

$$\begin{array}{@{}rcl@{}} \begin{array}{ll} minimize \ \gamma\\\vspace{0.1cm} subject\ to\\\vspace{0.1cm} \displaystyle\sum\limits_{i:e\in s_i}\left( y_i (K_e(i)+ 1)\right)-\sum\limits_{i:e\in s_i^{*}}\left( y_i (K_e(i)+ 1)\right)+\gamma O_e^2 \geq K_e^2, & \ \ \forall e\in E\\\vspace{0.1cm} \displaystyle\sum\limits_{i:e\in s_i}\left( y_i (K_e(i)+ 1)^2\right)-\sum\limits_{i:e\in s_i^{*}}\left( y_i (K_e(i)+ 1)^2\right)+\gamma O_e^3 \geq K_e^3, & \ \ \forall e\in E\\\vspace{0.1cm} y_i\geq 0, & \ \ \forall i\in [n] \end{array} \end{array} $$

From the above formulation, we obtain the following upper bound.

Theorem 8

For any $\mathcal G\in \mathcal UCG$ with quadratic latency functions, $\mathsf {Apx}^{1}_{\emptyset }({\mathcal G})\leq 37.5888$ .

Proof

The worst-case dual constraints occur when each player i using resource e in s ^∗ enters the game after all players using e in s have entered the game yet. The claim follows by choosing y _i = 5.2944 for any i ∈ [n] and γ = 37.5888.

According to these choices, the dual constraints, namely f ₁(K _e ,O _e ) and f ₂(K _e ,O _e ), become

$$2059{K_{e}^{2}}+ 3309K_{e}(1-2O_{e})+ 6O_{e}(7831O_{e}-1103)\geq 0 $$

and

$$956{K_{e}^{3}}+ 3309{K_{e}^{2}}(1-2O_{e})+ 1103K_{e}(1-12O_{e})+ 42986{O_{e}^{3}}-6618O_{e}\geq 0. $$

For the first constraint, it holds that $f_{1}(K_{e},0)= 2059{K_{e}^{2}}+ 3309K_{e}\geq 0$ which is always satisfied for any K _e ≥ 0. Moreover, the equation f ₁(K _e ,O _e ) = 0 has no solution for any O _e ≥ 1 (its discriminant is negative). Hence, the first constraint is always satisfied for any pair of non-negative integers(K _e ,O _e ).

For the second constraint, note that $\frac {\delta f_{2}}{\delta O_{e}}(K_{e},O_{e})=-6(1103{K_{e}^{2}}+ 2206K_{e}-23493{O_{e}^{2}}+ 1103)$ implies that, for any fixed value of K _e , f ₂ is increasing in O _e when O _e ≥ 1. Hence, we just need to show that f ₂(K _e ,O _e ) ≥ 0 for O _e ∈{0,1}. It holds that $f_{2}(K_{e},0)= 956{K_{e}^{3}}+ 3309{K_{e}^{2}}+ 1103K_{e}\geq 0$ which is always satisfied for any K _e ≥ 0 and $f_{2}(K_{e},1)= 956{K_{e}^{3}}-3309{K_{e}^{2}}-12133K_{e}+ 40368\geq 0$ which is always satisfied for any non-negative integer. Hence, the second constraint is always satisfied for any pair of non-negative integers(K _e ,O _e ). □

For the case d = 3, D L P(s,s ^∗) is defined as follows.

$$\begin{array}{@{}rcl@{}} \begin{array}{ll} minimize\ \gamma\\\vspace{0.1cm} subject\ to\\\vspace{0.1cm} \displaystyle\sum\limits_{i:e\in s_i}\left( y_i (K_e(i)+ 1)\right)-\sum\limits_{i:e\in s_i^{*}}\left( y_i (K_e(i)+ 1)\right)+\gamma O_e^2 \geq K_e^2, & \ \ \forall e\in E\\\vspace{0.1cm} \displaystyle\sum\limits_{i:e\in s_i}\left( y_i (K_e(i)+ 1)^2\right)-\sum\limits_{i:e\in s_i^{*}}\left( y_i (K_e(i)+ 1)^2\right)+\gamma O_e^3 \geq K_e^3, & \ \ \forall e\in E\\\vspace{0.1cm} \displaystyle\sum\limits_{i:e\in s_i}\left( y_i (K_e(i)+ 1)^3\right)-\sum\limits_{i:e\in s_i^{*}}\left( y_i (K_e(i)+ 1)^3\right)+\gamma O_e^4 \geq K_e^4, & \ \ \forall e\in E\\\vspace{0.1cm} y_i \geq 0, & \ \ \forall i\in [n] \end{array} \end{array} $$

From the above formulation, we obtain the following upper bound.

Theorem 9

For any $\mathcal G\in \mathcal UCG$ with cubic latency functions, $\mathsf {Apx}^{1}_{\emptyset }({\mathcal G})\leq \frac {17929}{34}\approx 527.323$ .

Proof

The worst-case dual constraints occur when each player i using resource e in s ^∗ enters the game after all players using e in s have entered the game yet. The claim follows by choosing $y_{i}=\frac {369}{34}$ for any i ∈ [n] and $\gamma =\frac {17929}{34}$.

According to these choices, the dual constraints, namely f ₁(K _e ,O _e ), f ₂(K _e ,O _e ) and f ₃(K _e ,O _e ), become

$$301{K_{e}^{2}}+ 3699K_{e}(1-2O_{e})+ 35858{O_{e}^{2}}-738O_{e}\geq 0, $$

$$178{K_{e}^{3}}+ 369{K_{e}^{2}}(1-2O_{e})+ 123K_{e}(1-12O_{e})+ 35858{O_{e}^{3}}-738O_{e}\geq 0 $$

and

$$233{K_{e}^{4}}+ 738{K_{e}^{3}}(1-2O_{e})+ 369{K_{e}^{2}}(1-12O_{e})-4428K_{e}O_{e}+ 71716{O_{e}^{4}}-1476O_{e}\geq 0. $$

For the first constraint, it holds that $f_{1}(K_{e},0)= 301{K_{e}^{2}}+ 369K_{e}\geq 0$ which is always satisfied for any K _e ≥ 0. Moreover, the equation f ₁(K _e ,O _e ) = 0 has no solution for any O _e ≥ 1 (its discriminant is negative). Hence, the first constraint is always satisfied for any pair of non-negative integers(K _e ,O _e ).

For the second constraint, note that $\frac {\delta f_{2}}{\delta O_{e}}(K_{e},O_{e})=-6(123{K_{e}^{2}}+ 246K_{e}-17929{O_{e}^{2}}+ 123)$ implies that, for any fixed value of K _e , f ₂ is increasing in O _e when O _e ≥ 1. Hence, we just need to show that f ₂(K _e ,O _e ) ≥ 0 for O _e ∈{0,1}. It holds that $f_{2}(K_{e},0)= 178{K_{e}^{3}}+ 369{K_{e}^{2}}+ 123K_{e}\geq 0$ which is always satisfied for any K _e ≥ 0 and $f_{2}(K_{e},1)= 178{K_{e}^{3}}-369{K_{e}^{2}}-1353K_{e}+ 35120\geq 0$ which is always satisfied for any non-negative integer. Hence, the second constraint is always satisfied for any pair of non-negative integers(K _e ,O _e ).

For the third constraint, note that $\frac {\delta f_{3}}{\delta O_{e}}(K_{e},O_{e})=-4(369{K_{e}^{3}}+ 1107{K_{e}^{2}}+ 1107K_{e}-71716{O_{e}^{3}}+ 369)$ implies that, for any fixed value of K _e , f ₃ is increasing in O _e when O _e ≥ 1. Hence, we just need to show that f ₃(K _e ,O _e ) ≥ 0 for O _e ∈{0,1}. It holds that $f_{3}(K_{e},0)= 233{K_{e}^{4}}+ 738{K_{e}^{3}}+ 369{K_{e}^{2}}\geq 0$ which is always satisfied for any K _e ≥ 0 and $f_{3}(K_{e},1)= 233{K_{e}^{4}}-738{K_{e}^{3}}-4059{K_{e}^{2}}-4428K_{e}+ 70240\geq 0$ which is always satisfied for any non-negative integer. Hence, the third constraint is always satisfied for any pair of non-negative integers(K _e ,O _e ). □

6 Further Applications: the P o A Under the Social Function Max

In this section, we show how the primal-dual technique can be adapted also to the case in which the social function is the maximum of the players’ payoffs. For the sake of brevity, we consider only the problem of bounding the P o A in unweighted congestion games with affine latency functions. In order to deal with the maximum social function, we assume, without loss of generality, that player n is the one paying the highest cost in s and impose that, in s ^∗, no player pays more than one.

Thus, L P(s,s ^∗) has the following form.

$$\begin{array}{@{}rcl@{}} \begin{array}{ll} maximize\ k\\\vspace{0.1cm} subject\ to\\\vspace{0.1cm} \displaystyle\sum\limits_{e\in s_i}\left( \alpha_e K_e\right)-\sum\limits_{e\in s_i^{*}}\left( \alpha_e (K_e + 1)\right)\leq 0, & \ \ \forall i\in [n]\\\vspace{0.1cm} \displaystyle\sum\limits_{e\in s_i}\left( \alpha_e K_e\right) \leq k, & \ \ \forall i\in [n-1]\\\vspace{0.1cm} \displaystyle\sum\limits_{e\in s_n}\left( \alpha_e K_e\right) = k\\\vspace{0.1cm} \displaystyle\sum\limits_{e\in s_i^{*}}\left( \alpha_e O_e\right)\leq 1, & \ \ \forall i\in [n]\\\vspace{0.1cm} \alpha_e \geq 0, & \ \ \forall e\in E \end{array} \end{array} $$

D L P(s,s ^∗) is as follows.

$$\begin{array}{@{}rcl@{}} \begin{array}{ll} minimize \displaystyle\sum\limits_{i\in [n]} z_i\\\vspace{0.1cm} subject\ to\\\vspace{0.1cm} \displaystyle\sum\limits_{i:e\in s_i}\left( K_e(x_i+y_i)\right)-\sum\limits_{i:e\in s_i^{*}}\left( x_i (K_e + 1)-z_i O_e\right)\geq 0, & \ \ \forall e\in E\\\vspace{0.1cm} \displaystyle\sum\limits_{i\in [n]} y_i\leq -1\\\vspace{0.1cm} x_i,z_i \geq 0, & \ \ \forall i\in [n]\\\vspace{0.1cm} y_i \geq 0, & \ \ \forall i\in [n-1] \end{array} \end{array} $$

We easily reobtain the upper bound on the P o A proven by Christodoulou and Koutsoupias in [23].

Theorem 10

For any $\mathcal G\in \mathcal UCG$ , $\mathsf {PoA}({\mathcal G})=O(\sqrt {n})$ .

Proof

The claim follows by choosing $x_{i}=\frac {1}{\sqrt {n}}$, y _i = 0 and $z_{i}=\frac {2}{\sqrt {n}}$ for each i ∈ [n − 1] and x _n = 1, y _n = − 1 and $z_{n}= 2\sqrt {n}$. Such a choice clearly satisfies the second dual constraint, thus we just need to show that the first dual constraint, that we denote as f(K _e ,O _e ) ≥ 0, is satisfied for any pair of non-negative integers. Note that f(K _e ,O _e ) may assume different forms depending of which of the following four situations occurs:

• $e\notin s_{n}\wedge e\notin s_{n}^{*}$. In this case, $f(K_{e},O_{e})={K_{e}^{2}}-K_{e} O_{e}-O_{e}+ 2{O_{e}^{2}}\geq 0$ is always satisfied for any pair of (K _e ,O _e ) since the equation f(K _e ,O _e ) = 0 has no solution (its discriminant is negative).

• $e\notin s_{n}\wedge e\in s_{n}^{*}$. In this case, $f(K_{e},O_{e})={K_{e}^{2}}-K_{e}(\sqrt {n}+O_{e}-1)+ 2nO_{e}-\sqrt {n}+(O_{e}-1)(2O_{e}-1)$. Note that $\frac {\delta f}{\delta O_{e}}(K_{e},O_{e})= 2n-K_{e}+ 4O_{e}-3$ which is increasing in O _e . Since $e\in s_{n}^{*}$ implies O _e ≥ 1, we just need to show that f(K _e ,O _e ) ≥ 0 for O _e = 1. It holds that $f(K_{e},1)\,=\,{K_{e}^{2}}\,-\,\sqrt {n}K_{e}\,-\,\sqrt {n}+ 2n$ which is always satisfied for any value of K _e (it suffices noting that this inequality coincides with the one considered in the previous case when $O_{e}=\sqrt {n}$).

• $e\in s_{n}\wedge e\notin s_{n}^{*}$. In this case, $f(K_{e},O_{e})={K_{e}^{2}}-K_{e}(O_{e}+ 1)-O_{e}+ 2{O_{e}^{2}}$. The equation f(K _e ,O _e ) = 0 has no solution for O _e ≥ 2 (its discriminant is negative), while it has a unique solution for O _e = 1. Hence, it suffices showing the claim for O _e = 0. It holds that $f(K_{e},O_{e})={K_{e}^{2}}-K_{2}\geq 0$ which is always satisfied for any integer K _e .

• $e\in s_{n}\wedge e\in s_{n}^{*}$. In this case, $f(K_{e},O_{e})={K_{e}^{2}}-K_{e} (\sqrt {n}+O_{e}) + 2nO_{e}-\sqrt {n}+(O_{e}-1)(2O_{e}-1)$. Note that $\frac {\delta f}{\delta O_{e}}(K_{e},O_{e})= 2n-K_{e}+ 4O_{e}-3$ which is increasing in O _e . Since $e\in s_{n}^{*}$ implies O _e ≥ 1, we just need to show that f(K _e ,O _e ) ≥ 0 for O _e = 1. It holds that $f(K_{e},1)\,=\,{K_{e}^{2}}-\!(\sqrt {n}+ 1)K_{e}-\!\sqrt {n}+ 2n$ which is always satisfied for any value of K _e (it suffices noting that this inequality coincides with the one considered in the previous case when $O_{e}=\sqrt {n}$).

The claim follows since ${\sum }_{i = 1}^{n} z_{i}<4\sqrt {n}$. □

7 Conclusions and Open Problems

In this paper, we have introduced a primal-dual method for bounding the quality of self-emerging solutions, namely (approximate) pure Nash equilibria and strategy profiles achieved after a one-round walk starting from the empty state, in weighted congestion games. Our technique has revealed itself to be particularly effective in this domain of application, as we could easily exploit it to reobtain, under a unifying approach, all the results already known in the literature for the case of affine latency functions as well as novel results for the cases of quadratic and cubic latency functions.

Our method differs significantly from the primal-dual method proposed by Nadav and Roughgarden in [37]. Roughly speaking, both methods consist in writing down a linear program aiming at measuring the “maximum distance” between a given strategy profile and the social optimum in a given game, but, while in their approach the strategic choices of the players are treated as variables (whereas the parameters of the game defining the players’ costs/utilities are fixed constant values), in our formulations these choices are reversed. Our key idea is, in fact, that of fixing two “virtual strategy profiles”, representing the self-emerging solution under analysis and the social optimum, which, although fixed, are kept parametric so as to encompass the spectrum of all possible pairs of profiles, while the parameters defining the players’ costs/utilities in the game are now treated as variables in the formulation. The particularly compact succinct representation characterizing weighted congestion games makes them the natural application arena for our technique even in several contexts in which Nadav and Roughgarden’s method cannot be applied since the formulation becomes non-linear.

Several interesting open problems are left open and we discuss in the following some of them which, in our opinion, are worth to be investigated.

The first approach coming into mind is to export our primal-dual method outside the scope of weighted congestion games, by trying to apply it to other succinctly representable games. It would also be nice to understand whether our method can be suitably used to analyze the efficiency of other self-emerging solutions in congestion games. For instance, it is known that the P o A of Strong Nash equilibria in symmetric unweighted congestion games with affine latency functions is strictly smaller than 5/2 [21] (which corresponds to the P o A of pure Nash equilibria), but no significant bounds have been given up to date.

Moreover, is it possible to strengthen some of the results already known in the literature for the case of unweighted congestion games with linear latencies? For instance, is it possible to narrow the gap between upper and lower bounds on the P o S _𝜖 ? (To this aim, we believe that adding suitable constraints in the primal formulation should provide better upper bounds.)

Or is it possible to narrow the gap between upper and lower bounds on the $\mathsf {Apx}^{1}_{\emptyset }$ when all the players’ strategies are made of a single resource? (In such a case, the best-known lower bound is 4 [20], while no improvements on the $2+\sqrt {5}\approx 4.24$ upper bound are known for this special case.)

Appendix: How to Compute Dual Variables: an Example

In this section, we show how to compute the dual variables exploited within the proof of Theorem 1.

In order to find the best possible upper bound on the P o A _𝜖 , we need to find the variables γ and y _i , for each i ∈ [n], such that the dual constraint

$$\sum\limits_{i:e\in s_{i}}\left( y_{i} K_{e}\right)-(1+\epsilon)\sum\limits_{i:e\in s_{i}^{*}}\left( y_{i} (K_{e}+w_{i})\right)+\gamma {O_{e}^{2}} \geq {K_{e}^{2}} $$

is satisfied for each pair of non-negative integers (K _e ,O _e ).

Since in our games no player has a special role which may distinguish her from the others, we can assume, without loss of generality, that all players are indistinguishable, so that we can set y _i = y for each i ∈ [n]. With this simplification, the dual constraint becomes

$$y{K_{e}^{2}}-(1+\epsilon)yO_{e}(K_{e}+ 1)+\gamma {O_{e}^{2}} \geq {K_{e}^{2}}, $$

by which we obtain

$$ \gamma\geq\frac{{K_{e}^{2}}(1-y)+(1+\epsilon)yO_{e}(K_{e}+ 1)}{{O_{e}^{2}}}, $$

(8)

for O _e ≥ 1 and y ≥ 1 for O _e = 0. Moreover, it is also easy to see that, for K _e >> O _e , the dual constraint is satisfied only if y > 1. Thus, from now on, we can assume, without loss of generality, that y > 1, O _e ≥ 1 and focus on the satisfiability of (8).

Let us denote with f(K _e ,O _e ,y) the right-hand side of (8). Our task is to find the value of y minimizing f(K _e ,O _e ,y) for each pair of non-negative integers (K _e ,O _e ) with O _e ≥ 1. We have $\frac {\delta f}{\delta K_{e}}(K_{e},O_{e},y)=\frac {y((1+\epsilon )O_{e}-2K_{e})+ 2K_{e}}{{O_{e}^{2}}}$ which, being a linear function in K _e , is maximized for $K_{e}=\frac {(1+\epsilon )yO_{e}}{2(y-1)}$. By using $K_{e}=\frac {(1+\epsilon )yO_{e}}{2(y-1)}$ in f(K _e ,O _e ,y), we obtain a function which is always decreasing in O _e ; hence, we can claim that the maximum value of f(K _e ,O _e ,y) is attained for $K_{e}=\frac {(1+\epsilon )y}{2(y-1)}$ and O _e = 1.

However, the resulting lower bound on γ might not be tight, as K _e might not be an integer. In order to remain within the realm of the integers, we can assume that the maximum value of f(K _e ,O _e ,y) is attained for O _e = 1 and K _e such that either $K_{e}=\left \lfloor \frac {(1+\epsilon )y}{2(y-1)}\right \rfloor$ or $K_{e}=\left \lceil \frac {(1+\epsilon )y}{2(y-1)}\right \rceil$. By setting $\left \lfloor \frac {(1+\epsilon )y}{2(y-1)}\right \rfloor =z$, this is equivalent to saying that the maximum value of f(K _e ,O _e ,y) is attained for O _e = 1 and K _e such that either K _e = z or K _e = z + 1. By imposing the condition f(z, 1,y) = f(z + 1, 1,y), we obtain $y=\frac {2z + 1}{2z-\epsilon }$ and $\gamma =f(z,1,\frac {2z + 1}{2z-\epsilon })=(1+\epsilon )\frac {z^{2}+ 3z + 1}{2z-\epsilon }$.