Skip to main content
Log in

Strong equilibrium in network congestion games: increasing versus decreasing costs

  • Published:
International Journal of Game Theory Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. We give here a verbal description of this class of games. Precise definitions are given in Sect. 2.

  2. A related model with a continuum of players, each having a negligible effect on the congestion, was introduced earlier in transportation science, e.g., Beckmann et al. (1956). This nonatomic variant of our model was also studied recently in the game theoretic literature by Milchtaich (2005, 2006).

  3. The case when all players have the same destination but may have any origins is equivalent, and hence will not be treated explicitly.

  4. The correct terminology for INC is nondecreasing costs, and that for DEC is nonincreasing costs. But we prefer the shorter and more transparent terms.

  5. This observation was made earlier, in related models, by Rozenfeld and Tennenholtz (2006) and Epstein et al. (2009).

  6. 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).

  7. 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.

  8. In some cases, the set of players \(N^{\prime }\) may be empty. Allowing such trivial induced games does not cause any difficulty.

  9. 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.

  10. 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

    Google Scholar 

  • Chartrand G, Lesniak L, Zhang P (2011) Graphs & digraphs, 5th edn. CRC Press, Boca Raton, FL

    Google Scholar 

  • Duffin RJ (1965) Topology of series-parallel networks. J Math Anal Appl 10:303–318

    Article  Google Scholar 

  • Epstein A, Feldman M, Mansour Y (2009) Strong equilibrium in cost sharing connection games. Games Econ Behav 67:51–68

    Article  Google Scholar 

  • Holzman R, Law-Yone N (1997) Strong equilibrium in congestion games. Games Econ Behav 21:85–101

    Article  Google Scholar 

  • Holzman R, Law-yone (Lev-tov) N (2003) Network structure and strong equilibrium in route selection games. Math Soc Sci 46:193–205

    Article  Google Scholar 

  • Milchtaich I (2005) Topological conditions for uniqueness of equilibrium in networks. Math Oper Res 30:225–244

    Article  Google Scholar 

  • Milchtaich I (2006) Network topology and the efficiency of equilibrium. Games Econ Behav 57:321–346

    Article  Google Scholar 

  • Monderer D, Shapley LS (1996) Potential games. Games Econ Behav 14:124–143

    Article  Google Scholar 

  • Rosenthal RW (1973a) A class of games possessing pure-strategy Nash equilibria. Int J Game Theory 2:65–67

    Article  Google Scholar 

  • Rosenthal RW (1973b) The network equilibrium problem in integers. Networks 3:53–59

    Article  Google Scholar 

  • 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

Download references

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

Authors

Corresponding author

Correspondence to Ron Holzman.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00182-014-0448-4

Keywords

JEL Classification

Navigation