On bilevel programming and the computation of Leader-Follower Nash Equilibria in games with many followers
Stefano Coniglio
Department of Mathematical Sciences, University of Southampton, UK
Politecnico di Milano - Dipartimento di Matematica, Saleri Room (6th floor)
March 9th, 2016
10.30 am - 11.30 am
Contact:
Nicola Gatti
Research Line:
Artificial intelligence and robotics
Department of Mathematical Sciences, University of Southampton, UK
Politecnico di Milano - Dipartimento di Matematica, Saleri Room (6th floor)
March 9th, 2016
10.30 am - 11.30 am
Contact:
Nicola Gatti
Research Line:
Artificial intelligence and robotics
Sommario
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.
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.