Abstract
We study the classical problem introduced by R. Isaacs and S. Gal of minimizing the time to find a hidden point H on a network Q moving from a known starting point. Rather than adopting the traditional continuous unit speed path paradigm, we use the dynamic “expanding search” paradigm recently introduced by the authors. Here the regions S(t) that have been searched by time t are increasing from the starting point and have total length t. Roughly speaking the search follows a sequence of arcs \(a_i\) such that each one starts at some point of an earlier one. This type of search is often carried out by real life search teams in the hunt for missing persons, escaped convicts, terrorists or lost airplanes. The paper which introduced this type of search solved the adversarial problem (where H is hidden to maximize the time to be found) for the cases where Q is a tree or is 2-arc-connected. This paper’s main contribution is to give two strategy classes which can be used on any network and have expected search times which are within a factor close to 1 of the value of the game (minimax search time). These strategies classes are respectively optimal for trees and 2-arc-connected networks. We also solve the game for circle-and-spike networks, which can be considered as the simplest class of networks for which a solution was previously unknown.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alpern, S. (2010). Search games on trees with asymmetric travel times. SIAM Journal on Control and Optimization, 48(8), 5547–5563.
Alpern, S. (2011a). Find-and-fetch search on a tree. Operations Research, 59(5), 1258–1268.
Alpern, S. (2011b). A new approach to Gal’s theory of search games on weakly Eulerian networks. Dynamic Games and Applications, 1(2), 209–219.
Alpern, S., & Gal, S. (2003). The theory of search games and rendezvous (p. 319)., Kluwer international series in operations research and management science Boston: Kluwer.
Alpern, S., & Lidbetter, T. (2013). Mining coal or finding terrorists: The expanding search paradigm. Operations Research, 61(2), 265–279.
Alpern, S., & Lidbetter, T. (2014). Searching a variable speed network. Mathematics of Operations Research, 39(3), 697–711.
Alpern, S., & Lidbetter, T. (2015). Optimal trade-off between speed and acuity when searching for a small object. Operations Research, 63(1), 122–133.
Alpern, S., Morton, A., & Papadaki, K. (2011). Patrolling games. Operations Research, 59(5), 1246–1257.
Anderson, E. J., & Aramendia, M. (1990). The search game on a network with immobile hider. Networks, 20(7), 817–844.
Angelopoulos, S. (2015). Connections between contract-scheduling and ray-searching problems. In Proceedings of the 24th international joint conference on artificial intelligence (IJCAI).
Baston, V., & Kikuta, K. (2015). Search games on a network with travelling and search costs. International Journal of Game Theory, 44(2), 347–365.
Chapman, M., Tyson, G., McBurney, P., Luck, M., & Parsons, S. (2014). Playing hide-and-seek: An abstract game for cyber security. In Proceedings of the 1st international workshop on agents and cybersecurity (p. 3). ACM.
Eckman, D. J., Maillart, L. M., & Schaefer, A. J. (2016). Optimal pinging frequencies in the search for an immobile beacon. IIE Transactions, 48(6), 489–500.
Fokkink, R., Kikuta, K., & Ramsey, D. (2016). The search value of a set. Annals of Operations Research, 256(1), 63–73.
Gal, S. (1979). Search games with mobile and immobile hider. SIAM Journal on Control and Optimization, 17(1), 99–122.
Gal, S. (2000). On the optimality of a simple strategy for searching graphs. International Journal of Game Theory, 29(4), 533–542.
Gal, S. (2005). Strategies for searching graphs. In M. Golumbic & I. Hartman (Eds.), Graph theory, combinatorics and algorithms (Vol. 34, pp. 189–214)., Operations research/computer science interfaces series New York: Springer.
Garnaev, A. (2000). Search games and other applications of game theory (Vol. 485)., Lecture notes in economics and mathematical systems New York: Springer.
Hohzaki, R. (2016). Search games: Literature and survey. Journal of the Operations Research Society of Japan, 59(1), 1–34.
Isaacs, R. (1965). Differential games. New York: Wiley.
Kolokoltsov, V. (2014). The evolutionary game of pressure (or interference), resistance and collaboration. arXiv preprint arXiv:1412.1269.
Lidbetter, T. (2013a). Search games with multiple hidden objects. SIAM Journal on Control and Optimization, 51(4), 3056–3074.
Lidbetter, T. (2013b). Search games for an immobile hider. In S. Alpern, et al. (Eds.), Search theory: A game theoretic perspective (pp. 17–27). New York: Springer.
Lin, K. Y., Atkinson, M. P., Chung, T. H., & Glazebrook, K. D. (2013). A graph patrol problem with random attack times. Operations Research, 61(3), 694–710.
Liu, D., Xiao, X., Li, H., & Wang, W. (2015). Historical evolution and benefit-cost explanation of periodical fluctuation in coal mine safety supervision: An evolutionary game analysis framework. European Journal of Operational Research, 243(3), 974–984.
Morice, S., Pincebourde, S., Darboux, F., Kaiser, W., & Casas, J. (2013). Predator-prey pursuit-evasion games in structurally complex environments. Integrative and Comparative Biology, 53(5), 767–779.
Pavlovic, L. (1993). Search game on an odd number of arcs with immobile hider. Yugoslav Journal of Operations Research, 3(1), 11–19.
Reijnierse, J. H., & Potter, J. A. M. (1993). Search games with immobile hider. International Journal of Game Theory, 21(4), 385–394.
Shechter, S. M., Ghassemi, F., Gocgun, Y., & Puterman, M. L. (2015). Technical note-trading off quick versus slow actions in optimal search. Operations Research, 63(2), 353–362.
Wenk, C. J. (2015). Control sequencing in a game of identity pursuit–evasion. SIAM Journal on Control and Optimization, 53(4), 1815–1841.
Zoroa, N., Fernández-Sáez, M. J., & Zoroa, P. (2013). Tools to manage search games on lattices. In S. Alpern, et al. (Eds.), Search theory: A game theoretic perspective (pp. 29–58). New York: Springer.
Acknowledgements
Steve Alpern wishes to acknowledge support from the Air Force Office of Scientific Research [Grant FA9550-14-1-0049].
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Alpern, S., Lidbetter, T. Approximate solutions for expanding search games on general networks. Ann Oper Res 275, 259–279 (2019). https://doi.org/10.1007/s10479-018-2966-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-018-2966-0