Designing the Game to Play: Optimizing Payoff Structure in Security Games
Abstract
We study Stackelberg Security Games where the defender, in addition to allocating defensive resources to protect targets from the attacker, can strategically manipulate the attacker’s payoff under budget constraints in weighted L^p-norm form regarding the amount of change. For the case of weighted L^1-norm constraint, we present (i) a mixed integer linear program-based algorithm with approximation guarantee; (ii) a branch-and-bound based algorithm with improved efficiency achieved by effective pruning; (iii) a polynomial time approximation scheme for a special but practical class of problems. In addition, we show that problems under budget constraints in L^0 and weighted L^\infty-norm form can be solved in polynomial time.
Cite
Text
Shi et al. "Designing the Game to Play: Optimizing Payoff Structure in Security Games." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/71Markdown
[Shi et al. "Designing the Game to Play: Optimizing Payoff Structure in Security Games." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/shi2018ijcai-designing/) doi:10.24963/IJCAI.2018/71BibTeX
@inproceedings{shi2018ijcai-designing,
title = {{Designing the Game to Play: Optimizing Payoff Structure in Security Games}},
author = {Shi, Zheyuan Ryan and Tang, Ziye and Tran-Thanh, Long and Singh, Rohit and Fang, Fei},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {512-518},
doi = {10.24963/IJCAI.2018/71},
url = {https://mlanthology.org/ijcai/2018/shi2018ijcai-designing/}
}