Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games

• 成果类型: Article
• 署名作者: Hellerstein, Lisa; Lidbetter, Thomas; Pirutinsky, Daniel
• 署名单位: New York University; New York University Tandon School of Engineering; Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1853
• 发表日期: 2019
• 页码: 731-743
• 关键词: algorithms

摘要

We present efficient algorithms for computing optimal or approximately optimal strategies in a zero-sum game for which player I has n pure strategies and player II has an arbitrary number of pure strategies. We assume that for any given mixed strategy of player I, a best response, or approximate best response, of player II can be found by an oracle-in-time polynomial in n. We then show how our algorithms may be applied to several search games with applications to security and counterterrorism. We evaluate our main algorithm experimentally on a prototypical search game. Our results show that it performs well compared with existing well-known algorithms for solving zero-sum games that can also be used to solve search games given a best-response oracle.