Show simple item record

Congestion Games with Capacitated Resources

dc.contributor.authorGourvès, Laurent
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.contributor.authorMoretti, Stefano
HAL ID: 739814
ORCID: 0000-0003-3627-3257
dc.contributor.authorKim Thang, Nguyen
dc.date.accessioned2013-09-06T08:41:22Z
dc.date.available2013-09-06T08:41:22Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11630
dc.language.isoenen
dc.subjectPolynomial algorithmsen
dc.subjectpure Nash equilibriumen
dc.subjectcongestion gamesen
dc.subject.ddc003en
dc.titleCongestion Games with Capacitated Resourcesen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.en
dc.identifier.citationpages204-215en
dc.relation.ispartofseriestitleLecture Notes in Computer Scienceen
dc.relation.ispartofseriesnumber7615en
dc.relation.ispartoftitleAlgorithmic Game Theory 5th International Symposium, SAGT 2012, Barcelona, Spain, October 22-23, 2012. Proceedingsen
dc.relation.ispartofeditorSerna, Maria
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2012
dc.relation.ispartofpages263en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-33996-7en
dc.identifier.urlsitehttp://hal.archives-ouvertes.fr/hal-00752265
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-33995-0en
dc.relation.conftitle5th International Symposium on Algorithmic Game Theory, SAGT 2012en
dc.relation.confdate2012-10
dc.relation.confcityBarceloneen
dc.relation.confcountryEspagneen
dc.relation.forthcomingnonen
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-642-33996-7_18en


Files in this item

Thumbnail
Name:
Sagt_congcap.pdf
Size:
154.4Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record