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

Lisa Hellerstein (), Thomas Lidbetter () and Daniel Pirutinsky ()
Additional contact information
Lisa Hellerstein: Department of Computer Science and Engineering, New York University Tandon School of Engineering, New York, New York 11201
Thomas Lidbetter: Department of Management Science and Information Systems, Rutgers Business School, Newark, New Jersey 07102
Daniel Pirutinsky: Department of Management Science and Information Systems, Rutgers Business School, Newark, New Jersey 07102

Operations Research, 2019, vol. 67, issue 3, 731-743

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.

Keywords: games/group decisions; search/surveillance; tree algorithms; networks/graphs; learning (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1853 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:67:y:2019:i:3:p:731-743

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().