skip to main content
10.5555/1402821.1402936acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

Asynchronous congestion games

Published: 12 May 2008 Publication History

Abstract

We introduce a new class of games, asynchronous congestion games (ACGs). In an ACG, each player has a task that can be carried out by any element of a set of resources, and each resource executes its assigned tasks in a random order. Each player's aim is to minimize his expected cost which is the sum of two terms - the sum of the fixed costs over the set of his utilized resources and the expected cost of his task execution. The cost of a player's task execution is determined by the earliest time his task is completed, and thus it might be beneficial for him to assign his task to several resources. We prove the existence of pure strategy Nash equilibria in ACGs. Moreover, we present a polynomial time algorithm for finding such an equilibrium in a given ACG.

References

[1]
E. Angel, E. Bampis, and F. Pascual. Truthful algorithms for scheduling selfish tasks on parallel machines. In WINE-05, pages 698--707, 2005.
[2]
V. Auletta, R. Prisco, P. Penna, and G. Persiano. Determinisitc truthful approximation mechanisms for scheduling related machines. In STACS-04, pages 608--619, 2004.
[3]
T. Carroll and D. Grosu. Selfish multi-user task scheduling. In ISPDC-06, pages 99--106, 2006.
[4]
G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games. In STOC-05, pages 67--73, 2005.
[5]
A. Fabrikant, C. Papadimitriou, and K. Talwar. The complexity of pure Nash equilibria. In STOC-04, pages 604--612, 2004.
[6]
D. Grosu and T. Carroll. A strategyproof mechanism for scheduling divisible loads in distributed systems. In ISPDC-05, pages 83--90, 2005.
[7]
E. Koutsoupias. Selfish task allocation. Bulletin of EATCS, 81:79--88, 2003.
[8]
I. Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, 13:111--124, 1996.
[9]
D. Monderer. Solution-based congestion games. Advances in Mathematical Economics, 8:397--407, 2006.
[10]
D. Monderer and L. Shapley. Potential games. Games and Economic Behavior, 14:124--143, 1996.
[11]
D. Monderer and M. Tennenholtz. Distributed games. Games and Economic Behavior, 28:181--188, 1999.
[12]
N. Nisan and A. Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1/2): 166--196, 2001.
[13]
M. Penn, M. Polukarov, and M. Tennenholtz. Congestion games with load-dependent failures: identical resources. In EC-07, pages 210--217, 2007.
[14]
R. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65--67, 1973.

Cited By

View all
  • (2009)Random Order Congestion GamesMathematics of Operations Research10.1287/moor.1090.039434:3(706-725)Online publication date: 1-Aug-2009
  • (2009)Games with Congestion-Averse UtilitiesProceedings of the 2nd International Symposium on Algorithmic Game Theory10.1007/978-3-642-04645-2_20(220-232)Online publication date: 13-Oct-2009

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 3
May 2008
503 pages
ISBN:9780981738123

Sponsors

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 12 May 2008

Check for updates

Author Tags

  1. algorithms
  2. asynchronous distributed systems
  3. congestion games
  4. pure-strategy Nash equilibrium

Qualifiers

  • Research-article

Conference

AAMAS08
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

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
  • (2009)Random Order Congestion GamesMathematics of Operations Research10.1287/moor.1090.039434:3(706-725)Online publication date: 1-Aug-2009
  • (2009)Games with Congestion-Averse UtilitiesProceedings of the 2nd International Symposium on Algorithmic Game Theory10.1007/978-3-642-04645-2_20(220-232)Online publication date: 13-Oct-2009

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