Publications -> Conference Papers

Coalitional Security Games


Authors: Q. Guo, B. An, Y. Vorobeychik, L. Tran-Thanh, J. Gan, and C. Miao
Title: Coalitional Security Games
Abstract: Game theoretic models of security, and associated computational methods, have emerged as critical components of security posture across a broad array of domains, including airport security and coast guard. These approaches consider terrorists as motivated but independent entities. There is, however, increasing evidence that attackers, be it terrorists or cyber attackers, communicate extensively and form coalitions that can dramatically increase their ability to achieve malicious goals. To date, such cooperative decision making among attackers has been ignored in the security games literature. To address the issue of cooperation among attackers, we introduce a novel coalitional security game (CSG) model. A CSG consists of a set of attackers connected by a (communication or trust) network who can form coalitions as connected subgraphs of this network so as to attack a collection of targets. A defender in a CSG can delete a set of edges, incurring a cost for deleting each edge, with the goal of optimally limiting the attackers' ability to form effective coalitions (in terms of successfully attacking high value targets). We first show that a CSG is, in general, hard to approximate. Nevertheless, we develop a novel branch and price algorithm, leveraging a combination of column generation, relaxation, greedy approximation, and stabilization methods to enable scalable high-quality approximations of CSG solutions on realistic problem instances.
Keywords: Game theory; Security; Optimization; Stackelberg games
Conference Name: 15th International Conference on Autonomous Agents and Multi-agent Systems (AAMAS'16)
Location: Singapore, Singapore
Publisher: IFAAMAS
Year: 2016
Accepted PDF File: Coalitional_Security_Games_accepted.pdf
Permanent Link: http://www.ifaamas.org/Proceedings/aamas2016/pdfs/p159.pdf
Reference: Q. Guo, B. An, Y. Vorobeychik, L. Tran-Thanh, J. Gan, and C. Miao, “Coalitional security games,” in Proceedings of the 15th International Conference on Autonomous Agents and Multi-agent Systems (AAMAS’16). IFAAMAS, May 2016, pp. 159–167.
bibtex: 
@inproceedings{LILY-c76, 
    author	= {Guo, Qingyu and An, Bo and Vorobeychik, Yevgeniy and Tran-Thanh, Long and Gan, Jiarui and Miao, Chunyan},
    title	= {Coalitional Security Games},  
    booktitle	= {Proceedings of the 15th International Conference on Autonomous Agents and Multi-agent Systems (AAMAS'16)}, 
    year		= {2016}, 
    month	= {May}, 
    pages	= {159-167}, 
    location	= {Singapore, Singapore},
    publisher	= {IFAAMAS},
 }