Title: Existence and Complexity of Equilibria in Congestion Games
Speaker: Diogo Poças (LASIGE, DI-FCUL)
Date: October, 27, 14h30
Where: zoom

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-approximate equilibria always exist, while 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)-approximate PNE, which provides the first super-constant 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, deploying this technique we are able to show that deciding whether a weighted congestion game has an Õ(√d)-PNE is NP-complete. Previous hardness results were known only for the special case of exact equilibria and arbitrary cost functions. We also 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 exist, matched by an almost tight nonexistence bound of Θ̃(n) which we can again transform into an NP-completeness proof for the decision problem.

Bio: Diogo Poças, LASIGE integrated member, did his MSc in Mathematics and Applications at Instituto Superior Técnico, and his PhD in Mathematics at McMaster University. Before coming to FCUL, he worked as a postdoctoral researcher in the Operations Research Group at TU Munich. Diogo’s research interests are on theoretical computer science, at the intersection of mathematics and general computer science. Recently, he has been working in algorithmic game theory topics such as the existence and computational complexity of finding Nash equilibria in games.

Personal webpage: here