Abstract
The problem of computing the strategy to commit to has been widely investigated in the scientific literature for the case where a single follower
is present. In the multi-follower setting though, results are only sporadic. In this paper, we address
the multi-follower case for normal-form games, assuming that, after observing the leader’s commitment, the followers play pure strategies and reach a
Nash equilibrium. We focus on the pessimistic case
where, among many equilibria, one minimizing the
leader’s utility is chosen (the opposite case is computationally trivial). We show that the problem is
NP-hard even with only two followers, and propose an exact exponential-time algorithm which,
for any number of followers, finds either an equilibrium when it exists (the leader’s utility admitting
a maximum) or, if not, an ?-approximation of the
supremum, for any ? > 0