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

Congestion games with failures

Published: 05 June 2005 Publication History

Abstract

We introduce a new class of games, congestion games with failures (CGFs), which extends the class of congestion games to allow for facility failures. In a basic CGF (BCGF) agents share a common set of facilities (service providers), where each service provider (SP) may fail with some known probability. For reliability reasons, an agent may choose a subset of the SPs in order to try and perform his task. The cost of an agent for utilizing any SP is a function of the total number of agents using this SP. A main feature of this setting is that the cost for an agent for successful completion of his task is the minimum of the costs of his successful attempts. We show that although BCGFs do not admit a potential function, and thus are not isomorphic to classic congestion games, they always possess a pure-strategy Nash equilibrium. We also show that the SPs' congestion experienced in different Nash equilibria is (almost) unique. For the subclass of symmetric BCGFs we give a characterization of best and worst Nash equilibria. We extend the basic model by making task submission costly and define a model for taxed CGFs (TCGFs). We prove the existence of a pure-strategy Nash equilibrium for quasi-symmetric TCGFs, and present an efficient algorithm for constructing such Nash equilibrium in symmetric TCGFs.

References

[1]
I. Ashlagi. The value of correlation in strategic form games. Technion - IIT, M.Sc. Thesis, 2004.
[2]
J. Correa, A. Schulz, and N. S. Moses. Computational complexity, fairness, and the price of anarchy of the maximum latency problem. MIT Sloan School of Management, Working Paper 4447-03, November 2003.
[3]
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.
[4]
N. Linial. Game-theoretic aspects of computing. In Handbook of Game Theory, volume 2, Elsevier Science B.V., 1994.
[5]
I. Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, 13:111--124, 1996.
[6]
I. Milchtaich. Congestion models of competition. American Naturalist, 147(5):760--783, 1996.
[7]
D. Monderer and L. Shapley. Potential games. Games and Economic Behavior, 14:124--143, 1996.
[8]
A. Orda, R. Rom, and N. Shimkin. Competitive routing in multi-user communication networks. IEEE/ACM Transactions on Networking, 1:510--521, 1993.
[9]
R. Porter, A. Ronen, Y. Shoham, and M. Tennenholtz. Mechanism design with execution uncertainty. In UAI-02, 2002.
[10]
T. Quint and M. Shubik. A model of migration. Cowles Foundation Discussion Papers, Yale University, (1088), 1994.
[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. Bounding the inefficiency of equilibria in nonatomic congestion games. Games and Economic Behavior, to appear.
[13]
T. Roughgarden and E. Tardos. How bad is selfish routing. Journal of the ACM, 49(2):236--259, 2002.

Cited By

View all
  • (2024)Making a Nash Equilibrium Resilient to CoalitionsProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673552(213-238)Online publication date: 8-Jul-2024
  • (2024)Nash equilibrium, dynamics and control of congestion games with resource failuresNonlinear Dynamics10.1007/s11071-024-09885-1112:18(16587-16599)Online publication date: 6-Jul-2024
  • (2023)Pure Nash equilibria in a generalization of congestion games allowing resource failuresTheoretical Computer Science10.1016/j.tcs.2023.113933963(113933)Online publication date: Jun-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
EC '05: Proceedings of the 6th ACM conference on Electronic commerce
June 2005
302 pages
ISBN:1595930493
DOI:10.1145/1064009
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: 05 June 2005

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. congestion games
  2. equilibrium
  3. failures
  4. pure-strategy nash

Qualifiers

  • Article

Conference

EC05
Sponsor:
EC05: Sixth ACM Conference on Electronic Commerce 2005
June 5 - 8, 2005
BC, Vancouver, Canada

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)5
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Making a Nash Equilibrium Resilient to CoalitionsProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673552(213-238)Online publication date: 8-Jul-2024
  • (2024)Nash equilibrium, dynamics and control of congestion games with resource failuresNonlinear Dynamics10.1007/s11071-024-09885-1112:18(16587-16599)Online publication date: 6-Jul-2024
  • (2023)Pure Nash equilibria in a generalization of congestion games allowing resource failuresTheoretical Computer Science10.1016/j.tcs.2023.113933963(113933)Online publication date: Jun-2023
  • (2022)On congestion games with player-specific costs and resource failuresAutomatica10.1016/j.automatica.2022.110367142(110367)Online publication date: Aug-2022
  • (2021)Pure Nash Equilibria in a Generalization of Congestion Games Allowing Resource FailuresAlgorithmic Game Theory10.1007/978-3-030-85947-3_13(186-201)Online publication date: 14-Sep-2021
  • (2019)Service Chain Composition with Failures in NFV Systems: A Game-Theoretic PerspectiveICC 2019 - 2019 IEEE International Conference on Communications (ICC)10.1109/ICC.2019.8761159(1-6)Online publication date: May-2019
  • (2018)Multiagent Reinforcement Learning Methods to Resolve Demand Capacity Balance ProblemsProceedings of the 10th Hellenic Conference on Artificial Intelligence10.1145/3200947.3201010(1-9)Online publication date: 9-Jul-2018
  • (2018)Multiagent Reinforcement Learning Methods for Resolving Demand - Capacity Imbalances2018 IEEE/AIAA 37th Digital Avionics Systems Conference (DASC)10.1109/DASC.2018.8569346(1-10)Online publication date: Sep-2018
  • (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
  • (2013)Confidence Intervals for the Shapley–Shubik Power Index in Markovian GamesDynamic Games and Applications10.1007/s13235-013-0079-64:1(10-31)Online publication date: 29-Mar-2013
  • Show More Cited By

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