2018 Optimization Days

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

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

TAP M. Labbé

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

Location: Plenaries - Amphithéâtre Banque Nationale

Chaired by Gilles Caporossi

1 Presentation

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.