The paper "Computational Complexity of Decision Problems about Nash Equilibria in Win-Lose Multi-Player Games" coauthored by Marios Mavronicolas, Kristoffer Arnsfelt Hansen and Vittorio Bilò was awarded the SAGT 2023 Best Paper Award in the 16th International Symposium on Algorithmic Game Theory (SAGT).

Abstract: We revisit the computational complexity of decision problems about the existence of Nash equilibria satisfying certain natural properties in multi-player games. Such problems have generally been shown to be complete for the complexity class Existential-R, which captures the complexity of the decision problem for the Existential Theory of the Reals. For most of these problems, we show that their complexity remains unchanged even when restricted to win-lose games: games where all utilities are 0 or 1.

The 16th International Symposium on Algorithmic Game Theory (SAGT) will take place at Royal Holloway University of London from 4th-7th September 2023.

The purpose of SAGT is to bring together researchers from Computer Science, Economics, Mathematics, Operations Research, Psychology, Physics, and Biology to present and discuss original research at the intersection of Algorithms and Game Theory.