Abstract
An open problem is presented regarding the existence of pure strategy Nash equilibrium (PNE) in network congestion games with a finite number of non-identical players, in which the strategy set of each player is the collection of all paths in a given network that link the player’s origin and destination vertices, and congestion increases the costs of edges. A network congestion game in which the players differ only in their origin–destination pairs is a potential game, which implies that, regardless of the exact functional form of the cost functions, it has a PNE. A PNE does not necessarily exist if (i) the dependence of the cost of each edge on the number of users is player- as well as edge-specific or (ii) the (possibly, edge-specific) cost is the same for all players but it is a function (not of the number but) of the total weight of the players using the edge, with each player i having a different weight w i . In a parallel two-terminal network, in which the origin and the destination are the only vertices different edges have in common, a PNE always exists even if the players differ in either their cost functions or weights, but not in both. However, for general two-terminal networks this is not so. The problem is to characterize the class of all two-terminal network topologies for which the existence of a PNE is guaranteed even with player-specific costs, and the corresponding class for player-specific weights. Some progress in solving this problem is reported.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Anantharam, V.: On the Nash Dynamics of Congestion Games With Player-Specific Utility. In: Proceedings of the 43rd IEEE Conference on Decision and Control, pp. 4673–4678 (2004)
Awerbuch, B., Azar, Y., Epstein, A.: The Price of Routing Unsplittable Flow. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 57–66 (2005)
Beckmann, M., McGuire, C.B., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)
Christodoulou, G., Koutsoupias, E.: The Price of Anarchy of Finite Congestion Games. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 67–73 (2005)
Diestel, R.: Graph Theory, 3rd edn. Graduate Texts in Mathematics, vol. 173. Springer, Heidelberg (2005)
Even-Dar, E., Kesselman, A., Mansour, Y.: Convergence Time to Nash Equilibria. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 502–513. Springer, Heidelberg (2003)
Fabrikant, A., Papadimitriou, C., Talwar, K.: The Complexity of Pure Nash Equilibria. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 604–612 (2004)
Fotakis, D., Kontogiannis, S., Spirakis, P.: Selfish Unsplittable Flows. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 593–605. Springer, Heidelberg (2004)
Fotakis, D., Kontogiannis, S., Spirakis, P.: Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol. 3879, pp. 161–175. Springer, Heidelberg (2006)
Holzman, R., Law-yone (Lev-tov), N.: Network Structure and Strong Equilibrium in Route Selection Games. Math. Social Sci. 46, 193–205 (2003)
Konishi, H.: Uniqueness of User Equilibrium in Transportation Networks With Heterogeneous Computers. Transportation Sci. 38, 315–330 (2004)
Konishi, H., Le Breton, M., Weber, S.: Pure Strategy Nash Equilibrium in a Group Formation Game With Positive Externalities. Games Econom. Behav. 21, 161–182 (1997)
Koutsoupias, E., Papadimitriou, C.: Worst-Case Equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, p. 404. Springer, Heidelberg (1999)
Libman, L., Orda, A.: Atomic Resource Sharing in Noncooperative Networks. Telecommunication Sys. 17, 385–409 (2001)
Milchtaich, I.: Congestion Games With Player-Specific Payoff Functions. Games Econom. Behav. 13, 111–124 (1996)
Milchtaich, I.: Crowding Games are Sequentially Solvable. Internat. J. Game Theory 27, 501–509 (1998)
Milchtaich, I.: Topological Conditions for Uniqueness of Equilibrium in Networks. Math. Oper. Res. 30, 225–244 (2005)
Milchtaich, I.: Network Topology and the Efficiency of Equilibrium. Games Econom. Behav. 57, 321–346 (2006)
Monderer, D., Shapley, L.S.: Potential Games. Games Econom. Behav. 14, 124–143 (1996)
Morgenstern, O., von Neumann, J.: Theory of Games and Economic Behavior, 3rd edn. Princeton University Press, Princeton (1953)
Morris, S., Ui, T.: Best Response Equivalence. Games Econom. Behav. 49, 260–287 (2004)
Papadimitriou, C.H.: Algorithms, Games, and the Internet. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 749–753 (2001)
Richman, O., Shimkin, N.: Topological Uniqueness of the Nash Equilibrium for Atomic Selfish Routing. Math. Oper. Res. (forthcoming)
Rosenthal, R.W.: A Class of Games Possessing Pure-Strategy Nash Equilibrium. Internat. J. Game Theory 2, 65–67 (1973)
Roughgarden, T.: The Price of Anarchy is Independent of the Network Topology. J. Comput. System Sci. 67, 341–364 (2003)
Roughgarden, T.: Selfish Routing With Atomic Players. In: Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1184–1185 (2005)
Roughgarden, T., Tardos, É.: How Bad is Selfish Routing? J. ACM 49, 236–259 (2002)
Roughgarden, T., Tardos, É.: Bounding the Inefficiency of Equilibria in Nonatomic Congestion Games. Games Econom. Behav. 47, 389–403 (2004)
Schmeidler, D.: Equilibrium Points of Nonatomic Games. J. Stat. Phys. 7, 295–300 (1970)
Wardrop, J.G.: Some Theoretical Aspects of Road Traffic Research. In: Proceedings of the Institute of Civil Engineers, Part II, vol. 1, pp. 325–378 (1952)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Milchtaich, I. (2006). The Equilibrium Existence Problem in Finite Network Congestion Games. In: Spirakis, P., Mavronicolas, M., Kontogiannis, S. (eds) Internet and Network Economics. WINE 2006. Lecture Notes in Computer Science, vol 4286. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11944874_9
Download citation
DOI: https://doi.org/10.1007/11944874_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68138-0
Online ISBN: 978-3-540-68141-0
eBook Packages: Computer ScienceComputer Science (R0)