|
Martine Labbé is a full professor at the Université Libre de Bruxelles (ULB), see http://homepages.ulb.ac.be/%7Emlabbe/. She is Professor of Operations Research at the Computer Science Department of the Faculty of Sciences. From 2007 to 2011, she was Dean of the Faculty of sciences. Her main research area is combinatorial optimization, including graph theory and integer programming problems and with a particular emphasis on location and network design problems. She is also specialized in bilevel programming and studies pricing problems and Stackelberg games. She served on the editorial boards of Discrete Optimization, Journal on combinatorial Optimization, Operations Research, Operations Research Letters and Transportation Science. She is now the Editor in Chief of the EURO Journal on Computational Optimization. She is the author or coauthor more than100 papers published in international journals. In 2007-2008, she was president of EURO, the Association of European Operational Research Societies. She was, in 2014 and 2015, Vice-Chair of the SIAM Activity Group on Optimization (SIAG/OPT).
|
Abstract
Stackelberg games and bilevel bilinear optimization problem
Stackelberg Games confront contenders with opposed objectives, each wanting to optimize their rewards. Decision-making parties involve a party with the capacity of committing to a given action or strategy, referred to as the leader, and a party responding to the leader's action, called the follower. The objective of the game is for the leader to commit to a reward-maximizing strategy anticipating that the follower will best respond.
Finding the optimal mixed strategy of the leader in a Stackelberg Game is NP-hard when the leader faces one out of several followers and polynomial when there exists a single follower. Additionally, games in which the strategies of the leader consist in covering a subset of at most K targets and the strategies of the followers consist in attacking some target are called Stackelberg Security Games and involve an exponential number of pure strategies for the leader.
A Stackelberg game can be modeled as a bilevel bilinear optimization problem which can be reformulated as a single level mixed integer nonlinear program (MINLP). We present different reformulations of this MINLP and compare their LP relaxations from both theoretical and computational points of view.
Stackelberg Games confront contenders with opposed objectives, each wanting to optimize their rewards. Decision-making parties involve a party with the capacity of committing to a given action or strategy, referred to as the leader, and a party responding to the leader's action, called the follower. The objective of the game is for the leader to commit to a reward-maximizing strategy anticipating that the follower will best respond.
Finding the optimal mixed strategy of the leader in a Stackelberg Game is NP-hard when the leader faces one out of several followers and polynomial when there exists a single follower. Additionally, games in which the strategies of the leader consist in covering a subset of at most K targets and the strategies of the followers consist in attacking some target are called Stackelberg Security Games and involve an exponential number of pure strategies for the leader.
A Stackelberg game can be modeled as a bilevel bilinear optimization problem which can be reformulated as a single level mixed integer nonlinear program (MINLP). We present different reformulations of this MINLP and compare their LP relaxations from both theoretical and computational points of view.
