1 Introduction

Atomic congestion games are one of the most well-studied topics in algorithmic game theory [2, 3]. In their most general form, players have weights and compete over a common set of resources; the cost of each resource is a function of the total weight of the players that end up using it. As a result, they can model a wide range of interesting applications including, e.g., network routing [4] and load balancing [5], but also even cost-sharing games (via the use of decreasing cost functions) like fair network design [6].

An important special case is that of unweighted congestion games, where the costs depend only on the number of players that use each edge. In a seminal paper, Rosenthal [7] proved that unweighted congestion games always have (pure Nash) equilibria. A key tool in his derivation was the novel use of a potential function, which is able to capture the different players’ deviations in a very elegant and concise way. Then, the desired equilibrium is derived as the minimizer of that function (over all feasible outcomes of the game).

This technique can also be viewed as an equilibrium refinement, and has been a very influential idea in game theory [8]. It allows us not only to establish the existence of equilibria, but in many cases, this special potential-minimizer equilibrium has additional desired properties.

Of particular importance to us in this paper, is that it has been the de facto method for proving Price of Stability (PoS) bounds in congestion games (see, e.g., [3, Ch. 18, 19]). The PoS notion [9, 10] captures the minimum approximation ratio of the social cost, among all equilibria, to the socially optimum outcome of the game (that might not be an equilibrium). In other words, the PoS is the best-case counterpart of the notorious Price of Anarchy (PoA) notion introduced by Koutsoupias and Papadimitriou [11, 12]

Unfortunately, though, it is a well-known fact that general weighted congestion games do not always have equilibria and thus, do not admit a potential function.

To alleviate this, a line of work has focused on designing approximate potential functions (see, e.g., [13,14,15,16,17]): the minimizer of such functions is guaranteed to be an approximate equilibrium (as opposed to an exact one that is given by Rosenthal’s potential in the unweighted case), while at the same time it can achieve a good approximation ratio to the optimal social cost (providing, thus, an upper bound for the approximate-equilibrium extension of the PoS notion). However, most of those prior works use different approximate potentials, designed specially for the particular cost-function model that each one studies.

Our goal in this paper is to provide a simple, high-level framework whose interface is agnostic to the underlying potential function technicalities and which can readily be instantiated for all resource costs at hand to derive meaningful bounds.

1.1 Related Work

Following the seminal work of [7], a long line of results has been devoted to the (non)existence of equilibria in weighted congestion games. [18,19,20] demonstrated that equilibria might not exist even in very simple classes of games, including network congestion games with quadratic cost functions and games where player weights are either 1 or 2. On the other hand, [20,21,22] showed that equilibria do exist in games with affine or exponential cost functions; [23, 24] proved the same for singleton games (where players can only occupy single resources). Dunkel and Schulz [25] were able to extend the nonexistence instance of Fotakis et al. [20] to a hardness gadget, in order to show that, deciding whether a congestion game with step cost functions has an equilibrium, is a (strongly) NP-complete problem.

Regarding the existence of approximate equilibria in general weighted congestion games, [26] showed that games with n players always have n-approximate equilibria, and this guarantee is tight (up to logarithmic factors); they also proved that the corresponding decision problem, i.e., of the existence of \(\tilde{\varTheta }(n)\)-approximate equilibria, is NP-complete.

A lot of work has been focused on the important special case of polynomial congestions games, parameterized by the maximum degree d of the cost functions. Although, due to [20] we already know that exact equilibria do not in general exist in such games, Caragiannis et al. [27] were the first to show that \(\alpha \)-approximate equilibria do exist for \(\alpha =d!\); this factor was later improved to \(\alpha =d+1\) [14, 16] and \(\alpha =d\) [17]. As a matter of fact, Caragiannis and Fanelli [17] provide an even more comprehensive result that, for any choice of a parameter \(\delta \in [0,1]\), simultaneously establishes the existence of \((d+\delta )\)-approximate equilibria and gives an upper bound of \(\frac{d+1}{\delta +1}\) on their PoS. They achieve this by designing an appropriate approximate potential function, tailored to polynomial costs. On the nonexistence front, [14] first gave instances of very simple, two-player polynomial congestion games that do not have \(\alpha \)-approximate equilibria, for \(\alpha \approx 1.153\). This was recently improved to \(\alpha =\varOmega \left( \frac{\sqrt{d}}{\log d}\right) \) by Christodoulou et al. [26], who also established NP-hardness of the corresponding existence decision problem.

The work of Hansknecht et al. [14] is very relevant for our approach in this paper, since they also propose a “generic” approximate potential function that can, in principle, be applied to general cost functions. They instantiate it for polynomial costs to derive their aforementioned existence of \((d+1)\)-approximate equilibria. Additionally, they also state a result about the existence of \(\frac{3}{2}\)-approximate equilibria in games with nondecreasing concave costs; however, this proof in their paper is not complete. Furthermore, [14] focuses just on the existence of approximate equilibria, and thus it does not provide any PoS bounds.

Another well-studied class of congestion games is that of fair cost sharing, where each resource has a constant initial cost which is split equally among the players that use it. Thus, such games have decreasing cost functions. Finding the PoS for the special, undirected network version of such games is a notorious open problem in the field (see, e.g., [9, 28,29,30,31]). Very relevant for us is the work of Chen and Roughgarden [13] who showed that general weighted fair cost sharing games always have \(\alpha \)-approximate equilibria whose PoS is at most \(O\left( \frac{\log W}{\alpha }\right) \), for any choice of parameter \(\alpha =\varOmega (\log w_{\max })\), where \(w_{\max }\) is the maximum weight of any player and W the maximum possible load in any resource. They achieve this by designing a special approximate potential function, tailored to the specific form of the cost functions.

1.2 Our Results and Techniques

We propose a new approximate potential function (see (9)) for weighted congestion games with general cost functions. In particular, our potential can be instantiated beyond the standard model of polynomial cost functions and the common assumption of non-decreasing monotonicity. However, this potential is only used in the analysis part of our paper: we hide away its specific form by hard-coding it within the proof of a unifying tool (Theorem 2). Then, this tool can be used in a black-box way to readily derive both existence of approximate equilibria, and bounds on their PoS. This proof makes also use of a general, high-level lemma that can capture the essence of the potential method as a technique for deriving existence and PoS bounds for approximate equilibria (Lemma 1); we believe this might be of independent interest, since in future work it could be used for alternative potential functions, beyond our choice of (9) in this paper.

Our framework effectively works in two steps. Given a congestion game, first one has to determine how good its cost functions are with respect to two simple, analytic properties (Definition 2). Then, the resulting “goodness” parameters can be plugged straight into our master theorem (Theorem 2) to deduce the existence of an \((\alpha ,\beta )\)-equilibrium; that is, an \(\alpha \)-approximate (pure Nash) equilibrium whose social cost is at most a factor of \(\beta \) away from the optimum.

We demonstrate the power of our tool by applying it to recover and improve prior bounds on the existence of \((\alpha ,\beta )\)-equilibria for well-studied classes of congestion games, as well as to derive novel results. The simplicity and the algebraic nature of our tool allows us to produce fine-grained bounds in the form of a parametric trade-off curve that describes the relation between the \(\alpha \) and \(\beta \) parameters of the \((\alpha ,\beta )\)-equilibrium; in other words, all our results give a continuum of existence bounds. Our bounds are summarized in Table 1.

Table 1 Our main results on the existence of \((\alpha ,\beta )\)-equilibria for different cost models. For polynomials of degree d we recover the result of [17]
Full size table

More specifically, first (Theorem 5) we rederive the recent bounds of [17] for polynomial congestion games, in a more “clean”, high-level way. Then (Theorem 10), we improve the \(\alpha ,\beta \) parameters on the \((\alpha ,\beta )\)-equilibrium existence results of [13] for fair cost-sharing games (a more detailed comparison can be seen in Fig. 1). Furthermore, we derive new results for (nondecreasing) concave costs: we show that \((\lambda ,\frac{\lambda }{\lambda -1})\)-equilibria always exist, for all \(\lambda \in [\frac{3}{2},2]\) (Theorem 7). The special corner case of a \((\frac{3}{2},3)\)-equilibrium is compatible, thus, with the \(\frac{3}{2}\)-approximate equilibrium existence stated in [14].

Fig. 1
figure 1

Fair cost sharing games. Top: guarantee on the existence of \(\alpha \)-approximate equilibria, as a function of \(w_{\max }\), given by Theorem 10 (setting \(\lambda =1\)). Bottom: trade-off curve for the existence of \((\alpha ,\beta )\)-equilibria, given by Theorem 10; here we choose \(w_{\max }=3\), \(W=50\). For comparison, the previously best bounds [13, Theorem 5.1 and Lemma 5.3] are plotted in red, while our results are in blue. The fact that the blue line of the right plot starts earlier is a direct consequence of our results providing a strictly better (smaller) absolute existence guarantee \(\alpha \) (see top plot)

Full size image

Another interesting characteristic of our tool is its modularity: it can readily combine different cost functions to give bounds for more complex congestion games (see Definition 3). For example, we prove that games with cost functions that are conical combinations of d-degree polynomials and concave costs, always have \(\left( \lambda ,1+\frac{d+1}{\lambda }\right) \)-equilibria, where \(\lambda \) ranges in \([d,d+1]\) (Theorem 11).

Finally, an added advantage of our black-box method is that it also results in arguably simpler and more streamlined proofs for the existence and PoS bounds.

Before concluding the overview of our results, we want to elaborate a bit more on the comparison to the potential approach of Hansknecht et al. [14]. Although [14] does not deal with PoS bounds, as far as existence of approximate equilibria is concerned, their paper is rather similar in principle to ours. They propose a general potential function which is based on a discrete interpretation of the cost function’s integral, which corresponds to the first component of our potential in (9). We take a different approach by using directly the actual integral, and also adding an extra term that corresponds to a weighted average of the costs of the players’ weights. In that way, we avoid a lot of the intricate technicalities that are involved with the discrete arguments (e.g., orderings of the weights) in [14], making the application of our potential (via our high-level tool of Theorem 2) more “tractable” for a wider range of cost functions.

2 Model and Notation

We use \(\mathbb { R}_+\) to denote the set of nonnegative real numbers.

In a (weighted) congestion game \(\mathcal G\) there are finite, nonempty sets of players N and resources E. Let \(n=\left| N \right| \). Each player \(i\in N\) has a weight \(w_i\in \mathbb { R}_{+}\) and a strategy set \(S_i\subseteq 2^E\). We use \(w_{\min }=\min _{i\in N} w_i\) and \(w_{\max }=\max _{i\in N} w_i\) for the minimum and maximum player weights, respectively, and for a subset of players \(I\subseteq N\), we use \(w_I=\sum _{i\in I} w_i\) to denote the sum of their weights. For the special case of \(w_{\min }=w_{\max }=1\), that is, if all weights are 1, we say that \(\mathcal G\) is unweighted.

Associated with each resource \(e\in E\) is a cost function \(c_e: \mathbb { R}_{+}\longrightarrow \mathbb { R}_{+}\). In general, we will make no extra assumptions on the cost functions. However, important special cases, that we will also study as applications of the main tool of our paper, include polynomial congestion games of degree d, for \(d\ge 1\) integer, and fair cost sharing games. In the former, the cost functions are polynomials with nonnegative coefficients and degree at most d; in the latter, cost functions are (decreasing) of the form \(c_e(x)=\frac{a_e}{x}\) where \(a_e\) is a positive real.

A (pure) strategy profile (or outcome) is a choice of strategies \({s}= (s_1, s_2,..., s_n)\in {S}={S}_1\times \cdots \times {S}_n\). We use the standard game-theoretic notation \({s}_{-i}=(s_1,\ldots , s_{i-1},s_{i+1},\ldots s_n)\), \({S}_{-i}={S}_1\times \cdots \times S_{i-1} \times S_{i+1} \times \cdots \times S_n\). In that way, for example, we can denote \({s}=(s_i,{s}_{-i})\). Given a profile \({s}\in {S}\), we define the load \(x_e({s})\) of resource e as the total weight of players that use resource e at outcome \({s}\), i.e., \(x_e({s})=w_{N_e({s})}= \sum _{i\in N: e\in s_i} w_i\), where \(N_e({s})\) is the set of players using e. We will use \(W=\sum _{i\in N} w_i\) to denote the maximum possible load of any resource. The cost of player i is defined by \(C_i({s})=\sum _{e\in s_i} c_e(x_e({s}))\). The social cost of a strategy profile \({s}\) is the weighted sum of the players’ costs

$$\begin{aligned} C({s})=\sum _{i\in N}w_i \cdot C_i({s}) = \sum _{e\in E} x_e({s}) \cdot c_e(x_e({s})). \end{aligned}$$

We use \(\textrm{OPT}(\mathcal G)=\min _{{s}\in S} C({s})\) to denote the optimum social cost over all outcomes.

An outcome \({s}\) is an \(\alpha \)-approximate (pure Nash) equilibrium, for \(\alpha \ge 1\), if

$$\begin{aligned} C_i({s})\le \alpha \cdot C_i(s'_i,{s}_{-i}) \qquad \text {for all}\;\; i\in N,\; s'_i\in S_i \end{aligned}$$
(1)

That is, no player can unilaterally deviate from \({s}\) and improve her cost by more than a factor of \(\alpha \). Notice that for the special case of \(\alpha =1\) we get the definition of the standard, exact pure Nash equilibrium. We denote the set of all \(\alpha \)-equilibria of \(\mathcal G\) by \(\textrm{NE}_\alpha (\mathcal G)\) Then, the \(\alpha \)-approximate Price of Stability (\(\alpha \)-PoS) of \(\mathcal G\) is the social cost of the best-case Nash equilibrium over the optimum social cost:

$$\begin{aligned} \textrm{PoS}_\alpha (\mathcal G) =\min _{{s}\in \textrm{NE}_\alpha (\mathcal G)}\frac{C({s})}{\textrm{OPT}(\mathcal G)}. \end{aligned}$$
(2)

For \(\alpha =1\) we get the standard definition of the Price of Stability (PoS) for exact equilibria [9].

We combine the notions of an approximate equilibrium with approximating the optimum social cost in the following definition:

Definition 1

(\((\alpha ,\beta )\)-equilibrium) Fix a congestion game \(\mathcal G\). A strategy profile \({s}\) is an \((\alpha ,\beta )\)-equilibrium if it is an \(\alpha \)-approximate equilibrium of \(\mathcal G\) (see (1)) and its social cost is at most \(\beta \) times the optimal cost of \(\mathcal G\), i.e., \(C({s}) \le \beta \cdot \textrm{OPT}(\mathcal G)\).

Notice that if a game has an \((\alpha ,\beta )\)-equilibrium then, due to (2), its \(\alpha \)-PoS is at most \(\beta \).

2.1 Equivalent Cost Functions

It is not difficult to see that, in any weighted congestion game, the cost functions of each resource are actually evaluated on finitely many points: although our model assumes \(c_e\) to be defined over the entire \(\mathbb { R}_{+}\), its values outside the domain \(\{ x_e({s})\; \left| \; {s}\in {S} \right. \}\) are irrelevant. In particular, this domain is included within the set of different sums of weights

$$\mathcal {W}=\left\{ \left. \sum _{i\in N}y_i\cdot w_i\;\right| \; y_i\in \{ 0,1\},\;i\in N\right\} .$$

This means that one only needs to define costs on at most \(\left| \mathcal {W} \right| \le 2^n\) different values: any two games whose costs coincide on \(\mathcal W\) are equivalent.

However, it is still convenient to treat our costs as functions over \(\mathbb { R}_{+}\). First, because this allows for simple and succinct representations. But of particular importance to us, is also the fact that our main tool (Theorem 2) can be applied to all integrable cost functions (so that  Definition 2 can be utilized). From the above discussion, it should be obvious that any congestion game has (infinitely) many equivalent representations, that is, different extensions from \(\mathcal W\) to \(\mathbb { R}_{+}\). Such an extension can always be done in a way that \(c_e\) is an integrable function (since \(\mathcal W\) is finite).

It is interesting to point out here that different representations can potentially give different existence and PoS bounds via our tool. Although we do not deal with this feature for most of the paper, it is important for our fair cost sharing results (Section 4.3); since function \(x\mapsto 1/x\) is not integrable over the interval \([0,w_{\min })\) (and as a matter of fact, not even defined on \(x=0\)) we have the freedom, according to the discussion above, to redefine it in any way we want on \([0,w_{\min })\), so that it is a well-defined, integrable function over \(\mathbb { R}_{+}\).

3 The Main Tool

In this section we present our framework for establishing existence of \((\alpha ,\beta )\)-equilibria in weighted congestion games with general cost functions. We begin with the following lemma, that tries to distil and abstract the potential method technique in congestion games. Specialized or restricted forms of it have essentially been used, even if not explicitly stated, in multiple works in the past (see, e.g., [13, 14, 17]). It can be seen as a more fine-grained version of [16, Lemma 4.1], although some extra care is needed to adapt it to the more abstract setting of our paper and utilize its full power.

Lemma 1

(Potential Method) Fix a congestion game. Assume that, for each resource e, there exist positive reals \(\alpha _{1,e}, \alpha _{2,e}, \beta _{1,e}, \beta _{2,e}\), and a function \(\phi _e: 2^N\longrightarrow \mathbb { R}\) such that \(\phi _e(\emptyset )=0\) and

$$\begin{aligned} \alpha _{1,e} \le \frac{\phi _e(I\cup \{ i\})-\phi _e(I)}{w_i\cdot c_e(w_I+w_i)} \le \alpha _{2,e} \qquad \text {for all}\;\; i\in N,\; I\subseteq N\setminus \{ i\}; \end{aligned}$$
(3)
$$\begin{aligned} \beta _{1,e}\le \frac{\phi _e(I)}{w_I\cdot c_e(w_I)} \le \beta _{2,e} \qquad \text {for all}\;\; \emptyset \ne I \subseteq N. \end{aligned}$$
(4)

Then the game has an \((\alpha ,\beta )\)-equilibrium with

$$\begin{aligned} \alpha = \max _{e\in E}\frac{\alpha _{2,e}}{\alpha _{1,e}} \quad \text {and}\quad \beta = \frac{\max _{e\in E} \beta _{2,e}/\alpha _{1,e}}{\min _{e\in E} \beta _{1,e}/\alpha _{1,e}}. \end{aligned}$$

Proof

Define function \( \varPhi ({s})=\sum _{e\in E}\frac{1}{\alpha _{1,e}}\phi _e(N_e({s}))\) over all feasible outcomes. We will show that \(\varPhi \) can serve as a desired approximate potential function for our game; that is, for any profiles \({s},{s}'\) and any player i, it satisfies:

$$\begin{aligned} \varPhi ({s}) \le \varPhi (s_i',{s}_{-i})&\quad \Longrightarrow \quad C_i({s}) \le \alpha \cdot C_i(s_i',{s}_{-i}) \end{aligned}$$
(5)
$$\begin{aligned} \varPhi ({s}) \le \varPhi ({s}')&\quad \Longrightarrow \quad C({s}) \le \beta \cdot C({s}'). \end{aligned}$$
(6)

This would be enough to establish our lemma: any (global) minimizer of \(\varPhi \) is an \(\alpha \)-approximate equilibrium, due to (5), and at the same time, due to (6), its social cost is within a factor of \(\beta \) from the social cost of any other profile (and, thus, from the optimal one). Notice also, that such a minimizer always exists, since the set \({S}\) of feasible outcomes is finite.

For (5) first, denote for simplicity \(N_e=N_e({s})\), \(x_e=x_e({s})\) and \(N_e'=N_e(s_i',{s}_{-i})\), \(x_e'=x_e(s_i',{s}_{-i})\) for all facilities e. Then, we have

$$\begin{aligned} \varPhi (s_i',{s}_{-i})-\varPhi ({s})&= \sum _{e\in E} \frac{1}{\alpha _{1,e}}\left[ \phi _e(N_e')-\phi _e(N_e)\right] \\&= \sum _{e\in s_i'\setminus s_i}\frac{1}{\alpha _{1,e}}\left[ \phi _e(N_e\cup \{ i\})-\phi _e(N_e)\right] \\&\qquad + \sum _{e\in s_i\setminus s_i'}\frac{1}{\alpha _{1,e}}\left[ \phi _e(N_e\setminus \{ i\})-\phi _e(N_e)\right] \\&\le \sum _{e\in s_i'\setminus s_i}\frac{\alpha _{2,e}}{\alpha _{1,e}} w_i c_e(x_e+w_i) - \sum _{e\in s_i\setminus s_i'} w_i c_e(x_e)\\&\le w_i\left[ \alpha \sum _{e\in s_i'\setminus s_i} c_e(x_e+w_i) - \sum _{e\in s_i\setminus s_i'} c_e(x_e)\right] \\&\le w_i\left[ \alpha \left( \sum _{e\in s_i'\setminus s_i} c_e(x_e+w_i) +\sum _{e\in s_i'\cap s_i} c_e(x_e)\right) \right. \\&\qquad - \left. \left( \sum _{e\in s_i\setminus s_i'} c_e(x_e) +\sum _{e\in s_i'\cap s_i} c_e(x_e)\right) \right] \\&= w_i\left[ \alpha C_i(s_i',{s}_{-i}) - C_i({s}) \right] . \end{aligned}$$

The first inequality holds due to (3); the second due to the definition of \(\alpha \); and the third one because \(\alpha \ge 1\). The fact that the cost functions are nonnegative is a critical component in all of them as well. The chain of inequalities above demonstrate that, if \(\varPhi (s_i',{s}_{-i})-\varPhi ({s})\) is nonnegative then \(\alpha C_i(s_i',{s}_{-i}) - C_i({s})\) is nonnegative, thus proving (5).

For (6) next, denote \(N_e=N_e({s})\), \(x_e=x_e({s})\) and \(N_e'=N_e({s}')\), \(x_e'=x_e({s}')\). Then, we have:

$$\begin{aligned} \varPhi ({s}')-\varPhi ({s})&= \sum _{e\in E}\frac{1}{\alpha _{1,e}}\phi _e(N_e')-\sum _{e\in E}\frac{1}{\alpha _{1,e}}\phi _e(N_e)\\&\le \sum _{e\in E}\frac{\beta _{2,e}}{\alpha _{1,e}}x_e'c_e(x_e') -\sum _{e\in E}\frac{\beta _{1,e}}{\alpha _{1,e}}x_ec_e(x_e)\\&\le \max _{e\in E}\frac{\beta _{2,e}}{\alpha _{1,e}}\cdot \sum _{e\in E}x_e'c_e(x_e') -\min _{e\in E}\frac{\beta _{1,e}}{\alpha _{1,e}}\cdot \sum _{e\in E}x_ec_e(x_e)\\&= \max _{e\in E}\frac{\beta _{2,e}}{\alpha _{1,e}}\cdot C({s}') -\min _{e\in E}\frac{\beta _{1,e}}{\alpha _{1,e}}\cdot C({s})\\&=\min _{e\in E}(\beta _{1,e}/\alpha _{1,e}) \cdot \left[ \beta C({s}') - C({s}) \right] , \end{aligned}$$

where for the first inequality we deployed (4). The chain of inequalities above demonstrate that if \(\varPhi ({s}')-\varPhi ({s})\) is nonnegative then \(\beta C({s}') - C({s})\) is nonnegative as well, this establishing (6).

We continue with defining a critical notion that will act as the medium to utilize our main black-box tool in Theorem 2. It involves a set of parameters, that determine how “well” a given cost function behaves with respect to two specific, simple analytic properties (namely (7) and (8)). These properties can be interpreted as bounds on the average of the cost function over continuous intervals.

Definition 2

(Good Cost Functions) Fix a congestion game \(\mathcal G\). A function \(c:\mathbb { R}_+\longrightarrow \mathbb { R}_+\) will be called \((\alpha _1,\alpha _2,\beta _1,\beta _2)\)-good (with respect to \(\mathcal G\)), for \(\alpha _1,\alpha _2,\beta _1,\beta _2>0\), if there exists a nonnegative constant \(\xi \) such that, for all \(x\in \{ 0\}\cup [w_{\min },W]\), \(w\in [w_{\min },w_{\max }]\):

$$\begin{aligned} \alpha _1\cdot c(x+w) - \xi \cdot c(w) \;\le \; \frac{1}{w}\int _x^{x+w} c(t)\,dt \;\le \; \alpha _2 \cdot c(x+w) - \xi \cdot c(w) \end{aligned}$$
(7)

and for all \(x\in [w_{\min },W]\):

$$\begin{aligned} \beta _1\cdot c(x) - \xi \cdot c_{\min }(x)\;\le \; \frac{1}{x}\int _0^{x} c(t)\,dt\;\le \; \beta _2\cdot c(x) - \xi \cdot c_{\max }(x), \end{aligned}$$
(8)

where \(c_{\min }(x)=\min _{y\in [w_{\min },x]}c(y)\), \(c_{\max }(x)=\max _{y\in [w_{\min },x]}c(y)\).

Definition 3

(Good Games) A congestion game will be called \(\{ (\alpha _{1,j},\alpha _{2,j},\beta _{1,j},\)\(\beta _{2,j})\}_{j\in J}\)-good if any cost function is a conical combination of such good functions. Formally, for any \(e\in E\) there exists a nonempty \(J_e\subseteq J\) and nonnegative constants \(\{ \lambda _{e,j}\}_{j\in J_e}\), such that

$$\begin{aligned} c_e(t)= \sum _{j\in J_e} \lambda _{e,j} c_j(t) \end{aligned}$$

where, for all \(j\in J\), \(c_j\) is a \((\alpha _{1,j},\alpha _{2,j},\beta _{1,j},\beta _{2,j})\)-good function (see Definition 2).

Remark 1

Notice that an important special case of Definition 3 is when \(J=E\), \(J_e=\{e\}\), and \(\lambda _{e,e}=1\), meaning that the actual cost functions of the game are good themselves. As a matter of fact, it is not hard to see that any good game \(\mathcal G\) can be transformed to a strategically equivalent one \(\mathcal G'\) that has that property. First, replace each resource e of \(\mathcal G\) with a gadget of “parallel” resources \(\{ (e,j)\;\vert \; j\in J_e\}\), each having a cost function of \(c_{(e,j)}(t)=\lambda _{e,j}c_j(t)\); this results in a strategically equivalent game \(\mathcal G'\) with resources \(E'=\{ (e,j)\;\vert \; e\in E,\; j\in J_e\}\). Next, just observe that Definition 2 is invariant under nonnegative scalar multiplication: since functions \(c_j\) satisfy conditions (7) and (8), so do functions \(\lambda _{e,j}\cdot c_j\) that are exactly the cost functions of the new game \(\mathcal G'\).

Remark 2

(Increasing Good Functions) If a cost function is nondecreasing, then (8) can be replaced by the (stronger, sufficient) condition:

$$\begin{aligned} \beta _1 c(x) \;\le \; \frac{1}{x}\int _{0}^x c(t)\,dt \;\le \; (\beta _2-\xi ) c(x), \end{aligned}$$
(8′)

since \(0 \le c(y) \le c(x)\) for any \(y\in [w_{\min },x]\).

Now we are ready to state our main tool. This is essentially the interface of our entire framework: under the hood it uses a specific potential function form (see (9)), but its statement involves only the goodness parameters of the cost functions, as defined above. In that way, one can readily derive meaningful bounds about the existence of \((\alpha ,\beta )\)-equilibria in a black-box way, just by studying the simple analytic properties given in (2) and the plugging the parameters in the theorem below:

Theorem 2

Any \(\left\{ (\alpha _{1,j},\alpha _{2,j},\beta _{1,j},\beta _{2,j})\right\} _{j\in J}\)-good congestion game has an \((\alpha ,\beta )\)-equilibrium with

$$\begin{aligned} \alpha = \max _{j\in J}\frac{\alpha _{2,j}}{\alpha _{1,j}} \qquad \text {and}\qquad \beta = \frac{\max _{j\in J} \beta _{2,j}/\alpha _{1,j}}{\min _{j\in J} \beta _{1,j}/\alpha _{1,j}}. \end{aligned}$$

Proof

First notice that, by Remark 1, it is without loss to assume that \(J=E\) and that any cost function \(c_e\), \(e\in E\), is \((\alpha _{1,e},\alpha _{2,e},\beta _{1,e},\beta _{2,e})\)-good. Denote by \(\xi _e\) (a choice of) the parameter \(\xi \) for which resource e satisfies Definition 2.

We will then show that functions

$$\begin{aligned} \phi _e(I) = \int _{0}^{w_I} c_e(t)\, dt + \xi _e \sum _{i\in I} w_i c_e(w_i) \end{aligned}$$
(9)

satisfy the conditions of Lemma 1,

Fix some resource \(e\in E\), a player i and a subset \(I\subseteq N\setminus \{ i\}\) of remaining players. For simplicity, from now on we drop the e subscripts and also denote \(w=w_i\) and \(x=w_I\). Then,

$$\begin{aligned} \phi (I\cup \{ i\}) - \phi (I)&= \int _{0}^{x+w} c_e(t)\, dt - \int _{0}^{x} c_e(t)\, dt\\&\qquad + \xi _e\left( \sum _{j\in I} w_j c_e(w_j) - \sum _{j\in I\cup \{ i\}} w_j c_e(w_j) \right) \\&=\int _{x}^{x+w} c(t)\, dt + \xi w c(w). \end{aligned}$$

So, by deploying (7), it is not difficult to see that

$$\begin{aligned} \alpha _1 c(x+w)\le \frac{1}{w}\left[ \phi (I\cup \{ i\}) - \phi (I)\right] \le \alpha _2 c(x+w), \end{aligned}$$

and thus condition (3) of Lemma 1 is indeed satisfied.

Next, observe that since \(w_j\in [w_{\min },w_{\max }]\) for all \(j\in I\), and \(x=\sum _{j\in I} w_j\), we have the bounds

$$\begin{aligned} c_{\min }(x)\le \min _{j\in I} c(w_j)\le \frac{1}{x}\sum _{j\in I}w_jc(w_j) \le \max _{j\in I} c(w_j)\le c_{\max }(x), \end{aligned}$$
(10)

where the first and the last inequalities hold due to the fact that \(\{ w_j\; \left| \; j\in I \right. \}\subseteq [w_{\min },x]\).

Assuming \(I\ne \emptyset \), we have that \(x\in [w_{\min },W]\) and so we can use (10) and (8) to bound \(\frac{1}{x}\phi (I)\) from below and above by:

$$\begin{aligned} \beta _1 c(x) \le \frac{1}{x}\phi (I)= \frac{1}{x}\int _{0}^x c(t)\, dt+\xi \frac{1}{x}\sum _{j\in I}w_jc(w_j) \le \beta _2 c(x). \end{aligned}$$

Thus, condition (4) of Lemma 1 is also satisfied. \(\square \)

4 Applications

In this section we present several applications of our black-box Theorem 2, that demonstrate both its power and simplicity. In accordance to the nature of that tool, they all share a common structure: first, we prove lemmas describing the right goodness parameters (according to Definition 2) for each special cost function of interest (see Lemma 3, 4, 6, and 8); then, we plug them in Theorem 2 to derive our bounds (see Theorem 5, 7, and 10).

4.1 Polynomial Costs

We start with polynomial cost functions, arguably the most studied setting in congestion games. We recover the result from Caragiannis and Fanelli [17] that, for polynomials of degree at most d with nonnegative coefficients, there exist \((d+\delta )\)-approximate equilibria with social cost at most \(\frac{d+1}{d+\delta }\) times the optimum, for any \(\delta \in [0,1]\). This is the currently best known guarantee of \((\alpha ,\beta )\)-equilibria for polynomial cost functions. Let us begin by analysing the goodness parameters of each monomial.

Lemma 3

Any monomial of degree \(d\ge 1\) is \(\left( \mu ,1,\frac{1}{d+1},\mu \right) \)-good, for any \(\mu \in [\frac{1}{d+1},\frac{1}{d}]\).

Proof

Fix a degree \(d\ge 1\). We will show that the function \(c(x)=x^d\) satisfies conditions (7) and (8) with

$$\begin{aligned} \alpha _1=\xi +\frac{1}{d+1},\qquad \alpha _2=1,\qquad \beta _1= \frac{1}{d+1},\qquad \beta _2=\xi +\frac{1}{d+1}, \end{aligned}$$

for all \(\xi \in [0,\frac{1}{d(d+1)}]\). Then, performing the change of variables \(\mu =\xi +\frac{1}{d+1}\) establishes our lemma, since \(\mu \in [0+\frac{1}{d+1},\frac{1}{d(d+1)}+\frac{1}{d+1}]=[\frac{1}{d+1},\frac{1}{d}]\).

To prove the bounds in \(\alpha _1\), \(\alpha _2\), we are interested in the quantity

$$\begin{aligned} a(w,x)=\frac{1}{w}\int _x^{x+w}c(t)dt+\xi c(w)=\frac{1}{(d+1)w}\left( (x+w)^{d+1}-x^{d+1}\right) +\xi w^d. \end{aligned}$$

By applying the binomial expansion rules, and collecting similar terms, we can further write

$$\begin{aligned} a(w,x)&=\frac{1}{(d+1)w}\left( w^{d+1}+\sum _{j=1}^d\left( {\begin{array}{c}d+1\\ j\end{array}}\right) x^jw^{d+1-j}+x^{d+1}-x^{d+1}\right) +\xi w^{d+1} \nonumber \\&=\frac{1}{d+1}\left( w^d+\sum _{j=1}^d\left( {\begin{array}{c}d+1\\ j\end{array}}\right) x^jw^{d-j}\right) +\xi w^d \nonumber \\&=\left( \frac{1}{d+1}+\xi \right) w^d+\sum _{j=1}^d\frac{1}{d+1}\left( {\begin{array}{c}d+1\\ j\end{array}}\right) x^jw^{d-j} \nonumber \\&=\left( \xi +\frac{1}{d+1}\right) w^d+\sum _{j=1}^d\frac{1}{d-j+1}\left( {\begin{array}{c}d\\ j\end{array}}\right) x^jw^{d-j}, \end{aligned}$$
(11)

where in the last step we simply use the fact that, for \(1\le j\le d\), \(\frac{1}{d+1}\left( {\begin{array}{c}d+1\\ j\end{array}}\right) =\frac{1}{d-j+1}\left( {\begin{array}{c}d\\ j\end{array}}\right) \). We would like to get upper and lower bounds on a(w, x) involving \(c(x+w)\), which can be written as

$$\begin{aligned} c(x+w)=(x+w)^d=w^d+\sum _{j=1}^d\left( {\begin{array}{c}d\\ j\end{array}}\right) x^jw^{d-j}. \end{aligned}$$
(12)

By comparing the coefficients of (11) and (12), we get that (7) is satisfied with

$$\begin{aligned} \alpha _1&=\! \min \left\{ \xi +\frac{1}{d+1},\min _{j=1,\dots ,d}\left\{ \frac{1}{d-j+1}\right\} \right\} \!=\! \min \left\{ \xi +\frac{1}{d+1},\frac{1}{d}\right\} \!=\! \xi +\frac{1}{d+1}\\ \alpha _2&= \max \left\{ \xi +\frac{1}{d+1},\max _{j=1,\dots ,d}\left\{ \frac{1}{d-j+1}\right\} \right\} = \max \left\{ \xi +\frac{1}{d+1},1\right\} =1, \end{aligned}$$

where to compute the maxima and minima we used the fact that \(\xi +\frac{1}{d+1} \le \frac{1}{d(d+1)}+\frac{1}{d+1} = \frac{1}{d} \le 1\), due to the assumptions that \(\xi \le \frac{1}{d(d+1)}\) and \(d\ge 1\).

For the bounds in \(\beta _1,\beta _2\), since \(x^d\) is nondecreasing we can use the simpler condition (8′). Then, we only have to observe that

$$\begin{aligned}\frac{1}{x}\int _0^xc(t)dt&=\frac{1}{d+1}x^d=\frac{1}{d+1}c(x)\\ \multicolumn{2}{l}{\text{ and }}\\ \frac{1}{x}\int _0^xc(t)dt+\xi c(x)&=\frac{1}{d+1}x^d+\xi x^d=\left( \xi +\frac{1}{d+1}\right) c(x). \end{aligned}$$

For the special case of constant cost functions, i.e., 0-degree monomials, it is not difficult to get the following:

Lemma 4

Any constant function is \(\left( 1,1,1,1\right) \)-good.

Proof

Follows directly from Definition 2 by taking \(\xi =0\): for any constant function \(c(x)=c\) we have

$$\begin{aligned} c(x+w)=c(x)=\frac{1}{w}\int _x^{x+w}c(t)dt=\frac{1}{x}\int _0^xc(t)dt=c. \end{aligned}$$

Theorem 5

Any weighted polynomial congestion game of degree \(d\ge 1\) has an \((\lambda ,\frac{d+1}{\lambda })\)-equilibrium, for any \(\lambda \in [d,d+1]\).

Proof

Fix a maximum degree \(d\ge 1\) and a parameter \(\lambda \in [d,d+1]\). Utilizing Lemma 3 with \(\mu =\frac{1}{k+1}\) and Lemma 4, we can see that monomials of degree \(k=0,\dots ,d-1\) are \((\frac{1}{k+1},1,\frac{1}{k+1},\frac{1}{k+1})\)-good; and utilizing Lemma 3 with \(\mu =\frac{1}{\lambda }\) we get that the monomial of degree d is \((\frac{1}{\lambda },1,\frac{1}{d+1},\frac{1}{\lambda })\)-good.

Since any polynomial of degree (at most) d is a conical combination of monomials of degree \(k=0,1,\dots ,d\), in light of Definition 3, we can deduce that our game is \(\left\{ (\alpha _{1,k},\alpha _{2,k},\beta _{1,k},\beta _{2,k})\right\} _{k=0,\ldots ,d}\)-good, with

$$\begin{aligned} \alpha _{1,k}\!=\! {\left\{ \begin{array}{ll} \frac{1}{\lambda }, &{}k=d,\\ \frac{1}{k+1}, &{}k<d; \end{array}\right. } \quad \alpha _{2,k}\!=\!1; \quad \beta _{1,k}\!=\! {\left\{ \begin{array}{ll} \frac{1}{d+1}, &{}k=d,\\ \frac{1}{k+1}, &{}k<d; \end{array}\right. } \quad \beta _{2,k}\!=\! {\left\{ \begin{array}{ll} \frac{1}{\lambda }, &{}k=\!d,\\ \frac{1}{k+1}, &{}k\!<d. \end{array}\right. } \end{aligned}$$

Thus, by Theorem 2 we conclude that our game has an \((\alpha ,\beta )\)-equilibrium with

$$\begin{aligned} \alpha =\max _{0\le k\le d}\frac{\alpha _{2,k}}{\alpha _{1,k}} =\max \left\{ 1,2,\dots ,d,\lambda \right\} =\lambda , \end{aligned}$$

and

$$\begin{aligned} \beta = \frac{\max \limits _{0\le k\le d}\frac{\beta _{2,k}}{\alpha _{1,k}}}{\min \limits _{0\le k\le d} \frac{\beta _{1,k}}{\alpha _{1,k}}} = \frac{1}{\min \left\{ 1,\dots ,1,\frac{1/(d+1)}{1/\lambda }\right\} } = \max \left\{ 1,\frac{d+1}{\lambda }\right\} = \frac{d+1}{\lambda }. \end{aligned}$$

\(\square \)

The parameter \(\lambda \) quantifies the trade-off curve between the approximation guarantee on the existence of \(\alpha \)-approximate equilibria and their PoS. At one extreme case \(\lambda =d+1\), we get that \(\alpha =d+1\) and \(\beta =1\); in other words, there always exist \((d+1)\)-approximate equilibria with an optimal PoS of 1 (as a matter of fact, from [16] we already know that every social optimum is itself a \((d+1)\)-approximate equilibrium). At the other extreme case \(\lambda =d\), we get that

$$\begin{aligned} \alpha =d,\qquad \beta = \frac{d+1}{d}=1+\frac{1}{d}; \end{aligned}$$

in other words, there always exist d-approximate equilibria with PoS at most \(1+\frac{1}{d}\).

4.2 Concave Costs

We now look at nondecreasing concave cost functions. The best known result in this setting is due to Hansknecht et al. [14], who state that 3/2-approximate equilibria exist. However, the proof in their paper is not complete. Moreover, the PoS of the existing approximate equilibria is not discussed. In this section, not only we provide a simpler proof of this result, but we also extend it for a range of \(\lambda \)-approximate equilibria with \(\lambda \in [3/2,2]\), and for a guarantee on the PoS.

Lemma 6

Any nondecreasing concave function is \((\mu ,\mu +\frac{1}{2},\frac{1}{2},\mu +\frac{1}{2})\)-good, for all \(\mu \in [\frac{1}{2},1]\).

Proof

Fix a nondecreasing concave function \(c:\mathbb { R}_+\longrightarrow \mathbb { R}_+\) and a parameter \(0\le \xi \le \frac{1}{2}\). First note that, since c is nonnegative and concave, it must be subadditive. That is, for all \(x,z\ge 0\):

$$\begin{aligned} c(x)+c(z) \ge c(x+z) \end{aligned}$$
(13)

Furthermore, from the Hermite-Hadamard inequality (see, e.g., [32]) and the fact that c is nondecreasing, for any \(0\le a < b\):

$$\begin{aligned} \frac{f(a)+f(b)}{2}\le \frac{1}{b-a}\int _a^b f(t)\, dt\le f(b). \end{aligned}$$
(14)

Applying first (14) for \(a=x\) and \(b=x+w\) we get that

$$\begin{aligned} \frac{c(x)+c(x+w)}{2}\le \frac{1}{w}\int _x^{x+w} c(t)\, dt \le c(x+w), \end{aligned}$$

so

$$\begin{aligned} \frac{1}{w} \int _x^{x+w} c(t)\,dt +\xi \cdot c(w)\le & {} c(x+w)+ \xi c(w)\le (1+\xi )c(x+z)\\ \end{aligned}$$

and

$$\begin{aligned} \frac{1}{w} \int _x^{x+w} c(t)\,dt +\xi \cdot c(w)\ge & {} \frac{c(x)+c(x+w)}{2} +\xi c(w)\\\ge & {} \frac{1}{2} c(x+w) + \xi [c(x)+c(w)], \qquad \text {since}\;\; \xi \le \frac{1}{2},\\\ge & {} \left( \frac{1}{2}+\xi \right) c(x+w), \qquad \text {due to (13).} \end{aligned}$$

Thus, condition (7) is satisfied with \(\alpha _{1}=\frac{1}{2}+\xi \), \(\alpha _{2}=1+\xi \).

Next, applying (14) for \(a=0\) and \(b=x\) we get that

$$\begin{aligned} \frac{1}{2}c(x) \le \frac{c(0)+c(x)}{2} \le \frac{1}{x} \int _0^x c(t)\,dt \le c(x)=(1+\xi )c(x)-\xi c(x), \end{aligned}$$

thus condition (8′) is satisfied with \(\beta _{1}=\frac{1}{2}\), \(\beta _{2}=1+\xi \).

Summarizing, we have shown (see Definition 2) that any concave cost function is \((\xi +\frac{1}{2},\xi +1,\frac{1}{2},\xi +1)\)-good, for any \(\xi \in [0,\frac{1}{2}]\). Performing the change of variables \(\mu =\xi +\frac{1}{2}\) concludes our proof.

Theorem 7

Any weighted congestion game with nondecreasing concave cost functions has a \((\lambda ,\frac{\lambda }{\lambda -1})\)-equilibrium, for any \(\lambda \in [\frac{3}{2},2]\).

Proof

Fix a parameter \(\lambda \in [\frac{3}{2},2]\) and let \(\mu =\frac{1}{2(\lambda -1)}\). Then, \(\mu \in [\frac{1}{2},1]\) and thus, due to Lemma 6, we can deduce that our game is \((\mu ,\mu +\frac{1}{2},\frac{1}{2},\mu +\frac{1}{2})\)-good (according to Definition 2). Deploying Theorem 2 we can establish the existence of an a \((\alpha ,\beta )\)-equilibrium with

$$\begin{aligned} \alpha =\frac{\mu +\frac{1}{2}}{\mu }=1+\frac{1}{2\mu }=1+(\lambda -1)=\lambda \end{aligned}$$

and

$$\begin{aligned} \beta =\frac{(\mu +\frac{1}{2})/\mu }{\frac{1}{2}/\mu }=2\mu +1=\frac{1}{\lambda -1}+1=\frac{\lambda }{\lambda -1}. \end{aligned}$$

4.3 Fair Cost Sharing

In this section, we focus on the fair cost sharing model in which \(c_e(x)=\frac{a_e}{x}\), where \(a_e\) is a positive, resource-dependent value. We assume that \(w_{\min }=1\); this is without loss, since we can just rescale the player weights. This setting was studied by Chen and Roughgarden [13]. Here we improve on their results (see Fig. 1), with a simpler proof.

We must notice that the function \(x\mapsto a_e/x\) is not integrable in an interval starting at 0, and hence we cannot immediately apply our Definition 2. However, based on our discussion in Section 2.1 we can modify the game in order to overcome this. First, we assume for our analysis that \(a_e=1\) since any other choice of \(a_e\) can be seen as a trivial conical combination of the function 1/x (see Definition 3). Next, we change the cost function \(c_e(x)\) to be constant and equal to \(\lambda \) in the interval [0, 1), for some \(\lambda \ge 1\).

Lemma 8

Fix a weighted congestion game with \(w_{\min }=1\). For any \(\lambda \ge 1\), the cost function

$$c(x)={\left\{ \begin{array}{ll}1/x, &{} x\ge 1,\\ \lambda , &{} 0\le x<1\end{array}\right. }$$

is \((\alpha _1,\alpha _2,\beta _1,\beta _2)\)-good with

$$\begin{aligned} \alpha _1&=1,&\alpha _2&=\max \left( \left( 1+\frac{1}{w_{\max }}\right) \ln (1+w_{\max }),\ln (w_{\max })+\lambda \right) ,\\ \beta _1&=\lambda ,&\beta _2&=\ln W+\lambda . \end{aligned}$$

Proof

We will choose \(\xi =0\) in the Definition 2 of good cost functions. Thus, we need to find nonnegative quantities \(\alpha _1\), \(\alpha _2\), \(\beta _1\), \(\beta _2\) such that, for \(x\in \{0\}\cup [1,W]\), \(w\in [1,w_{\max }]\),

$$\begin{aligned} \alpha _1\cdot c(x+w)\le \frac{1}{w}\int _x^{x+w}c(t)dt\le \alpha _2\cdot c(x+w), \end{aligned}$$

and for all \(x\in [1,W]\),

$$\begin{aligned} \beta _1\cdot c(x)\le \frac{1}{x}\int _0^xc (t)dt\le \beta _2\cdot c(x). \end{aligned}$$

For the bounds in \(\alpha _1\), \(\alpha _2\), we are interested in upper and lower bounds on the ratio

$$\begin{aligned} R(w,x)=\frac{\frac{1}{w}\int _x^{x+w}c(t)dt}{c(x+w)}. \end{aligned}$$

When \(x\ge 1\), this becomes

$$\begin{aligned} R(w,x)=\frac{\frac{1}{w}(\ln (x+w)-\ln (x))}{\frac{1}{x+w}}=\left( 1+\frac{x}{w}\right) \ln \left( 1+\frac{w}{x}\right) ; \end{aligned}$$

on the other hand, when \(x=0\), this becomes

$$\begin{aligned} R(w,0)=\frac{\frac{1}{w}(\ln (w)+\lambda )}{\frac{1}{w}}=\ln (w)+\lambda . \end{aligned}$$

Thus, we get

$$\begin{aligned} R(w,x)=\left\{ \begin{array}{cc}\left( 1+\frac{x}{w}\right) \ln \left( 1+\frac{w}{x}\right) ,&{}x\ge 1;\\ \ln w+\lambda ,&{}x=0.\end{array}\right. \end{aligned}$$

In the following technical Lemma 9, we show that the upper branch of R(w, x) is increasing in w and decreasing in x; hence, it is maximized at \(w\rightarrow w_{\max }\), \(x\rightarrow 1\), for a value of \(R(w_{\max },1)=\left( 1+\frac{1}{w_{\max }}\right) \ln (1+w_{\max })\); and minimized at \(w\rightarrow 1\), \(x\rightarrow W\), for a value of \(R(1,W)\ge R(1,\infty )=1\). On the other hand, the lower branch is maximized at \(w\rightarrow w_{\max }\), for a value of \(R(w_{\max },0)=\ln (w_{\max })+\lambda \); and minimized at \(w\rightarrow 1\), for a value of \(R(1,0)=\lambda \ge 1\). This gives the desired bounds on \(\alpha _1\) and \(\alpha _2\).

Lemma 9

For \(w,x\in [1,\infty )\), the function

$$\begin{aligned} R(w,x)=\left( 1+\frac{x}{w}\right) \ln \left( 1+\frac{w}{x}\right) \end{aligned}$$

is increasing in w and decreasing in x.

Proof

Let us apply the change of variables \(\frac{1}{z}\equiv 1+\frac{x}{w}\), so that we can write

$$\begin{aligned} R(w,x)=\left( 1+\frac{x}{w}\right) \ln \left( 1+\frac{w}{x}\right) \equiv \frac{\ln \left( \frac{1}{1-z}\right) }{z}. \end{aligned}$$

Since \(w,x\in [1,\infty )\), it follows that \(1/z\in (1,\infty )\) and thus \(z\in (0,1)\). Notice now that \(\ln \left( \frac{1}{1-z}\right) \) is convex for \(z\in (0,1)\), since its first derivative,

$$\begin{aligned} \frac{d}{dz}\ln \left( \frac{1}{1-z}\right) =-\frac{d}{dz}\ln \left( 1-z\right) =\frac{1}{1-z} \end{aligned}$$

is increasing in z. Since in addition \(\left. \ln \left( \frac{1}{1-z}\right) \right| _{z=0}=0\), we conclude that \(\ln \left( \frac{1}{1-z}\right) /z\) is increasing in z. Since \(z=\frac{w}{w+x}\) is increasing in w and decreasing in x, the result follows.

Next, we look at the bounds in \(\beta _1,\beta _2\). Since \(x\in [1,W]\) we have that \(\int _0^x c(t)dt=\ln x+\lambda \). Moreover, it is immediate to observe that

$$\begin{aligned} \lambda \cdot c(x)=\lambda \cdot \frac{1}{x}\le \frac{1}{x}(\ln x+\lambda )\le \frac{1}{x}(\ln W+\lambda )=(\ln W+\lambda )\cdot c(x). \end{aligned}$$

Theorem 10

Fix a fair cost sharing game with unit minimum weight (\(w_{\min }=1\)), and let \(w_{\max },W\) be the maximum weight and the maximum total load. Then, for any \(\lambda \ge 1\), our game has an \((\alpha ,\beta )\)-equilibrium where

$$\begin{aligned} \alpha =\max \left( \left( 1+\frac{1}{w_{\max }}\right) \ln (1+w_{\max }),\ln (w_{\max })+\lambda \right) ,\qquad \beta =1+\frac{\ln W}{\lambda }. \end{aligned}$$

Proof

Combining Theorem 2 with Lemma 8 we conclude that, for \(\lambda \ge 1\), our game has an \((\alpha ,\beta )\)-equilibrium with

$$\begin{aligned} \alpha&=\frac{\alpha _2}{\alpha _1}=\max \left( \left( 1+\frac{1}{w_{\max }}\right) \ln (1+w_{\max }),\ln (w_{\max })+\lambda \right) ,\\ \beta&=\frac{\beta _2/\alpha _1}{\beta _1/\alpha _1}=\frac{\ln W+\lambda }{\lambda }=1+\frac{\ln W}{\lambda }. \end{aligned}$$

\(\square \)

The parameter \(\lambda \) quantifies the trade-off curve between the approximation guarantee on equilibria and their price of stability. At one extreme case \(\lambda =1\), we get that

$$\begin{aligned} \alpha&=\max \left( \left( 1+\frac{1}{w_{\max }}\right) \ln (1+w_{\max }),\ln (w_{\max })+1\right) =\varTheta (\ln w_{\max }),\\ \beta&=1+\ln W; \end{aligned}$$

in other words, there exist \(\varTheta (\ln w_{\max })\)-approximate equilibria with price of stability \(\varTheta (\ln W)\). At the other extreme case \(\lambda =\varTheta (\ln W)\), we get that

$$\begin{aligned} \alpha&=\max \left( \left( 1+\frac{1}{w_{\max }}\right) \ln (1+w_{\max }),\ln (w_{\max })+\varTheta (\ln W)\right) =\varTheta (\ln W),\\ \beta&=1+\frac{\ln W}{\varTheta (\ln W)}=\varTheta (1); \end{aligned}$$

in other words, there exist \(\varTheta (\ln W)\)-approximate equilibria with constant price of stability \(\varTheta (1)\). The complete trade-off curve can be seen in Fig. 1 (bottom). We can also compare our results with the best known upper bounds. In [13, Lemma 5.3], it was shown that \(\alpha \)-approximate equilibria exist for \(\alpha \ge \log _2[e(1+w_{\max })]\); and in [13, Theorem 5.1], it was shown that \(\left( f,1+\frac{2\log _2(1+W)}{f}\right) \)-equilibria exist for any \(f\ge 2\log _2[e(1+w_{\max })]\). As Fig. 1 shows, we improve on both results.

4.4 Mixtures of Cost Functions

A big advantage of our approach is that we can study the existence of \((\alpha ,\beta )\)-equilibria for games that merge cost functions of two or more different types. For example, in this section we look at congestion games that have both concave costs and polynomial costs (as well as any conical combination). Interestingly, we show that this results in only a small increase in the PoS guarantee of Theorem 5, while the existence guarantee stays the same. For the following theorem we consider polynomials of degree at least 2, since affine functions are themselves concave and would be already captured by Theorem 7.

Theorem 11

Any weighted congestion game with cost functions that are conical combinations of concave and polynomial costs of maximum degree \(d\ge 2\) has an \((\lambda ,1+\frac{d+1}{\lambda })\)-equilibrium, for any \(\lambda \in [d,d+1]\).

Proof

Fix a maximum degree \(d\ge 2\) for the polynomial costs and a parameter \(\lambda \in [d,d+1]\). By defining \(\mu =\frac{d+1}{2\lambda }\) we have that \(\frac{1}{2}\le \mu \le \frac{1}{2}\left( 1+\frac{1}{d}\right) \le 1\), and so by applying Lemma 6 we can derive that any concave cost is \((\mu ,\mu +\frac{1}{2},\frac{1}{2},\mu +\frac{1}{2})\)-good. Next, by Lemma 3 and 4 we can derive that all monomials of degree \(k=0,\dots ,d-1\) are \((\frac{1}{k+1},1,\frac{1}{k+1},\frac{1}{k+1})\)-good and the monomial of degree d is \((\frac{1}{\lambda },1,\frac{1}{d+1},\frac{1}{\lambda })\)-good.

Deploying our black-box tool Theorem 2 (and shortcutting some calculations that we have already performed in the proof of Theorem 5) we can guarantee the existence of an \((\alpha ,\beta )\)-equilibrium with

$$\begin{aligned} \alpha = \max \left\{ 1+\frac{1}{2\mu },\lambda \right\} = \max \left\{ 1+\frac{\lambda }{d+1},\lambda \right\} = \lambda , \end{aligned}$$

since \(2\le d\le \lambda \le d+1\), and

$$\begin{aligned} \beta = \frac{\max \left\{ \frac{\mu +1/2}{\mu },1\right\} }{\min \left\{ \frac{1/2}{\mu },\frac{\lambda }{d+1}\right\} } = \frac{1+\frac{1}{2\mu }}{\min \left\{ \frac{1}{2\mu },\frac{\lambda }{d+1}\right\} } = 1+2\mu = 1+ \frac{d+1}{\lambda }, \end{aligned}$$

where for the third equality we used that, from the definition of \(\mu \), \(\frac{1}{2\mu }= \frac{\lambda }{d+1}\). \(\square \)