Optimization Online


Novel formulations for general and security Stackelberg games

Carlos Casorrán(ccasorra***at***ulb.ac.be)
Bernard Fortz(bernard.fortz***at***ulb.ac.be)
Martine Labbé(mlabbe***at***ulb.ac.be)
Fernando Ordóńez(fordon***at***dii.uchile.cl)

Abstract: In this paper we analyze general Stackelberg games (SGs) and Stackelberg security games (SSGs). SGs are hierarchical adversarial games where players select actions or strategies to optimize their payoffs in a sequential manner. SSGs are a type of SGs that arise in security applications, where the strategies of the player that acts first consist in protecting subsets of targets and the strategies of the followers consist in attacking one of the targets. We review existing mixed integer optimization formulations in both the general and the security setting and present new formulations for both settings. We compare the SG formulations and the SSG formulations both from a theoretical and a computational point of view. Our theoretical results show that the new formulations provide tighter linear relaxations. Our computational experiments show that the new formulations give better solution times.

Keywords: Operations Research, Game Theory, Mixed Integer Linear Programming, Bilevel Optimization

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Working Paper, Université Libre de Bruxelles, August 2016.

Download: [PDF]

Entry Submitted: 10/26/2016
Entry Accepted: 10/26/2016
Entry Last Modified: 10/26/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society