Existence and Complexity of Approximate Equilibria in Weighted Congestion Games

Christodoulou, George, Gairing, Martin, Giannakopoulos, Yiannis, Pocas, Diogo and Waldmann, Clara (2022) Existence and Complexity of Approximate Equilibria in Weighted Congestion Games. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 2020-7-8 - 2020-7-11, Saarbruecken.

Text hardness_equilibria_ICALP.pdf - Author Accepted Manuscript Download (614kB) | Preview

Abstract

<jats:p> 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 [Formula: see text]-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 [Formula: see text]-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 [Formula: see text], 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 [Formula: see text], which we can again transform into an NP-completeness proof for the decision problem. </jats:p><jats:p> Funding: Supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research (BMBF). D. Poças was also funded by FCT via LASIGE Research Unit, ref. UIDB/00408/2020 and ref. UIDP/00408/2020. </jats:p>

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	atomic congestion games, weighted congestion games, existence of equilibria, pure Nash equilibria, approximate equilibria, hardness of equilibria
Depositing User:	Symplectic Admin
Date Deposited:	26 May 2020 09:13
Last Modified:	22 Mar 2023 14:42
DOI:	10.1287/moor.2022.1272
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3088425