LASIGE’s researcher Diogo Poças published joint work with George Christodoulou (Aristotle University of Thessaloniki), Martin Gairing (University of Liverpool), Yiannis Giannakopoulos (Friedrich-Alexander-Universität Erlangen-Nürnberg), and Clara Waldmann (Technical University of Munich) in the INFORMS Journal Mathematics of Operations Research (Scimago Q1). The paper, entitled “Existence and Complexity of Approximate Equilibria in Weighted Congestion Games”, studies the existence of approximate Nash equilibrium in weighted atomic congestion games with polynomial cost functions of maximum degree d. The paper proves that such games in general do not have alpha(d)-PNE, where alpha(d) grows like the square root of d.. Furthermore, the paper provides 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.

The research lies in the important research direction of understanding the complexity of computing equilibria. Congestion games constitute the standard framework to study settings where selfish players compete over common resources and are widely used in practice. The main result improves significantly upon the previous known lower bound, namely a small constant. In addition, the paper is a valuable addition to the literature on local search problems, as congestion games (with best-response dynamics) are one of the fundamental settings in this line of research.

The article is available here.