Pessimistic Leader-Follower Equilibria with Multiple Followers

Pessimistic Leader-Follower Equilibria with Multiple Followers

Stefano Coniglio, Nicola Gatti, Alberto Marchesi

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 171-177. https://doi.org/10.24963/ijcai.2017/25

The problem of computing the strategy to commit to has been widely investigated in the scientific literature for the case where a single-follower is present. In the multi-follower setting though, results are only sporadic. In this paper, we address the multi-follower case for normal-form games, assuming that, after observing the leader’s commitment, the followers play pure strategies and reach a Nash equilibrium. We focus on the pessimistic case where, among many equilibria, one minimizing the leader’s utility is chosen (the opposite case is computationally trivial). We show that the problem is NP-hard even with only two followers, and propose an exact exponential-time algorithm which, for any number of followers, either finds an equilibrium when the game admits a finite one or, if not, an α-approximation of the supremum of the leader’ utility, for any α > 0.
Keywords:
Agent-based and Multi-agent Systems: Economic paradigms, auctions and market-based systems
Agent-based and Multi-agent Systems: Noncooperative Games