Title: Computing Pessimistic Leader-Follower Equilibria with Multiple Followers
Speaker: Dr Stefano Coniglio
Affiliation: Dept. of Mathematical Sciences, Southampton University
Location: Room 217 Huxley Building
Time: 14:00 – 15:00
Abstract. We investigate the problem of computing a Leader-Follower equilibrium in Stackelberg games where two or more followers react to the strategy chosen by the (single) leader by playing a Nash Equilibrium. We consider two natural cases, the optimistic one where the followers select a Nash Equilibrium maximizing the leader’s utility and the pessimistic one where they select an equilibrium minimizing the leader’s utility. We first illustrate that, in both cases, 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 would be played with strictly positive probability is NP-hard. We then focus on the pessimistic case with followers restricted to pure strategies, showing that this problem too is NP-hard and not in Poly-APX unless P=NP. After casting it as a pessimistic bilevel programming problem, we propose an exact implicit enumeration algorithm for its solution. In particular, our algorithm is capable of computing the maximum of the problem and, for the general case where the former only admits a supremum, an alpha-approximate strategy for any nonnegative alpha. Experimental results are presented and illustrated, showing the viability of the proposed approach.
This is joint work with Nicola Gatti and Alberto Marchesi.
About the speaker. Dr Stefano Coniglio is a Lecturer in Operational Research within Mathematical Sciences at the University of Southampton. Dr Stefano Coniglio joined the University of Southampton as Lecturer in Operational Research within Mathematical Sciences in February 2016. Prior to that, he served as Research Associate at the RWTH Aachen University, Germany, and as Postdoctoral Researcher at Politecnico di Milano, Italy, where he received his Ph.D. in Information Technology in 2011. His research focuses on exact methods for the solution of mathematical programming and combinatorial optimization problems. Recently, he has been most active in bilevel programming, robust optimization, and methodological aspects of cutting plane generation, with applications to algorithmic game theory, optimization in telecommunication networks, energy production planning, and data mining.