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.

Be sure to check-out Margarida, Sriram, and Felipe websites! Browse the pre-print on arXiv

Resources
  • gitHub the C++ implementation for this paper
  • gitHub repository with the instances for our computational tests
Image

Gabriele Dragotto

Hello, nothing special to say here except this is my personal website

Back to Overview