@conference {1506502,
	title = {Optimal defender allocation for massive security games: A branch and price approach },
	booktitle = {AAMAS 2010 Workshop on Optimisation in Multi-Agent Systems (OptMas)},
	year = {2010},
	abstract = {Algorithms to solve security games, an important class of Stackelberg games, have seen successful real-world deployment by LAX
police and the Federal Air Marshal Service. These algorithms provide randomized schedules to optimally allocate limited security
resources for infrastructure protection. Unfortunately, these stateof-the-art algorithms fail to scale-up or to provide a correct solution for massive security games with arbitrary scheduling constraints. This paper provides ASPEN, a branch-and-price algorithm to overcome this limitation based on two key contributions:
(i) A column-generation approach that exploits an innovative compact network flow representation, avoiding a combinatorial explosion of schedule allocations; (ii) A branch-and-bound approach
with novel upper-bound generation via a fast algorithm for solving under-constrained security games. ASPEN is the first known
method for efficiently solving real-world-sized security games with
arbitrary schedules. This work contributes to a very new area of
work that applies techniques used in large-scale optimization to
game-theoretic problems{\textemdash}an exciting new avenue with the potential to greatly expand the reach of game theory.},
	author = {Jain, Manish and Erim Kardes and Kiekintveld, Christopher and Ordonez, Fernando and Tambe, Milind}
}
