824. Branch-and-price and novel constraints in Stackelberg Security Games
Invited abstract in session TB-4: Topics in Competition and Games, cluster Location, Network Design, and Routing.
Tuesday, 10:30-12:00Room: CE-209
Authors (first author is the speaker)
| 1. | Pamela Alejandra Bustamante Faúndez
|
| Department of Industrial and Systems Engineering, Pontificia Universidad Católica de Chile | |
| 2. | Victor Bucarey
|
| Institute of Engineering Sciences, Universidad de O'Higgins | |
| 3. | Martine Labbé
|
| computer Science, Université Libre de Bruxelles | |
| 4. | Vladimir Marianov
|
| Electrical Engineering, Pontificia Universidad Catolica de Chile | |
| 5. | Fernando Ordonez
|
| Universidad de Chile |
Abstract
Stackelberg security games are used as decision-support tools in security settings. The algorithms addressing these games generate optimal randomized schedules for distributing security resources. Unfortunately, finding optimal strategies for Bayesian Stackelberg games and Stackelberg security games is generally NP-Hard.
Developing efficient methodologies to tackle large instances is essential to face this. We propose a branch-and-price scheme with novel and tighter constraints to find a Strong Stackelberg Equilibrium for Stackelberg games.
We also provide a general algorithm generating upper and lower bounds for Stackelberg Security Games. We compare different methods and parameters for branch-and-price in these games, and we test and compare our proposed method to prior decomposition methods based on different integer programming formulations of Stackelberg games.
Keywords
- Game Theory
- Mixed Integer Programming
- Bilevel programming
Status: accepted
Back to the list of papers