We analyze Nash games played among leaders of Stackelberg games (NASP), and prove it is \(\Sigma^p_2\)-hard to decide if the game has a mixed-strategy Nash equilibrium (MNE). We then provide a finite algorithm which computes exact MNEs for NASP when there is at least one, or returns a certificate if no MNE exists. We introduce an inner approximation hierarchy that increasingly grows the description of each Stackelberg leader feasible region. Furthermore, we extend the algorithmic framework to specifically retrieve a pure-strategy Nash Equilibrium if one exists - and present a combinatorial algorithm for this latter task. Finally, we provide computational tests on a range of NASPs instances inspired by international energy trades.

Be sure to check-out Margarida, Sriram, and Felipe websites!

  • pre-print is available on arXiv.
  • gitHub the C++ implementation for this paper
  • gitHub repository with the instances for our computational tests

Gabriele Dragotto

Back to Overview