Automated Generation of Counterterrorism Policies Using Multiexpert Input
Abstract
The use of game theory to model conflict has been studied by several researchers, spearheaded by Schelling. Most of these efforts assume a single payoff matrix that captures players’ utilities under different assumptions about what the players will do. Our experience in counterterrorism applications is that experts disagree on these payoffs. We leverage Shapley’s notion of vector equilibria, which formulates games where there are multiple payoff matrices, but note that they are very hard to compute in practice. To effectively enumerate large numbers of equilibria with payoffs provided by multiple experts, we propose a novel combination of vector payoffs and well-supported ϵ-approximate equilibria. We develop bounds related to computation of these equilibria for some special cases and give a quasipolynomial time approximation scheme (QPTAS) for the general case when the number of players is small (which is true in many real-world applications). Leveraging this QPTAS, we give efficient algorithms to find such equilibria and experimental results showing that they work well on simulated data.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jul 10, 2015
- Source ID
- 10.1145/2716328
Entities
People
- Anshul Sawant
- John P. Dickerson
- Mohammad T. Hajiaghayi
- V. S. Subrahmanian
Organizations
- American Society for Engineering Education
- Army Research Office
- Carnegie Mellon University
- Defense Advanced Research Projects Agency
- National Science Foundation
- Office of Naval Research
- University of Maryland