Title: Methods for finding leader--follower equilibria with multiple followers,
Abstract: The concept of leader--follower (or Stackelberg) equilibrium plays a central
role in a number of real--world applications of game theory. While the case
with a single follower has been thoroughly investigated, results with multiple
followers are only sporadic and the problem of designing and evaluating
computationally tractable equilibrium-finding algorithms is still largely open.
In this work, we focus on the fundamental case where multiple followers play a
Nash equilibrium once the leader has committed to a strategy---as we
illustrate, the corresponding equilibrium finding problem can be easily shown
to be $\mathcal{FNP}$--hard and not in Poly--$\mathcal{APX}$ unless
$\mathcal{P} = \mathcal{NP}$ and therefore it is one among the hardest problems
to solve and approximate. We propose nonconvex mathematical programming
formulations and global optimization methods to find both exact and approximate
equilibria, as well as a heuristic black box algorithm. All the methods and
formulations that we introduce are thoroughly evaluated computationally.