skip to main content
10.1145/1250910.1250941acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
Article

Congestion games with load-dependent failures: identical resources

Published: 11 June 2007 Publication History

Abstract

We define a new class of games, congestion games with load-dependent failures (CGLFs), which generalizes the well-known class of congestion games, by incorporating the issue of resource failures into congestion games. In a CGLF, agents share a common set of resources, where each resource has a cost and a probability of failure. Each agent chooses a subset of the resources for the execution of his task, in order to maximize his own utility. The utility of an agent is the difference between his benefit from successful task completion and the sum of the costs over the resources he uses. CGLFs possess two novel features. It is the first model to incorporate failures into congestion settings, which results in a strict generalization of congestion games. In addition, it is the first model to consider load-dependent failures in such framework, where the failure probability of each resource depends on the number of agents selecting this resource. Although, as we show, CGLFs do not admit a potential function, and in general do not have a pure strategy Nash equilibrium, our main theorem proves the existence of a pure strategy Nash equilibrium in every CGLF with identical resources and nondecreasing cost functions.

References

[1]
H. Ackermann, H. Röglin, and B. Vöcking. Pure nash equilibria in player-specific and weighted congestion games. In WINE-06, 2006.
[2]
G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games. In Proceedings of the 37th Annual ACM Symposium on Theory and Computing (STOC-05), 2005.
[3]
A. Fabrikant, C. Papadimitriou, and K. Talwar. The complexity of pure nash equilibria. In STOC-04, pages 604--612, 2004.
[4]
E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, pages 404--413, 1999.
[5]
K. Leyton-Brown and M. Tennenholtz. Local-effect games. In IJCAI-03, 2003.
[6]
I. Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, 13:111--124, 1996.
[7]
D. Monderer. Solution-based congestion games. Advances in Mathematical Economics, 8:397--407, 2006.
[8]
D. Monderer. Multipotential games. In IJCAI-07, 2007.
[9]
D. Monderer and L. Shapley. Potential games. Games and Economic Behavior, 14:124--143, 1996.
[10]
M. Penn, M. Polukarov, and M. Tennenholtz. Congestion games with failures. In Proceedings of the 6th ACM Conference on Electronic Commerce (EC-05), pages 259--268, 2005.
[11]
R. Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
[12]
T. Roughgarden and E. Tardos. How bad is selfish routing. Journal of the ACM, 49(2):2360--259, 2002.

Cited By

View all
  • (2017)Congestion Game With Agent and Resource FailuresIEEE Journal on Selected Areas in Communications10.1109/JSAC.2017.267235835:3(764-778)Online publication date: 1-Mar-2017
  • (2010)Stressed web environments as strategic gamesProceedings of the 5th international conference on Trustworthly global computing10.5555/1893701.1893717(189-204)Online publication date: 24-Feb-2010
  • (2010)Stressed Web Environments as Strategic Games: Risk Profiles and WeltanschauungTrustworthly Global Computing10.1007/978-3-642-15640-3_13(189-204)Online publication date: 2010
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
EC '07: Proceedings of the 8th ACM conference on Electronic commerce
June 2007
384 pages
ISBN:9781595936530
DOI:10.1145/1250910
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. congestion games
  2. load-dependent resource failures
  3. pure strategy Nash equilibrium

Qualifiers

  • Article

Conference

EC07
Sponsor:
EC07: ACM Conference on Electronic Commerce
June 11 - 15, 2007
California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25
The 25th ACM Conference on Economics and Computation
July 7 - 11, 2025
Stanford , CA , USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2017)Congestion Game With Agent and Resource FailuresIEEE Journal on Selected Areas in Communications10.1109/JSAC.2017.267235835:3(764-778)Online publication date: 1-Mar-2017
  • (2010)Stressed web environments as strategic gamesProceedings of the 5th international conference on Trustworthly global computing10.5555/1893701.1893717(189-204)Online publication date: 24-Feb-2010
  • (2010)Stressed Web Environments as Strategic Games: Risk Profiles and WeltanschauungTrustworthly Global Computing10.1007/978-3-642-15640-3_13(189-204)Online publication date: 2010
  • (2009)Congestion games with load-dependent failures: Identical resourcesGames and Economic Behavior10.1016/j.geb.2009.03.00467:1(156-173)Online publication date: Sep-2009
  • (2009)Asynchronous Congestion GamesGraph Theory, Computational Intelligence and Thought10.1007/978-3-642-02029-2_5(41-53)Online publication date: 27-Jul-2009
  • (2008)Asynchronous congestion gamesProceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 310.5555/1402821.1402936(1605-1608)Online publication date: 12-May-2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media