Xu, Haifeng, Tran-Thanh, Long and Jennings, Nick (2016) Playing repeated security games with no prior knowledge. In: 15th International Conference on Autonomous Agents & Multiagent Systems (AAMAS 2016), Singapore , 9-13 May 2016. Published in: AAMAS '16: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems pp. 104-112. ISBN 9781450342391. doi:10.5555/2936924.2936944

Preview

PDF WRAP-Playing-repeated-security-games-prior-Tran-2016.pdf - Accepted Version - Requires a PDF viewer. Download (932Kb) | Preview

Request Changes to record.

Abstract

This paper investigates repeated security games with unknown (to the defender) game payoffs and attacker behaviors. As existing work assumes prior knowledge about either the game payoffs or the attacker's behaviors, they are not suitable for tackling our problem. Given this, we propose the first efficient defender strategy, based on an adversarial online learning framework, that can provably achieve good performance guarantees without any prior knowledge. In particular, we prove that our algorithm can achieve low performance loss against the best fixed strategy on hindsight (i.e., having full knowledge of the attacker's moves). In addition, we prove that our algorithm can achieve an efficient competitive ratio against the optimal adaptive defender strategy. We also show that for zero-sum security games, our algorithm achieves efficient results in approximating a number of solution concepts, such as algorithmic equilibria and the minimax value. Finally, our extensive numerical results demonstrate that, without having any prior information, our algorithm still achieves good performance, compared to state-of-the-art algorithms from the literature on security games, such as SUQR, which require significant amount of prior knowledge.

Item Type:	Conference Item (Paper)
Alternative Title:
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH):	Game theory , Computer security, Computer algorithms
Journal or Publication Title:	AAMAS '16: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems
Publisher:	ACM Press
ISBN:	9781450342391
Official Date:	May 2016
Dates:	Date Event May 2016 Published 1 January 2016 Accepted
Page Range:	pp. 104-112
DOI:	10.5555/2936924.2936944
Status:	Peer Reviewed
Publication Status:	Published
Publisher Statement:	"© ACM, 2016. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in 15th International Conference on Autonomous Agents & Multiagent Systems (AAMAS 2016) http://doi.acm.org/10.5555/2936924.2936944
Access rights to Published version:	Restricted or Subscription Access
RIOXX Funder/Project Grant:	Project/Grant ID RIOXX Funder Name Funder ID CCF- 1350900 National Science Foundation http://dx.doi.org/10.13039/501100008982 EP/I011587/ UK Research and Innovation http://dx.doi.org/10.13039/100014013 MURI W911NF-11-1-0332 U.S. Department of Defense http://dx.doi.org/10.13039/100000005
Conference Paper Type:	Paper
Title of Event:	15th International Conference on Autonomous Agents & Multiagent Systems (AAMAS 2016)
Type of Event:	Conference
Location of Event:	Singapore
Date(s) of Event:	9-13 May 2016
Related URLs:	Other Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads