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

References

• Alpern S (2017) Hide-and-seek games on a network, using combinatorial search paths. Oper. Res. 65(5):1207–1214.Link, Google Scholar
• Alpern S, Gal S (2003) The Theory of Search Games and Rendezvous. Price CC, ed. Kluwer International Series in Operations Research and Management Science, vol. 55 (Kluwer, Boston).Google Scholar
• Alpern S, Lidbetter T (2013a) Searching a variable speed network. Math. Oper. Res. 39(3):697–711.Link, Google Scholar
• Alpern S, Lidbetter T (2013b) Mining coal or finding terrorists: The expanding search paradigm. Oper. Res. 61(2):265–279.Link, Google Scholar
• Alpern S, Lidbetter T (2015) Optimal trade-off between speed and acuity when searching for a small object. Oper. Res. 63(1):122–133.Link, Google Scholar
• Angelopoulos S, Dürr C, Lidbetter T (2019) The expanding search ratio of a graph. Discrete Appl. Math. 260(May):51–65.Google Scholar
• Arora S, Hazan E, Kale S (2012) The multiplicative weights update method: A meta-algorithm and applications. Theory Comput. 8(1):121–164.Crossref, Google Scholar
• Baston V, Kikuta K (2013) Search games on networks with travelling and search costs and with arbitrary searcher starting points. Networks 62(1):72–79.Crossref, Google Scholar
• Baston V, Kikuta K (2015) Search games on a network with travelling and search costs. Internat. J. Game Theory 44(2):347–365.Crossref, Google Scholar
• Brown GW (1949) Some notes on computation of game solutions. RAND-P-78, RAND Corp., Santa Monica, CA.Google Scholar
• Carr R, Vempala S (2002) Randomized metarounding. Random Structures Algorithms 20(3):343–352.Crossref, Google Scholar
• Chekuri C, Motwani R (1999) Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discrete Appl. Math. 98(1):29–38.Crossref, Google Scholar
• Condon A, Deshpande A, Hellerstein L, Wu N (2009) Algorithms for distributional and adversarial pipelined filter ordering problems. ACM Trans. Algorithms (TALG) 5(2):24–34.Google Scholar
• Daskalakis C (2013) On the complexity of approximating a Nash equilibrium. ACM Trans. Algorithms (TALG) 9(3):1.Crossref, Google Scholar
• Daskalakis C, Pan Q (2014) A counter-example to Karlin’s strong conjecture for fictitious play. Proc. 2014 IEEE 55th Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 11–20.Crossref, Google Scholar
• Dürr C (2016) Data on the NP-hardness of the expanding search problem provided via personal communication with the authors, February 11.Google Scholar
• Feldman M, Kortsarz K, Nutov Z (2012) Improved approximation algorithms for directed Steiner forest. J. Comput. System Sci. 78(1):279–292.Crossref, Google Scholar
• Freund Y, Schapire RE (1999) Adaptive game playing using multiplicative weights. Games Econom. Behav. 29(1):79–103.Crossref, Google Scholar
• Friggstad Z, Swarmy C (2012) Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing. Proc. 46th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 744–753.Google Scholar
• Fokkink R, Kikuta K, Ramsey D (2016) The search value of a set. Ann. Oper. Res. 256(1):63–73.Crossref, Google Scholar
• Fokkink R, Lidbetter T, Végh L (2018) On submodular search and machine scheduling. Working paper, Delft University of Technology, Delft, Netherlands.Google Scholar
• Freund Y, Schapire R (1996) Game theory, on-line prediction and boosting. Proc. 9th Annual Conf. Comput. Learn. Theory (Association for Computing Machinery, New York), 325–332.Crossref, Google Scholar
• Hohzaki R (2016) Search games: Literature and survey. J. Oper. Res. Soc. Japan 59(1):1–34.Crossref, Google Scholar
• Gal S (1979) Search games with mobile and immobile hider. SIAM J. Control Optim. 17(1):99–122.Crossref, Google Scholar
• Gal S (2000) On the optimality of a simple strategy for searching graphs. Internat. J. Game Theory 29(4):533–542.Crossref, Google Scholar
• Gal S (2011) Search games. Cochran J, ed. Wiley Encyclopedia of Operations Research and Management Science (Wiley, New York).Crossref, Google Scholar
• Gal S, Casas J (2014) Succession of hide–seek and pursuit–evasion at heterogenous locations. J. Roy. Soc. Interface 11(94):20140062.Crossref, Google Scholar
• Garg N, Könemann J (2007) Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput. 37(2):630–652.Crossref, Google Scholar
• Jansen K (2003) Approximate strong separation with application in fractional graph coloring and preemptive scheduling. Theoret. Comput. Sci. 302(1–3):239–256.Crossref, Google Scholar
• Lidbetter T (2013) Search games with multiple hidden objects, SIAM J. Control Optim. 51(4):3056–3074.Crossref, Google Scholar
• Lin KY, Singham DI (2015) Robust search policies against an intelligent evader. Technical report, Naval Postgraduate School, Monterey, CA.Google Scholar
• Lin KY, Singham DI (2016) Finding a hider by an unknown deadline. Oper. Res. Lett. 44(1):25–32.Crossref, Google Scholar
• Liu Z, Parthasarathy S, Ranganathan A, Yang H (2008) A generic flow algorithm for shared filter ordering problems. Proc. 27th ACM SIGMOD-SIGACT-SIGART Sympos. Principles Database Systems (Association for Computing Machinery, New York), 79–88.Crossref, Google Scholar
• Matula D (1964) A periodic optimal search. Amer. Math. Monthly 71(1):15–21.Crossref, Google Scholar
• McMahan HB, Gordon GJ, Blum A (2003) Planning in the presence of cost functions controlled by an adversary. Proc. 20th Internat. Conf. Machine Learn. (ICML-03) (Association for the Advancement of Artificial Intelligence, Palo Alto, CA), 536–543.Google Scholar
• Robinson J (1951) An iterative method of solving a game. Ann. Math. 54(2):296–301.Crossref, Google Scholar
• Schulz AS (1996) Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. Proc. 5th Conf. Integer Programming Combin. Optim. (Springer, Berlin), 301–315.Crossref, Google Scholar
• Sidney J (1975) Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs. Oper. Res. 23(2):283–298.Link, Google Scholar
• Smith WE (1956) Various optimizers for single-stage production. Naval Res. Logist. Quart. 3(1–2):59–66.Crossref, Google Scholar
• Vazirani VV (2013) Approximation Algorithms (Springer Science & Business Media, Berlin).Google Scholar
• Wilder B, Yadav A, Immorlica N, Rice E, Tambe M (2017) Uncharted but not uninfluenced: Influence maximization with an uncertain network. Proc. 16th Conf. Autonomous Agents MultiAgent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 1305–1313.Google Scholar