Journées de l'optimisation 2018

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

Horaire Auteurs Mon horaire

TAP M. Labbé

8 mai 2018 09h00 – 10h00

Salle: Pléniers - Amphithéâtre Banque Nationale

Présidée par Gilles Caporossi

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.