Existence and Complexity of Approximate Equilibria in Weighted Congestion Games

George Christodoulou (), Martin Gairing (), Yiannis Giannakopoulos (), Diogo Poças () and Clara Waldmann ()
Additional contact information
George Christodoulou: School of Informatics, Aristotle University of Thessaloniki, 541 24 Thessaloniki, Greece
Martin Gairing: Department of Computer Science, University of Liverpool, Liverpool L69 3BX, United Kingdom
Yiannis Giannakopoulos: Department of Data Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany
Diogo Poças: Laboratório de Sistemas de Grande Escala, Fundação para a Ciência e Tecnologia, 1749-016 Lisboa, Portugal
Clara Waldmann: Operations Research Group, Technical University of Munich, 80333 Munich, Germany

Mathematics of Operations Research, 2023, vol. 48, issue 1, 583-602

Abstract: We study the existence of approximate pure Nash equilibria ( α -PNE) in weighted atomic congestion games with polynomial cost functions of maximum degree d . Previously, it was known that d -PNE always exist, whereas nonexistence was established only for small constants, namely, for 1.153-PNE. We improve significantly upon this gap, proving that such games in general do not have Θ ˜ ( d ) -PNE, which provides the first superconstant lower bound. Furthermore, we provide a black-box gap-introducing method of combining such nonexistence results with a specific circuit gadget, in order to derive NP-completeness of the decision version of the problem. In particular, by deploying this technique, we are able to show that deciding whether a weighted congestion game has an O ˜ ( d ) -PNE is NP-complete. Previous hardness results were known only for the special case of exact equilibria and arbitrary cost functions. The circuit gadget is of independent interest, and it allows us to also prove hardness for a variety of problems related to the complexity of PNE in congestion games. For example, we demonstrate that the question of existence of α -PNE, in which a certain set of players plays a specific strategy profile, is NP-hard for any α < 3 d / 2 , even for unweighted congestion games. Finally, we study the existence of approximate equilibria in weighted congestion games with general (nondecreasing) costs, as a function of the number of players n . We show that n -PNE always exists, matched by an almost tight nonexistence bound of Θ ˜ ( n ) , which we can again transform into an NP-completeness proof for the decision problem.

Keywords: Primary: 91A14; secondary: 91A68; 68Q17; atomic congestion games; weighted congestion games; existence of equilibria; pure Nash equilibria; approximate equilibria; hardness of equilibria (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1272 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:1:p:583-602

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().