research-article

On the impact of combinatorial structure on congestion games

Authors:

Heiner Ackermann,

Berthold VöckingAuthors Info & Claims

Journal of the ACM (JACM), Volume 55, Issue 6

Article No.: 25, Pages 1 - 22

https://doi.org/10.1145/1455248.1455249

Published: 17 December 2008 Publication History

Abstract

We study the impact of combinatorial structure in congestion games on the complexity of computing pure Nash equilibria and the convergence time of best response sequences. In particular, we investigate which properties of the strategy spaces of individual players ensure a polynomial convergence time. We show that if the strategy space of each player consists of the bases of a matroid over the set of resources, then the lengths of all best response sequences are polynomially bounded in the number of players and resources. We also prove that this result is tight, that is, the matroid property is a necessary and sufficient condition on the players' strategy spaces for guaranteeing polynomial-time convergence to a Nash equilibrium.

In addition, we present an approach that enables us to devise hardness proofs for various kinds of combinatorial games, including first results about the hardness of market sharing games and congestion games for overlay network design. Our approach also yields a short proof for the PLS-completeness of network congestion games. In particular, we show that network congestion games are PLS-complete for directed and undirected networks even in case of linear latency functions.

References

[1]

Ackermann, H., Röglin, H., and Vöcking, B. 2006. Pure Nash equilibria in player-specific and weighted congestion games. In Proceedings of the 2nd International Workshop on Internet and Network Economics (WINE). Lecture Notes in Computer Science, vol. 4286. Springer-Verlag, New York, 50--61.

Digital Library

[2]

Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., and 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). IEEE Computer Society Press, Los Alamitos, CA, 295--304.

Digital Library

[3]

Anshelevich, E., Dasgupta, A., Tardos, E., and Wexler, T. 2003. Near-optimal network design with selfish agents. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 511--520.

Digital Library

[4]

Chakrabarty, D., Mehta, A., and Nagarajan, V. 2005. Fairness and optimality in congestion games. In Proceedings of the 6th ACM Conference on Electronic Commerce. ACM, New York, 52--57.

Digital Library

[5]

Fabrikant, A., Papadimitriou, C. H., and Talwar, K. 2004. The complexity of pure Nash equilibria. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 604--612.

Digital Library

[6]

Floren, P., and Orponen, P. 1994. Complexity issues in discrete Hopfield networks. Department of Computer Science, University of Helsinki, Helsinki, Finland, Tech. Rep. A-1994-4.

[7]

Goemans, M. X., Li, E. L., Mirrokni, V. S., and Thottan, M. 2004. Market sharing games applied to content distribution in ad-hoc networks. In Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). ACM, New York, 55--66.

Digital Library

[8]

Ieong, S., McGrew, R., Nudelman, E., Shoham, Y., and Sun, Q. 2005. Fast and compact: A simple class of congestion games. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI). AAAI Press, Menlo Park, CA, 489--494.

Digital Library

[9]

Johnson, D. S., Papadimitriou, C. H., and Yannakakis, M. 1988. How easy is local search&quest; J. Comput. Syst. Sci. 37, 1, 79--100.

Digital Library

[10]

Mirrokni, V. S. 2005. Approximation algorithms for distributed and selfish agents. Ph.D. dissertation, Massachusetts Institute of Technology.

Digital Library

[11]

Orponen, P. 1997. Computing with truly asynchronous threshold logic networks. Theoret. Comput. Sci. 174, 1--2, 123--136.

Digital Library

[12]

Poljak, S. 1995. Integer linear programs and local search for max-cut. SIAM J. Comput. 24, 4, 822--839.

Digital Library

[13]

Rosenthal, R. W. 1973. A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65--67.

Digital Library

[14]

Schäffer, A. A., and Yannakakis, M. 1991. Simple local search problems that are hard to solve. SIAM J. Comput. 20, 1, 56--87.

Digital Library

[15]

Schrijver, A. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer. Volume B, Matroids, Trees, Stable Sets, Chapters 39--69.

[16]

Stoica, I., Adkins, D., Zhuang, S., Shenker, S., and Surana, S. 2004. Internet indirection infrastructure. IEEE/ACM Trans. Netw. 12, 2, 205--218.

Digital Library

[17]

Werneck, R. F., and Setubal, J. C. 2000. Finding minimum congestion spanning trees. ACM J. Exper. Alg. 5, 11.

Digital Library

Cited By

Takazawa K(2025)A Unified Model of Congestion Games with PrioritiesWALCOM: Algorithms and Computation10.1007/978-981-96-2845-2_23(361-376)Online publication date: 21-Feb-2025
https://doi.org/10.1007/978-981-96-2845-2_23
Ma MBai TCheng XXiao M(2025)Facility Assignment with Fair Cost Sharing: Equilibrium and Mechanism DesignComputing and Combinatorics10.1007/978-981-96-1090-7_17(203-215)Online publication date: 5-Mar-2025
https://doi.org/10.1007/978-981-96-1090-7_17
Irfan MChan HSoundy JDastani MSichman JAlechina NDignum V(2024)Computing Nash Equilibria in Multidimensional Congestion GamesProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663143(2309-2311)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663143
Show More Cited By

Index Terms

On the impact of combinatorial structure on congestion games
1. Theory of computation

Recommendations

Pure Nash equilibria in player-specific and weighted congestion games

Unlike standard congestion games, weighted congestion games and congestion games with player-specific delay functions do not necessarily possess pure Nash equilibria. It is known, however, that there exist pure equilibria for both of these variants in ...
Pure Nash equilibria in restricted budget games

In budget games, players compete over resources with finite budgets. For every resource, a player has a specific demand and as a strategy, he chooses a subset of resources. If the total demand on a resource does not exceed its budget, the utility of ...
Congestion games with mixed objectives

We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We ...

Comments

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 55, Issue 6

December 2008

114 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/1455248

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 December 2008

Accepted: 01 September 2008

Revised: 01 April 2008

Received: 01 August 2007

Published in JACM Volume 55, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

185
Total Citations
View Citations
1,311
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)6

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Takazawa K(2025)A Unified Model of Congestion Games with PrioritiesWALCOM: Algorithms and Computation10.1007/978-981-96-2845-2_23(361-376)Online publication date: 21-Feb-2025
https://doi.org/10.1007/978-981-96-2845-2_23
Ma MBai TCheng XXiao M(2025)Facility Assignment with Fair Cost Sharing: Equilibrium and Mechanism DesignComputing and Combinatorics10.1007/978-981-96-1090-7_17(203-215)Online publication date: 5-Mar-2025
https://doi.org/10.1007/978-981-96-1090-7_17
Irfan MChan HSoundy JDastani MSichman JAlechina NDignum V(2024)Computing Nash Equilibria in Multidimensional Congestion GamesProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663143(2309-2311)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663143
Bilò VFlammini MMonaco GMoscardelli LVinci CDastani MSichman JAlechina NDignum V(2024)On Green Sustainability of Resource Selection Games with Equitable Cost-SharingProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662868(207-215)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662868
Khanchouche FSbabou SSmaoui HZiad A(2024)Nash Equilibria in Two-Resource Congestion Games with Player-Specific Payoff FunctionsGames10.3390/g1502000715:2(7)Online publication date: 26-Feb-2024
https://doi.org/10.3390/g15020007
Giannakopoulos YKleinberg RSaban DBergemann D(2024)A Smoothed FPTAS for Equilibria in Congestion GamesProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673615(401-413)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3670865.3673615
Sun GHe LSun ZWu QLiang SLi JNiyato DLeung V(2024)Joint Task Offloading and Resource Allocation in Aerial-Terrestrial UAV Networks With Edge and Fog Computing for Post-Disaster RescueIEEE Transactions on Mobile Computing10.1109/TMC.2024.335088623:9(8582-8600)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1109/TMC.2024.3350886
Hao BMichini C(2024)The price of Anarchy in series-parallel network congestion gamesMathematical Programming: Series A and B10.1007/s10107-022-01803-w203:1-2(499-529)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s10107-022-01803-w
Fokkema WHoeksma RUetz M(2024)Price of Anarchy for Graphic Matroid Congestion GamesAlgorithmic Game Theory10.1007/978-3-031-71033-9_21(371-388)Online publication date: 3-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71033-9_21
Hao BMichini C(2024)Price of Anarchy in Paving Matroid Congestion GamesAlgorithmic Game Theory10.1007/978-3-031-71033-9_20(353-370)Online publication date: 31-Aug-2024
https://doi.org/10.1007/978-3-031-71033-9_20
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents