Price of Anarchy for Highly Congested Routing Games in Parallel Networks

We consider nonatomic routing games with one source and one destination connected by multiple parallel edges. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we prove that under suitable conditions on the costs the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case, and that these counterexamples already occur in simple networks with only 2 parallel links.

Riccardo Colini-Baldeschi is a member of GNAMPA-INdAM. Roberto Cominetti gratefully acknowledges the support and hospitality of LUISS during a visit in which this research was initiated. Roberto Cominetti’s research is also supported by FONDECYT 1130564 and Núcleo Milenio ICM/FIC RC130003 “Información y Coordinación en Redes”. Marco Scarsini is a member of GNAMPA-INdAM. He gratefully acknowledges the support and hospitality of FONDECYT 1130564 and Núcleo Milenio “Información y Coordinación en Redes”.

Authors and Affiliations

1. Dipartimento di Economia e Finanza, LUISS, Viale Romania 32, 00197, Roma, Italy

   Riccardo Colini-Baldeschi & Marco Scarsini

2. Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Santiago, Chile

   Roberto Cominetti

Corresponding author

Correspondence to Riccardo Colini-Baldeschi.

This article is part of the Topical Collection on Special Issue on Algorithmic Game Theory (SAGT 2016)

Appendix A: Regularly Varying Functions

The reader is referred to [3] for an extended treatment of regularly varying functions. Here we gather a few basic properties that are useful for our results.

Lemma 1

Letβ > 0 and let Θ be a continuous and strictly increasing function, then the following properties are equivalent:

1. (a)

   the function Θ isβ-regularlyvarying,

2. (b)

   the function Θ⁻¹is\(\frac {1}{\beta }\)-regularlyvarying,

3. (c)

   for allγ > 0

   $$\lim\limits_{x \to \infty} \frac{1}{x}{\Theta}^{-1}(\gamma {\Theta}(x)) = \gamma^{1/\beta}. $$

Proof

The equivalence of (a) and (b) is proved in [8, page 22]. The equivalence of (b) and (c) is immediate, since, by setting u = Θ(x), we have

□

Lemma 2

If Θ is a continuous and strictly increasingβ-regularlyvarying function, thenx ⋅Θ(x) and\({{\int }_{0}^{x}} {\Theta }(s) \ \mathrm {d} s\)are (1 + β)-regularlyvarying functions.

Proof

For the functionx ⋅Θ(x) it suffices to note that

For \({{\int }_{0}^{x}} {\Theta }(s) \ \mathrm {d} s\) a direct application of l’Hôpital rule gives

□

The following two lemmata appear in [3, Proposition 1.5.7].

Lemma 3

Fori = 1, 2,let Θ_ibe a continuous and strictly increasingβ_i-regularlyvarying function. Then Θ₁ ∘Θ₂isβ₁ ⋅ β₂-regularlyvarying.

Lemma 4

LetΘ₁and Θ₂be two continuous and strictly increasingβ-regularlyvarying functions, then Θ₁ + Θ₂isβ-regularlyvarying.

Appendix B: Omitted Proofs

1.1 Proofs of Section 4

In the whole subsection, for the sake of simplicity, we call x the flow on e₁ and y the flow on e₂.

Proof (Proof (of Theorem 4))

Let us study the price of anarchy for M ∈ (2a^k, 2a^k+ 1], keeping in mind that a ≥ 2.

Equilibrium cost. :

In the subinterval M ∈ (2a^k, a^k + a^k+ 1] we have

$$\begin{array}{ll} x^{*}=M-a^{k}, &\qquad c_{1}(x^{*})= M-a^{k}\le a^{k + 1},\\ y^{*}=a^{k}, &\qquad c_{2}(y^{*})= a^{k}. \end{array} $$

For M ∈ (a^k + a^k+ 1, 2a^k+ 1] we have

$$\begin{array}{ll} x^{*}=a^{k + 1}, &\qquad c_{1}(x^{*})= a^{k + 1},\\ y^{*}=M-a^{k + 1}, &\qquad c_{2}(y^{*})= a^{k + 1}. \end{array} $$

Therefore

$${\mathsf{WEq}}({\Gamma}_{M})= \left\{\begin{array}{ll} (M-a^{k})^{2}+a^{2k}&\;\text{for } M\in(2a^{k}, a^{k}+a^{k + 1}],\\ Ma^{k + 1}&\;\text{for } M\in(a^{k}+a^{k + 1},2a^{k + 1}]. \end{array}\right. $$

Optimal cost. :

In order to compute the optimal cost

$${\mathsf{Opt}}({\Gamma}_{M})=\min\limits_{0\leq y\leq M} yc_{2}(y)+(M-y)^{2} $$

we decompose the problem over the intervals I_j = (a^j, a^j+ 1] on which c₂(⋅) is constant, namely, we consider the subproblems

$$C_{j}=\min\limits_{y\in I_{j},y\leq M}a^{j + 1}y+(M-y)^{2}. $$

We observe that for j ≥ k + 2 we have a^j ≥ a^k+ 2 ≥ 2a^k+ 1 ≥ M so that C_j is infeasible and therefore \({\mathsf {Opt}}({\Gamma }_{M})=\min \{C_{0},C_{1},\ldots ,C_{k + 1}\}\). In fact, we will show that \({\mathsf {Opt}}({\Gamma }_{M})=\min \{C_{k-1},C_{k}\}\).

Let us compute C_j. Since (M − y)² is symmetric around M, the constraint y ≤ M can be dropped and then the minimum C_j is obtained by projecting onto [a^j, a^j+ 1] the unconstrained minimizer y_j = M − a^j+ 1/2. We get

$$ C_{j}= \left\{\begin{array}{ll} a^{j + 1}a^{j}+(M-a^{j})^{2}&\text{ if } M<a^{j}+\frac{a^{j + 1}}{2},\\ a^{j + 1}\left( M-\frac{a^{j + 1}}{2}\right)+\left( \frac{a^{j + 1}}{2}\right)^{2}&\text{ if } a^{j}+\frac{a^{j + 1}}{2}\leq M\leq a^{j + 1}+\frac{a^{j + 1}}{2},\\ a^{j + 1}a^{j + 1}+(M-a^{j + 1})^{2}&\text{ if } M>a^{j + 1}+\frac{a^{j + 1}}{2}. \end{array}\right. $$

(5)

□

Claim 7

Forj ≤ k − 1we haveC_j = a^j+ 1a^j+ 1 + (M − a^j+ 1)²andC_j− 1 ≥ C_j.

Proof

The expression for C_j follows from (5) if we note that \(M > 2a^{k} \ge \frac {3}{2}a^{j + 1}\). In order to prove that C_j− 1 ≥ C_j we observe that

Since M > 2a^k = a^k + a^k ≥ a^j + a^j+ 1, this holds true. □

Claim 8

C_k+ 1 = a^k+ 2a^k+ 1 + (M − a^k+ 1)² ≥ C_k− 1.

Proof

Since \(M \le 2 a^{k + 1} \le a^{k + 1}+\frac {a^{k + 2}}{2}\) we get the expression for C_k+ 1 from (5). Then

Since M ≤ 2a^k+ 1 it suffices to have 4a^k+ 1 ≤ a^k(a² + 2a + 2) which is easily seen to hold. □

Combining the previous claims we get that \({\mathsf {Opt}}({\Gamma }_{M})=\min \{C_{k-1},C_{k}\}\). It remains to figure out which one between C_k− 1 and C_k attains the minimum. This depends on where M is located within the interval (2a^k, 2a^k+ 1] as explained in our next claim. In the sequel we denote

and we observe that

Claim 9

ForM ∈ (2a^k, 2a^k+ 1] we have

Proof

Recall that a ≥ 2. From (5) we have C_k− 1 = (a^k)² + (M − a^k)² whereas the expression for C_k changes depending where M is located.

1. (a)

   Initial intervalM ∈ (2a^k, αa^k).

   Here \(M<a^{k}+\frac {1}{2}a^{k + 1}\) so that (5) gives C_k = a^k+ 1a^k + (M − a^k)². Hence, clearly C_k− 1 ≤ C_k and Opt(Γ_M) = C_k− 1.

2. (b)

   Final intervalM ∈ (γa^k, 2a^k+ 1].

   Here \(M>\gamma a^{k} =\frac {3}{2}a^{k + 1}\) so that (5) gives C_k = (a^k+ 1)² + (M − a^k+ 1)². Proceeding as in the proof of Claim 7, we have C_k− 1 ≥ C_k if and only if M ≥ a^k + a^k+ 1. The latter holds since \(M \ge \frac {3}{2}a^{k + 1} \ge a^{k + 1}+a^{k}\). Hence Opt(Γ_M) = C_k.

3. (c)

   Intermediate intervalM ∈ [αa^k, γa^k].

Here \(a^{k}+\frac {1}{2}a^{k + 1}\leq M \leq \frac {3}{2}a^{k + 1}\) so that (5) gives

Then, denoting z = M/a^k we have

The upper limit for z is precisely β while the lower limit is smaller than α. Hence Opt(Γ_M) = C_k− 1 for M ∈ [αa^k, βa^k] and Opt(Γ_M) = C_k for M ∈ [βa^k, γa^k].

Figure 4 illustrates the different intervals in which the equilibrium (above) and the optimum (below) change. Notice that Opt(Γ_M) varies continuously even at breakpoints, whereas WEq(Γ_M) has a jump at a^k + a^k+ 1. We now proceed to examine the price of anarchy which will be expressed as a function of z = M/a^k.

Breakpoints for optimum and equilibrium

Full size image

From the expressions of WEq(Γ_M) and Opt(Γ_M) (see Fig. 4) it follows that PoA(Γ_M) = 1 throughout the initial interval M ∈ (2a^k, βa^k). Over the next interval M ∈ [βa^k, a^k + a^k+ 1] we have

which increases from 1 at z = β up to (4 + 4a²)/(a(4 + 3a)) at z = 1 + a.

At M = a^k + a^k+ 1 the equilibrium has a discontinuity and PoA(Γ_M) jumps to (4 + 4a)/(4 + 3a) and then it decreases over the interval \(M\in (a^{k}+a^{k + 1},\frac {3}{2}a^{k + 1})\) as

Finally, for \(M\in (\frac {3}{2}a^{k + 1},2a^{k + 1}]\) the price of anarchy continues to decrease as

going back to 1 at z = 2a which corresponds to M = 2a^k+ 1.

Thus the price of anarchy oscillates over each interval (2a^k, 2a^k+ 1] between a minimum value of 1 and a maximum of (4 + 4a)/(4 + 3a). This completes the proof of Theorem 4. □

Proof 15 (Proof (of Theorem 5))

Consider a parallel network with two edges with a quadratic cost c₁(x) = x² on the upper edge and a lower edge cost defined by linearly interpolating c₁, that is, for a ≥ 2 we let (see Fig. 5)

x² and its linear interpolation

Full size image

Note that c₁ and c₂ are convex. Consider the optimal cost problem

Since the function h(y) = yc₂(y) is non-differentiable, the optimality condition reads 3x² ∈ ∂h(y). In particular, the subdifferential at y = a^k is

and there is a range of values of M for which the optimal solution is y = a^k. The smallest such M is obtained when 3x² = a^2(k− 1)(2a² + a). This gives as optimal solution y = a^k and x = a^k− 1b, with \(b=\sqrt {(2a^{2}\,+\,a)/3}\), corresponding to M_k = a^k− 1[a + b] with optimal value

In order to find the equilibrium for M_k we solve the equation x² = c₂(y) with x + y = M_k. A routine calculation gives x = a^k− 1c and y = a^k− 1d with

Note that 1 < d < a so that y ∈ (a^k− 1, a^k), and therefore the equilibrium cost is

Putting together the previous formulae we get

For a = 2 this expression evaluates to \({\mathsf {PoA}}({\Gamma }_{M_{k}})\sim 1.0059\) from which the result follows. □

Proof (of Theorem 6)

Take a fixed sequence α_k > 0 such that \(\alpha _{k + 1}/\alpha _{k}\to \infty \) and consider a game \({\Gamma }_{M}=(\mathcal {G},M,\boldsymbol {c})\), where \(\mathcal {G}=(V,E)\) is a simple Pigou network with two parallel links with costs given by

Since we are interested in asymptotic results, we are concerned only with the case c(x) =e^x/x.

Depending on the location of M, the equilibrium is given by

We note that at the point M_k = α_k + α_k+ 1 the equilibrium has a discontinuity. The cost inmediately to the right of this point is

Let us now turn to computing the optimum

which we decomposed into the restricted minima C_j given by

The unconstrained minimum for each j is obtained by solving the equation \(\mathrm {e}^{x}=\frac {\mathrm {e}^{\alpha _{j + 1}}}{\alpha _{j + 1}}\) so that denoting

we have the following expression for the constrained minimizers \(\tilde y_{j}\) and the values C_j

We remark that y_j varies continuously with M, and therefore the same holds for \(\tilde y_{j}\) and C_j. It follows that Opt(Γ_M) is also continuous in M.

Claim 10

LetM = M_k. For klargeenough we have

Proof

1. a)

   C_jisdecreasing forj ≤ k − 1. Indeed, for j ≤ k − 1 we have M > 2α_j+ 1 so that

   $$y_{j}=M - \alpha_{j + 1} + \ln \alpha_{j + 1} > \alpha_{j + 1} + \ln \alpha_{j + 1} > \alpha_{j + 1} $$

   and therefore

   $$C_{j}=\mathrm{e}^{M-\alpha_{j + 1}} + \mathrm{e}^{\alpha_{j + 1}}.$$

   Denoting h(x) :=e^M−x +e^x, the inequality C_j ≤ C_j− 1 is equivalent to h(α_j+ 1) ≤ h(α_j), which holds because h is decreasing on the interval [0,M/2] and since \(\alpha _{j} \le \alpha _{j + 1} \le \alpha _{k} \le \frac {M}{2}\).

2. b)

   C_jis increasing forj ≥ k + 1. We first show that if k is large enough then y_j < α_j. Considering the expression of y_j, this inequality is equivalent to \(M < \alpha _{j} + \alpha _{j + 1} - \ln \alpha _{j + 1}\). Now, since M ≤ 2α_k+ 1 ≤ 2α_j it suffices to show that

   $$2 \alpha_{j} < \alpha_{j} + \alpha_{j + 1} - \ln \alpha_{j + 1} $$

   which can also be written as

   $$\frac{\ln \alpha_{j + 1}}{\alpha_{j + 1}} + \frac{\alpha_{j}}{\alpha_{j + 1}} < 1.$$

   Now, our choice of the sequence α_j implies that the right hand side tends to zero as \(j\to \infty \), proving that y_j < α_j for j ≥ k + 1 provided that k is chosen large enough. In this situation we have for all j ≥ k + 1

   $$C_{j}=\mathrm{e}^{M- \alpha_{j}}+\frac{\alpha_{j}}{\alpha_{j + 1}}\mathrm{e}^{\alpha_{j + 1}}. $$

   In order to show that C_j ≤ C_j+ 1 we note that

   $$\begin{array}{@{}rcl@{}} C_{j} \le C_{j + 1} \iff \mathrm{e}^{M- \alpha_{j}}+\frac{\alpha_{j}}{\alpha_{j + 1}}\mathrm{e}^{\alpha_{j + 1}} \le \mathrm{e}^{M- \alpha_{j + 1}}+\frac{\alpha_{j + 1}}{\alpha_{j + 2}}\mathrm{e}^{\alpha_{j + 2}}. \end{array} $$

   For x ≥ 1 the function e^x/x is increasing so that

   $$\mathrm{e}^{M- \alpha_{j}}+\alpha_{j}\frac{\mathrm{e}^{\alpha_{j + 1}}}{\alpha_{j + 1}} \le \mathrm{e}^{M- \alpha_{j}}+\alpha_{j}\frac{\mathrm{e}^{\alpha_{j + 2}}}{\alpha_{j + 2}}. $$

   It remains to replace α_j by α_j+ 1 on the right for which it suffices to prove that the function

   $$g(x):=\mathrm{e}^{M-x}+x\frac{\mathrm{e}^{\alpha_{j + 2}}}{\alpha_{j + 2}} $$

   is increasing for x ≥ α_k+ 1. Indeed, since \(g^{\prime }(x)=\frac {\mathrm {e}^{\alpha _{j + 2}}}{\alpha _{j + 2}}-\mathrm {e}^{M-x}\) we have

   $$\begin{array}{@{}rcl@{}} g^{\prime}(x) \ge 0 &\iff& M-x \le \alpha_{j + 2} - \ln \alpha_{j + 2} \\ &\iff& M \le x + \alpha_{j + 2} - \ln \alpha_{j + 2}, \end{array} $$

   which is true for x ≥ α_k+ 1 iff \(M \le \alpha _{k + 1} + \alpha _{j + 2} - \ln \alpha _{j + 2}\). Since M ≤ 2α_k+ 1, it is enough to have \(\alpha _{k + 1} \le \alpha _{j + 2} - \ln \alpha _{j + 2}\), and since \(x \mapsto x - \ln x\) is increasing for x ≥ 1, it suffices to prove that \(\alpha _{k + 1} \le \alpha _{k + 2} - \ln \alpha _{k + 2}\), that is,

   $$ \frac{\ln \alpha_{k + 2}}{\alpha_{k + 2}}+\frac{\alpha_{k + 1}}{\alpha_{k + 2}} \le 1. $$

   (7)

   By our choice of α_k this holds for k large enough, which completes the proof of Claim 10.

□

Claim 11

LetM = M_k. For all klarge enough we have

Proof

From the proof of Claim 10 we have

and it is easy to see that C_k− 1 ≤ C_k+ 1 so that in fact \({\mathsf {Opt}}({\Gamma }_{M_{k}})=\min \{C_{k-1},C_{k}\}\).

Now, the expression of C_k depends on the location of \(y_{k}=M-\alpha _{k + 1}+\ln \alpha _{k + 1}\) with respect to the interval [α_k, α_k+ 1]. Substituting the value of M = α_k + α_k+ 1 we get \(y_{k}=\alpha _{k}+\ln \alpha _{k + 1}\) so that clearly y_k > α_k. Also, for k large we have y_k < α_k+ 1 since

It follows that

and therefore it remains to show that C_k ≤ C_k− 1. The latter is equivalent to

which can be rewritten as

Since the right hand side tends to 0, this inequality holds for k large enough. □

Conclusion

Let us compute the price of anarchy just to the right of M_k, namely

Since Opt(Γ_M) is continuous in M, using (6) and (8) we get

from which we get the conclusion

Reprints and permissions