Exact single level and bilevel programming approaches to the computation of Leader-Follower Nash Equilibria in games with many followers
Dr. Stefano Coniglio, University of Southampton
Sala conferenze IMATI-CNR, Pavia - Tuesday, April 4, 2017 h.15:00
Abstract. We investigate the problem of computing a Leader-Follower Nash Equilibrium. Given a normal-form game with a single leader and two or more followers, a strategy profile is a Leader-Follower Nash Equilibrium if i) given the leader's strategy, the followers' strategies yield a Nash Equilibrium in the corresponding subgame and ii) the leader's strategy is such that his utility is maximized. To cope with the presence of multiple Nash Equilibria in the followers' subgame, we consider two natural (extreme) cases: the optimistic case, where the followers select a Nash Equilibrium maximizing the leader's utility, and the pessimistic case, where a Nash Equilibrium minimizing the leader's utility is chosen.
We first illustrate that computing a Leader-Follower Nash Equilibrium is NP-hard and not in Poly-APX unless P=NP and that even deciding whether one of the leader's actions will be played with a strictly positive probability in an equilibrium is NP-hard. We also show that, in the general case, pessimistic equilibria may not be finite.
After showing that the optimistic problem can be cast as a single level mathematical program (whereas the pessimistic one is intrinsically bilevel), we propose some (mixed-integer) nonconvex formulations for the optimistic case, which we then evaluate computationally. We conclude by presenting an exact (up to finite precision) branch-and-bound algorithm for the pessimistic case based on disjunctive programming, suitable for the case where the followers are restricted to pure strategies, and sketch its extension to the general case of mixed strategies.
This is joint work with Nicola Basilico, Nicola Gatti, and Alberto Marchesi.
Università degli Studi di Pavia -
Via Ferrata, 5 - 27100 Pavia
Tel +39.0382.985600 - Fax +39.0382.985602