Skip to main navigation Skip to main content
The University of Southampton
CORMSIS Centre for Operational Research, Management Sciences and Information Systems

CORMSIS seminar: Exact single level and bilevel programming approaches to the computation of Leader-Follower Nash Equilibria in games with many followers Event

Time:
16:00 - 17:00
Date:
26 May 2016
Venue:
Room 3041 Building 2, Southampton Business School

For more information regarding this event, please email Dr Yuan Huang at yuan.huang@soton.ac.uk .

Event details

Abstract: We investigate the problem of computing a Leader-Follower Nash Equilibrium. Given a normal-form game with a 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 and Nicola Gatti.

Speaker information

Dr Stefano Coniglio,Mathematics School, University of Southampton,Bio: 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 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.

Privacy Settings