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.

(2017). Pessimistic Leader-Follower Equilibria with Multiple Followers . Retrieved from http://hdl.handle.net/10446/229378

Pessimistic Leader-Follower Equilibria with Multiple Followers

Coniglio, Stefano;Gatti, Nicola
2017

Abstract

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.
Coniglio, Stefano; Marchesi, Alberto; Gatti, Nicola
File allegato/i alla scheda:
File Dimensione del file Formato  
2017-IJCAI.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 186.37 kB
Formato Adobe PDF
186.37 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/229378
Citazioni
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 3
social impact