We study the problem of computing Stackelberg equilibria in Stackelberg games whose underlying structure is a congestion game, focusing on singleton congestion games, i.e., on congestion games where each player can choose a single resource, and assuming that one of them acts as leader while the other ones act as followers. We provide a comprehensive picture of the computational complexity of finding equilibria in these games, investigating different forms of commitment (pure-strategy and mixed-strategy) and followers' tie-breaking rules (optimistic and pessimistic). We identify two features of such games, namely, identical/different action spaces and monotonic/generic cost functions, by which we provide a complete characterization of the cases in which the equilibrium-finding problem is either easy or hard. In particular, we show that, in the case where the action spaces are different, the cost the leader incurs in an optimistic or pessimistic Stackelberg equilibrium cannot be approximated in polynomial time up to any polynomial factor in the size of the game unless , independently of the cost functions being monotonic or generic. This result holds even when the commitment is restricted to pure strategies. For general mixed-strategy commitments, we show that a similar result also holds when the players have generic cost functions, even if their action spaces are identical. Furthermore, we prove that the case with identical action spaces and monotonic cost functions is easy. We also improve the efficiency of a polynomial-time algorithm available in the literature for the computation of a socially optimal Nash equilibrium in non-Stackelberg singleton congestion games with identical action spaces and generic cost functions, and we extend it to the computation of a Stackelberg equilibrium for the case where the leader is restricted to playing pure strategies. For the cases in which the problem of finding an equilibrium is hard, we show how, in the optimistic setting where the followers break ties in favor of the leader, the problem can be formulated via mixed-integer linear programming techniques. We also provide an experimental evaluation of our algorithms both on random instances and on instances generated from our inapproximability reductions.

(2019). Leadership in singleton congestion games: What is hard and what is easy [journal article - articolo]. In ARTIFICIAL INTELLIGENCE. Retrieved from http://hdl.handle.net/10446/229309

Leadership in singleton congestion games: What is hard and what is easy

Castiglioni, Matteo;Gatti, Nicola;Coniglio, Stefano
2019

Abstract

We study the problem of computing Stackelberg equilibria in Stackelberg games whose underlying structure is a congestion game, focusing on singleton congestion games, i.e., on congestion games where each player can choose a single resource, and assuming that one of them acts as leader while the other ones act as followers. We provide a comprehensive picture of the computational complexity of finding equilibria in these games, investigating different forms of commitment (pure-strategy and mixed-strategy) and followers' tie-breaking rules (optimistic and pessimistic). We identify two features of such games, namely, identical/different action spaces and monotonic/generic cost functions, by which we provide a complete characterization of the cases in which the equilibrium-finding problem is either easy or hard. In particular, we show that, in the case where the action spaces are different, the cost the leader incurs in an optimistic or pessimistic Stackelberg equilibrium cannot be approximated in polynomial time up to any polynomial factor in the size of the game unless , independently of the cost functions being monotonic or generic. This result holds even when the commitment is restricted to pure strategies. For general mixed-strategy commitments, we show that a similar result also holds when the players have generic cost functions, even if their action spaces are identical. Furthermore, we prove that the case with identical action spaces and monotonic cost functions is easy. We also improve the efficiency of a polynomial-time algorithm available in the literature for the computation of a socially optimal Nash equilibrium in non-Stackelberg singleton congestion games with identical action spaces and generic cost functions, and we extend it to the computation of a Stackelberg equilibrium for the case where the leader is restricted to playing pure strategies. For the cases in which the problem of finding an equilibrium is hard, we show how, in the optimistic setting where the followers break ties in favor of the leader, the problem can be formulated via mixed-integer linear programming techniques. We also provide an experimental evaluation of our algorithms both on random instances and on instances generated from our inapproximability reductions.
articolo
Castiglioni, Matteo; Marchesi, Alberto; Gatti, Nicola; Coniglio, Stefano
(2019). Leadership in singleton congestion games: What is hard and what is easy [journal article - articolo]. In ARTIFICIAL INTELLIGENCE. Retrieved from http://hdl.handle.net/10446/229309
File allegato/i alla scheda:
File Dimensione del file Formato  
2019-AIJ.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 1.21 MB
Formato Adobe PDF
1.21 MB 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/229309
Citazioni
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 2
social impact