IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v231y2013i3p667-689.html
   My bibliography  Save this article

Static search games played over graphs and general metric spaces

Author

Listed:
  • Oléron Evans, Thomas P.
  • Bishop, Steven R.

Abstract

We define a general game which forms a basis for modelling situations of static search and concealment over regions with spatial structure. The game involves two players, the searching player and the concealing player, and is played over a metric space. Each player simultaneously chooses to deploy at a point in the space; the searching player receiving a payoff of 1 if his opponent lies within a predetermined radius r of his position, the concealing player receiving a payoff of 1 otherwise. The concepts of dominance and equivalence of strategies are examined in the context of this game, before focusing on the more specific case of the game played over a graph. Methods are presented to simplify the analysis of such games, both by means of the iterated elimination of dominated strategies and through consideration of automorphisms of the graph. Lower and upper bounds on the value of the game are presented and optimal mixed strategies are calculated for games played over a particular family of graphs.

Suggested Citation

  • Oléron Evans, Thomas P. & Bishop, Steven R., 2013. "Static search games played over graphs and general metric spaces," European Journal of Operational Research, Elsevier, vol. 231(3), pages 667-689.
    • Handle: RePEc:eee:ejores:v:231:y:2013:i:3:p:667-689
    DOI: 10.1016/j.ejor.2013.06.024
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221713005122
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2013.06.024?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Alpern, Steven & Morton, Alec & Papadaki, Katerina, 2011. "Patrolling games," LSE Research Online Documents on Economics 32210, London School of Economics and Political Science, LSE Library.
    2. Kjell Hausken, 2011. "Protecting complex infrastructures against multiple strategic attackers," International Journal of Systems Science, Taylor & Francis Journals, vol. 42(1), pages 11-29.
    3. Martin Dufwenberg & Mark Stegeman, 2002. "Existence and Uniqueness of Maximal Reductions Under Iterated Strict Dominance," Econometrica, Econometric Society, vol. 70(5), pages 2007-2023, September.
    4. Steve Alpern & Vic Baston, 2005. "Rendezvous on a Planar Lattice," Operations Research, INFORMS, vol. 53(6), pages 996-1006, December.
    5. Steve Alpern & Shmuel Gal, 2002. "Searching for an Agent Who May OR May Not Want to be Found," Operations Research, INFORMS, vol. 50(2), pages 311-323, April.
    6. K. Kikuta & W. H. Ruckle, 1997. "Accumulation Games, Part 1: Noisy Search," Journal of Optimization Theory and Applications, Springer, vol. 94(2), pages 395-408, August.
    7. Rafael Hortala-Vallve & Aniol Llorente-Saguer, 2012. "Pure strategy Nash equilibria in non-zero sum colonel Blotto games," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(2), pages 331-343, May.
    8. Hohzaki, Ryusuke & Iida, Koji, 2000. "A search game when a search path is given," European Journal of Operational Research, Elsevier, vol. 124(1), pages 114-124, July.
    9. Powell, Robert, 2009. "Sequential, nonzero-sum "Blotto": Allocating defensive resources prior to attack," Games and Economic Behavior, Elsevier, vol. 67(2), pages 611-615, November.
    10. Kikuta, Kensaku & Ruckle, William H., 2010. "Two point one sided rendezvous," European Journal of Operational Research, Elsevier, vol. 207(1), pages 78-82, November.
    11. Hausken, Kjell, 2010. "Defense and attack of complex and dependent systems," Reliability Engineering and System Safety, Elsevier, vol. 95(1), pages 29-42.
    12. Zoroa, Noemi & Zoroa, Procopio & Jose Fernandez-Saez, M., 1999. "A generalization of Ruckle's results for an ambush game," European Journal of Operational Research, Elsevier, vol. 119(2), pages 353-364, December.
    13. Kensaku Kikuta & William H. Ruckle, 1994. "Initial point search on weighted trees," Naval Research Logistics (NRL), John Wiley & Sons, vol. 41(6), pages 821-831, October.
    14. Brian Roberson, 2006. "The Colonel Blotto game," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 29(1), pages 1-24, September.
    15. Lyn C. Thomas & Alan R. Washburn, 1991. "Dynamic Search Games," Operations Research, INFORMS, vol. 39(3), pages 415-422, June.
    16. Steve Alpern & Vic Baston & Shmuel Gal, 2008. "Network search games with immobile hider, without a designated searcher starting point," International Journal of Game Theory, Springer;Game Theory Society, vol. 37(2), pages 281-302, June.
    17. Steve Alpern, 2002. "Rendezvous Search: A Personal Perspective," Operations Research, INFORMS, vol. 50(5), pages 772-795, October.
    18. Garnaev, A Yu, 1992. "A Remark on the Princess and Monster Search Game," International Journal of Game Theory, Springer;Game Theory Society, vol. 20(3), pages 269-276.
    19. Powell, Robert, 2007. "Defending against Terrorist Attacks with Limited Resources," American Political Science Review, Cambridge University Press, vol. 101(3), pages 527-541, August.
    20. Reijnierse, J H & Potters, J A M, 1993. "Search Games with Immobile Hider," International Journal of Game Theory, Springer;Game Theory Society, vol. 21(4), pages 385-394.
    21. Kikuta, Kensaku & Ruckle, William H., 2007. "Rendezvous search on a star graph with examination costs," European Journal of Operational Research, Elsevier, vol. 181(1), pages 298-304, August.
    22. W. H. Ruckle & K. Kikuta, 2000. "Continuous Accumulation Games in Continuous Regions," Journal of Optimization Theory and Applications, Springer, vol. 106(3), pages 581-601, September.
    23. Steve Alpern & Anatole Beck, 2000. "Pure Strategy Asymmetric Rendezvous on the Line with an Unknown Initial Distance," Operations Research, INFORMS, vol. 48(3), pages 498-501, June.
    24. Zoroa, Noemi & Zoroa, Procopio & Jose Fernandez-Saez, M., 2003. "Raid games across a set with cyclic order," European Journal of Operational Research, Elsevier, vol. 145(3), pages 684-692, March.
    25. Zoroa, N. & Fernández-Sáez, M.J. & Zoroa, P., 2012. "Patrolling a perimeter," European Journal of Operational Research, Elsevier, vol. 222(3), pages 571-582.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Garrec, Tristan, 2019. "Continuous patrolling and hiding games," European Journal of Operational Research, Elsevier, vol. 277(1), pages 42-51.
    2. Alpern, Steve & Fokkink, Robbert & Simanjuntak, Martin, 2016. "Optimal search and ambush for a hider who can escape the search region," European Journal of Operational Research, Elsevier, vol. 251(3), pages 707-714.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Duffy, John & Matros, Alexander, 2017. "Stochastic asymmetric Blotto games: An experimental study," Journal of Economic Behavior & Organization, Elsevier, vol. 139(C), pages 88-105.
    2. Lidbetter, Thomas, 2017. "On the approximation ratio of the Random Chinese Postman Tour for network search," European Journal of Operational Research, Elsevier, vol. 263(3), pages 782-788.
    3. Garrec, Tristan, 2019. "Continuous patrolling and hiding games," European Journal of Operational Research, Elsevier, vol. 277(1), pages 42-51.
    4. Leone, Pierre & Buwaya, Julia & Alpern, Steve, 2022. "Search-and-rescue rendezvous," European Journal of Operational Research, Elsevier, vol. 297(2), pages 579-591.
    5. Shan, Xiaojun & Zhuang, Jun, 2013. "Hybrid defensive resource allocations in the face of partially strategic attackers in a sequential defender–attacker game," European Journal of Operational Research, Elsevier, vol. 228(1), pages 262-272.
    6. Steve Alpern & Thomas Lidbetter, 2013. "Mining Coal or Finding Terrorists: The Expanding Search Paradigm," Operations Research, INFORMS, vol. 61(2), pages 265-279, April.
    7. Steve Alpern, 2011. "Find-and-Fetch Search on a Tree," Operations Research, INFORMS, vol. 59(5), pages 1258-1268, October.
    8. John Duffy & Alexander Matros, 2013. "Stochastic Asymmetric Blotto Games: Theory and Experimental Evidence," Working Paper 509, Department of Economics, University of Pittsburgh, revised Nov 2013.
    9. Dan J. Kovenock & Brian Roberson, 2015. "The Optimal Defense of Network Connectivity," CESifo Working Paper Series 5653, CESifo.
    10. Antoine Pietri, 2017. "Les modèles de « rivalité coercitive » dans l’analyse économique des conflits," Revue d'économie politique, Dalloz, vol. 127(3), pages 307-352.
    11. Dan Kovenock & Brian Roberson, 2018. "The Optimal Defense Of Networks Of Targets," Economic Inquiry, Western Economic Association International, vol. 56(4), pages 2195-2211, October.
    12. Dan Kovenock & Brian Roberson & Roman M. Sheremeta, 2019. "The attack and defense of weakest-link networks," Public Choice, Springer, vol. 179(3), pages 175-194, June.
    13. Pierre Leone & Steve Alpern, 2018. "Rendezvous search with markers that can be dropped at chosen times," Naval Research Logistics (NRL), John Wiley & Sons, vol. 65(6-7), pages 449-461, September.
    14. Chen, Shun & Zhao, Xudong & Chen, Zhilong & Hou, Benwei & Wu, Yipeng, 2022. "A game-theoretic method to optimize allocation of defensive resource to protect urban water treatment plants against physical attacks," International Journal of Critical Infrastructure Protection, Elsevier, vol. 36(C).
    15. Nakao, Keisuke, 2017. "Denial vs. Punishment: Strategies Shape War, but War Itself Affects Strategies," MPRA Paper 81418, University Library of Munich, Germany.
    16. Baykal-Gürsoy, Melike & Duan, Zhe & Poor, H. Vincent & Garnaev, Andrey, 2014. "Infrastructure security games," European Journal of Operational Research, Elsevier, vol. 239(2), pages 469-478.
    17. Zhang, Chi & Ramirez-Marquez, José Emmanuel & Wang, Jianhui, 2015. "Critical infrastructure protection using secrecy – A discrete simultaneous game," European Journal of Operational Research, Elsevier, vol. 242(1), pages 212-221.
    18. Subhasish Chowdhury & Dan Kovenock & Roman Sheremeta, 2013. "An experimental investigation of Colonel Blotto games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 52(3), pages 833-861, April.
    19. Laan, Corine M. & van der Mijden, Tom & Barros, Ana Isabel & Boucherie, Richard J. & Monsuur, Herman, 2017. "An interdiction game on a queueing network with multiple intruders," European Journal of Operational Research, Elsevier, vol. 260(3), pages 1069-1080.
    20. B. Golany & N. Goldberg & U. Rothblum, 2015. "Allocating multiple defensive resources in a zero-sum game setting," Annals of Operations Research, Springer, vol. 225(1), pages 91-109, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:231:y:2013:i:3:p:667-689. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.