Leadership in Singleton Congestion Games

Leadership in Singleton Congestion Games

Alberto Marchesi, Stefano Coniglio, Nicola Gatti

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 447-453. https://doi.org/10.24963/ijcai.2018/62

We study Stackelberg games where the underlying structure is a congestion game. We recall that, while leadership in 2-player games has been widely investigated, only few results are known when the number of players is three or more. The intractability of finding a Stackelberg equilibrium (SE) in normal-form and polymatrix games is among them. In this paper, we focus on congestion games in which each player can choose a single resource (a.k.a. singleton congestion games) and a player acts as leader. We show that, without further assumptions, finding an SE when the followers break ties in favor of the leader is not in Poly-APX, unless P = NP. Instead, under the assumption that every player has access to the same resources and that the cost functions are monotonic, we show that an SE can be computed efficiently when the followers break ties either in favor or against the leader.
Keywords:
Agent-based and Multi-agent Systems: Noncooperative Games
Agent-based and Multi-agent Systems: Algorithmic Game Theory