Abstract
A network congestion game is played on a directed, two-terminal network. Every player chooses a route from his origin to his destination. The cost of a route is the sum of the costs of the arcs on it. The arc cost is a function of the number of players who use it. Rosenthal proved that such a game always has a Nash equilibrium in pure strategies. Here we pursue a systematic study of the classes of networks for which a strong equilibrium is guaranteed to exist, under two opposite monotonicity assumptions on the arc cost functions. Our main results are: (a) If costs are increasing, strong equilibrium is guaranteed on extension-parallel networks, regardless of whether the players’ origins and destinations are the same or may differ. (b) If costs are decreasing, and the players have the same origin but possibly different destinations, strong equilibrium is guaranteed on series-parallel networks. (c) If costs are decreasing, and both origins and destinations may differ, strong equilibrium is guaranteed on multiextension-parallel networks. In each case, the network condition is not only sufficient but also necessary in order to guarantee strong equilibrium. These results extend and improve earlier ones by Holzman and Law-Yone in the increasing case, and by Epstein et al. in the decreasing case.
Similar content being viewed by others
Notes
We give here a verbal description of this class of games. Precise definitions are given in Sect. 2.
The case when all players have the same destination but may have any origins is equivalent, and hence will not be treated explicitly.
The correct terminology for INC is nondecreasing costs, and that for DEC is nonincreasing costs. But we prefer the shorter and more transparent terms.
It is natural to try to analyze a AOAD game \(G\) on \(D\) by associating with it an auxiliary game \(\overline{G}\) on \(D\), as follows. In \(\overline{G}\), all players have origin \(s_0\) and destination \(s_1\), but each player \(i \in N\) may use only routes that contain \(F^i\). Thus, the strategy spaces \(\Sigma ^i\) in \(G\) correspond bijectively to the strategy spaces \(\overline{\Sigma }^i\) in \(\overline{G}\). To account for the extra usage of arcs in \(\overline{G}\) compared to \(G\), the cost functions in \(\overline{G}\) are reset as \(\overline{c}_a(k)=c_a(k-f_a)\), \(f_a < k \le |N|\), where \(f_a=|\{i \in N:\, a \in F^i\}|\). One can show that a Nash equilibrium \(\overline{R}\) in \(\overline{G}\) corresponds to a Nash equilibrium \(R\) in \(G\). However, this approach breaks down when considering strong equilibrium: it may be the case that \(P^S\) is a profitable deviation of coalition \(S\) from \(R\) in \(G\), while the corresponding deviation \(\overline{P}^S\) from \(\overline{R}\) is not profitable in \(\overline{G}\). This may occur when a player \(i \in S\) is adversely affected in \(\overline{G}\) by the added congestion on an arc \(a \in F^i\), caused by another player \(j \in S\) with \(a \in P^j \setminus R^j\). Thus, AOAD games are not equivalent to SOSD games with restricted choices of routes. That is why we need a more delicate proof technique, which uses tools developed earlier for SOSD games, but does so in a significantly more involved way than in Holzman and Law-Yone (1997).
In general, given an extension-parallel network \(D\) we can construct a tree-representation \(T\) by induction on the extension-parallel construction of \(D\). Indeed, a single-arc network is represented by a single-edge tree. If \(D\) is obtained from \(D^{\prime }\) by an extension with arc \(a\), then \(T\) is obtained from \(T^{\prime }\) by adding a new root joined by an edge to the root of \(T^{\prime }\), and labeling the latter by \(a\). If \(D\) is the parallel join of \(D^{\prime }\) and \(D^{\prime \prime }\), then \(T\) is constructed as the union of \(T^{\prime }\) and \(T^{\prime \prime }\) with their roots identified.
In some cases, the set of players \(N^{\prime }\) may be empty. Allowing such trivial induced games does not cause any difficulty.
Our proof is essentially the same as the proofs of the corresponding (but less general) statements in Epstein et al. (2009), with one significant simplification. Much of the effort in their proof was devoted to showing that if a strong equilibrium exists, then one with \(\pi ^i(R)=\text {opt}^i(G)\) for complete players also exists (their Lemma 3.2). We get this extra property along with the inductive proof of existence, at no extra cost.
The construction in Fig. 4b was given by Epstein et al. (2009). The network \(W\), however, was given by them as an example of a non-series-parallel network which, nevertheless, has the property that every same-origin fair connection game on it possesses a strong equilibrium. Our construction in Fig. 4a shows that this depends on the special cost structure of fair connection games, and does not extend to arbitrary decreasing costs.
References
Anshelevich E, Dasgupta A, Kleinberg J, Tardos É, Wexler T, Roughgarden T (2004) The price of stability for network design with fair cost allocation. In: Proceedings of the 45th annual IEEE symposium on foundations of computer science (FOCS), pp 295–304
Aumann RJ (1959) Acceptable points in general cooperative \(n\)-person games. In: Tucker AW, Luce RD (eds) Contributions to the theory of games, vol 4. In: Ann Math Stud, vol 40. Princeton University Press, pp 287–324
Beckmann M, McGuire CB, Winsten CB (1956) Studies in the economics of transportation. Yale University Press, New Haven, CT
Chartrand G, Lesniak L, Zhang P (2011) Graphs & digraphs, 5th edn. CRC Press, Boca Raton, FL
Duffin RJ (1965) Topology of series-parallel networks. J Math Anal Appl 10:303–318
Epstein A, Feldman M, Mansour Y (2009) Strong equilibrium in cost sharing connection games. Games Econ Behav 67:51–68
Holzman R, Law-Yone N (1997) Strong equilibrium in congestion games. Games Econ Behav 21:85–101
Holzman R, Law-yone (Lev-tov) N (2003) Network structure and strong equilibrium in route selection games. Math Soc Sci 46:193–205
Milchtaich I (2005) Topological conditions for uniqueness of equilibrium in networks. Math Oper Res 30:225–244
Milchtaich I (2006) Network topology and the efficiency of equilibrium. Games Econ Behav 57:321–346
Monderer D, Shapley LS (1996) Potential games. Games Econ Behav 14:124–143
Rosenthal RW (1973a) A class of games possessing pure-strategy Nash equilibria. Int J Game Theory 2:65–67
Rosenthal RW (1973b) The network equilibrium problem in integers. Networks 3:53–59
Rozenfeld O, Tennenholtz M (2006) Strong and correlated strong equilibria in monotone congestion games. In: Proceedings of the 2nd international workshop on internet and network economics (WINE)
Valdes J (1978) Parsing flowcharts and series-parallel graphs. STAN-CS-78-682, Stanford University
Acknowledgments
This research was supported by the FIRST program of the Israel Science Foundation (Grant No. 1013/08). Part of Ron Holzman’s research was done while visiting the Department of Mathematical Sciences, Carnegie Mellon University. Dov Monderer gratefully thanks the Electronic Commerce Technion-Microsoft Research Center for its financial contribution.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Holzman, R., Monderer, D. Strong equilibrium in network congestion games: increasing versus decreasing costs. Int J Game Theory 44, 647–666 (2015). https://doi.org/10.1007/s00182-014-0448-4
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-014-0448-4