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

Abstract

How to Choose Between Exponentially Many Strategies In “Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games,” L. Hellerstein, T. Lidbetter, and D. Pirutinsky consider zero-sum games between a minimizer and a maximizer, where the number of pure strategies of the minimizer is exponential in the number of pure strategies of the maximizer. Such games are frequent in the search-games literature. Solving them with standard algorithms typically takes exponential time. The authors show how to compute (approximate) solutions in polynomial time, provided that there is a polynomial time (approximate) algorithm solving the best-response problem: given a mixed (randomized) strategy of the maximizer, what is a best response of the minimizer? The paper presents both a learning approach using weight updates and an approach of solely theoretical interest based on the ellipsoid algorithm. The learning approach performs well experimentally compared with approaches in the literature. The results are applied to obtain new algorithms for solving specific search games.