1 présentation

• 
  09h00 - 10h00

  Stackelberg games and bilevel bilinear optimization problem

  • Martine Labbé, prés., GOM, Université Libre de Bruxelles and INRIA

  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 them from both theoretical and computational points of view.