2017/04/09 by Lisa Hellerstein, Hellerstein, Lisa, Thomas Lidbetter +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Advanced Bandit Algorithms Research #Artificial Intelligence in Games #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Optimization and Control (math.OC) #Sports Analytics and Performance
paper · pdf · doi:10.48550/arxiv.1704.02657
openalex publication_date 2017/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present efficient algorithms for computing optimal or approximately\noptimal strategies in a zero-sum game for which Player I has n pure strategies\nand Player II has an arbitrary number of pure strategies. We assume that for\nany given mixed strategy of Player I, a best response or "approximate" best\nresponse of Player II can be found by an oracle in time polynomial in n. We\nthen show how our algorithms may be applied to several search games with\napplications to security and counter-terrorism. We evaluate our main algorithm\nexperimentally on a prototypical search game. Our results show it performs well\ncompared to an existing, well-known algorithm for solving zero-sum games that\ncan also be used to solve search games, given a best response oracle.\n