2018 Optimization Days

HEC Montréal, Québec, Canada, 7 — 9 May 2018

Schedule Authors My Schedule

TAP M. Labbé

May 8, 2018 09:00 AM – 10:00 AM

Location: Plenaries - Amphithéâtre Banque Nationale

Chaired by Gilles Caporossi

1 Presentation

  • 09:00 AM - 10:00 AM

    Stackelberg games and bilevel bilinear optimization problem

    • Martine Labbé, presenter, 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.