Motivated by international energy trade between countries with profit-maximizing domestic producers, we analyze Nash games played among Stackelberg games leaders (NASP). We prove it is both \(\Sigma^p_2\)-hard to decide if the game has a pure-strategy (PNE) or a mixed-strategy Nash equilibrium (MNE). We provide a finite algorithm that computes exact MNEs for NASPs when there is at least one or returns a certificate if no MNE exists. To enhance computational speed, we introduce an inner approximation hierarchy that increasingly grows the description of each Stackelberg leader feasible region. Furthermore, we extend the algorithmic framework to retrieve a PNE if one exists specifically. Finally, we provide computational tests on a range of NASPs instances inspired by international energy trades.
Be sure to check-out Margarida, Sriram websites!
- pre-print is available on arXiv.
- EPECSolve on GitHub: the C++ implementation for this paper
- EPECInstances on GitHub repository with the instances for our computational tests
- Aussois Pitch: at the Aussois COW 2020
- MIP2020: a poster presentation at MIP 2020. A video of this talk is available here
- AIROYoung Workshop 2021: a talk at AIROYoung 2021 with extra material and renewed humor. Also, winner of one of the conference's awards.