• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Congestion Games with Capacitated Resources

Gourvès, Laurent; Monnot, Jérôme; Moretti, Stefano; Kim Thang, Nguyen (2015), Congestion Games with Capacitated Resources, Theory of Computing Systems, 57, 3, p. 598-616. 10.1007/s00224-014-9541-0

View/Open
tocs_congcap.pdf (221.6Kb)
Type
Article accepté pour publication ou publié
Date
2015
Journal name
Theory of Computing Systems
Volume
57
Number
3
Publisher
Springer
Pages
598-616
Publication identifier
10.1007/s00224-014-9541-0
Metadata
Show full item record
Author(s)
Gourvès, Laurent
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Moretti, Stefano cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Kim Thang, Nguyen
Abstract (EN)
The players of a congestion game interact by allocating bundles of resources from a common pool. This type of games leads to well studied models for analyzing strategic situations, including networks operated by uncoordinated selfish users. Congestion games constitute a subclass of potential games, meaning that a pure Nash equilibrium emerges from a myopic process where the players iteratively react by switching to a strategy that diminishes their individual cost. With the aim of covering more applications, for instance in communication networks, we extend congestion games to the setting where every resource is endowed with a capacity which possibly limits its number of users. From the negative side, we show that a pure Nash equilibrium is not guaranteed to exist in any case and we prove that deciding whether a game possesses a pure Nash equilibrium is NP-complete. Our positive results state that congestion games with capacities are potential games in the well studied singleton case. Polynomial algorithms that compute these equilibria are also provided.
Subjects / Keywords
Pure Nash equilibrium; Congestion games; Algorithms; Potential function

Related items

Showing items related by title and author.

  • Thumbnail
    Congestion Games with Capacitated Resources 
    Gourvès, Laurent; Monnot, Jérôme; Moretti, Stefano; Kim Thang, Nguyen (2012) Communication / Conférence
  • Thumbnail
    Strategy-Proof Mechanisms for Facility Location Games with Many Facilities 
    Spanjaard, Olivier; Pascual, Fanny; Thang, Nguyen Kim; Gourvès, Laurent; Escoffier, Bruno (2011) Communication / Conférence
  • Thumbnail
    On the performance of congestion games for optimum satisfiability problems 
    Monnot, Jérôme; Giannakos, A.; Gourvès, Laurent; Paschos, Vangelis (2007) Communication / Conférence
  • Thumbnail
    On the performance of congestion games for optimum satisfiability problems 
    Giannakos, Aristotelis; Gourvès, Laurent; Monnot, Jérôme; Paschos, Vangelis (2007) Document de travail / Working paper
  • Thumbnail
    Cost allocation protocols for network formation on connection situations 
    Escoffier, Bruno; Monnot, Jérôme; Gourvès, Laurent; Moretti, Stefano (2012) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo