When Nash Meets Stackelberg

Motivated by international energy trade between countries with profit-maximizing domestic producers, we analyze Nash games played among Stackelberg games leaders ($NASP$). In particular, we focus on $NASPs$ where each leader program is a linear bilevel with quadratic convex followers, and we assume the standard optimistic version of such bilevels. 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.