We investigate the problem of computing a Leader-Follower Nash Equilibrium (LFNE) in a normal-form game. Given a game with a leader and two or more followers, the LFNE is Stackelberg Equilibrium in which, given the leader's commitment to a strategy, the followers play a Nash Equilibrium that either maximizes (optimistic case) or minimizes (pessimistic case) the leader's utility.
We focus on the case where both the leader and the followers are entitled to mixed strategies. We show that the problem is NP-hard and not in APX unless P=NP, and that the same holds for deciding whether, in an equilibrium, one of the leader's actions will be played with a strictly positive probability. We also illustrate that, in the general case, pessimistic LFNEs may not be finite.
We propose different compact (and exact) nonconvex (mixed-integer) nonlinear programming formulations for the optimistic case, a faster implicit-enumeration algorithm which is suitable when the leader is only entitled to pure strategies, and a black box (heuristic) algorithm for the both the optimistic and pessimistic cases. Computational experiments are reported and illustrated.
We conclude by sketching an exact (up to finite precision) branch-and-bound algorithm for the pessimistic case based either on Farkas's lemma for the case where the followers are restricted to pure strategies, or on a result by Balas on the convex hull of a disjunction of polyhedra for the general case in mixed strategies.
This is joint work with Nicola Gatti and Nicola Basilico.
When: March 9, 2016 at 10.30
Where: Aula Fausto Saleri - 6th floor Dipartimento di Matematica, Building 14, Politecnico di Milano