We analyze Nash games played among leaders of Stackelberg games (NASP). We show it is $Sigma^p_2$-hard to decide if the game has a mixed-strategy Nash equilibrium (MNE), even when there are only two leaders and each leader has one follower. We provide a finite time algorithm with a running time bounded by $O(2^{2^n})$ which computes MNEs for NASP when it exists and returns infeasibility if no MNE exists. We also provide two ways to improve the algorithm which involves constructing a series of inner approximations (alternatively, outer approximations) to the leaders' feasible region that will provably obtain the required MNE. Finally, we test our algorithms on a range of NASPs arising out of a game in the energy market, where countries act as Stackelberg leaders who play a Nash game, and the domestic producers act as the followers.

When Nash Meets Stackelberg / Carvalho, Margarida; Dragotto, Gabriele; Feijoo, Felipe; Lodi, Andrea; Sankaranarayanan, Sriram. - ELETTRONICO. - (2019).

When Nash Meets Stackelberg

Gabriele Dragotto;
2019

Abstract

We analyze Nash games played among leaders of Stackelberg games (NASP). We show it is $Sigma^p_2$-hard to decide if the game has a mixed-strategy Nash equilibrium (MNE), even when there are only two leaders and each leader has one follower. We provide a finite time algorithm with a running time bounded by $O(2^{2^n})$ which computes MNEs for NASP when it exists and returns infeasibility if no MNE exists. We also provide two ways to improve the algorithm which involves constructing a series of inner approximations (alternatively, outer approximations) to the leaders' feasible region that will provably obtain the required MNE. Finally, we test our algorithms on a range of NASPs arising out of a game in the energy market, where countries act as Stackelberg leaders who play a Nash game, and the domestic producers act as the followers.
2019
When Nash Meets Stackelberg / Carvalho, Margarida; Dragotto, Gabriele; Feijoo, Felipe; Lodi, Andrea; Sankaranarayanan, Sriram. - ELETTRONICO. - (2019).
File in questo prodotto:
File Dimensione Formato  
1910.06452.pdf

non disponibili

Descrizione: Article
Tipologia: 1. Preprint / submitted version [pre- review]
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 719.21 kB
Formato Adobe PDF
719.21 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2858249