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

Weighted network search games with multiple hidden objects and multiple search teams

Author

Listed:
  • Yolmeh, Abdolmajid
  • Baykal-Gürsoy, Melike

Abstract

Most search game models assume that the hiding locations are identical and the players’ objective is to optimize the search time. However, there are some cases in which the players may differentiate the hiding locations from each other and the objective is to optimize a weighted search time. In addition, the search may involve multiple search teams. To address these, we introduce a new network search game with consideration given to the weights at different locations. A hider can hide multiple objects and there may be multiple search teams. For a special case of the problem, we prove that the game has a closed-form Nash equilibrium. For the general case, we develop an algorithm based on column and row generation. We show that the Searcher’s subproblem is NP-hard and propose a branch and price algorithm to solve it. We also present a polynomial time algorithm for the Hider’s subproblem. Numerical experiments demonstrate the efficiency of the proposed algorithms, and reveal insights into the properties of this game.

Suggested Citation

  • Yolmeh, Abdolmajid & Baykal-Gürsoy, Melike, 2021. "Weighted network search games with multiple hidden objects and multiple search teams," European Journal of Operational Research, Elsevier, vol. 289(1), pages 338-349.
  • Handle: RePEc:eee:ejores:v:289:y:2021:i:1:p:338-349
    DOI: 10.1016/j.ejor.2020.06.046
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722172030607X
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Steve Alpern & Thomas Lidbetter, 2013. "Mining Coal or Finding Terrorists: The Expanding Search Paradigm," Operations Research, INFORMS, vol. 61(2), pages 265-279, April.
    2. Steve Alpern, 2017. "Hide-and-Seek Games on a Network, Using Combinatorial Search Paths," Operations Research, INFORMS, vol. 65(5), pages 1207-1214, October.
    3. Sharlin, Ariela, 1987. "Optimal search for one of many objects hidden in two boxes," European Journal of Operational Research, Elsevier, vol. 32(2), pages 251-259, November.
    4. Thomas L. Morin & Roy E. Marsten, 1976. "Branch-and-Bound Strategies for Dynamic Programming," Operations Research, INFORMS, vol. 24(4), pages 611-627, August.
    5. Steve Alpern & Thomas Lidbetter, 2015. "Optimal Trade-Off Between Speed and Acuity When Searching for a Small Object," Operations Research, INFORMS, vol. 63(1), pages 122-133, February.
    6. Luo, Zhixing & Qin, Hu & Lim, Andrew, 2014. "Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints," European Journal of Operational Research, Elsevier, vol. 234(1), pages 49-60.
    7. Alpern, Steven & Lidbetter, Thomas, 2015. "Optimal trade-off between speed and acuity when searching for a small object," LSE Research Online Documents on Economics 61504, London School of Economics and Political Science, LSE Library.
    8. David R. Morrison & Jason J. Sauppe & Wenda Zhang & Sheldon H. Jacobson & Edward C. Sewell, 2017. "Cyclic best first search: Using contours to guide branch‐and‐bound algorithms," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(1), pages 64-82, February.
    9. Steve Alpern, 2011. "Find-and-Fetch Search on a Tree," Operations Research, INFORMS, vol. 59(5), pages 1258-1268, October.
    10. 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.
    11. Zoroa, N. & Zoroa, P. & Fernández-Sáez, M.J., 2009. "Weighted search games," European Journal of Operational Research, Elsevier, vol. 195(2), pages 394-411, June.
    12. E. C. Sewell & S. H. Jacobson, 2012. "A Branch, Bound, and Remember Algorithm for the Simple Assembly Line Balancing Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 433-442, August.
    13. J.C. Gittins & D.M. Roberts, 1979. "The search for an intelligent evader concealed in one of an arbitrary number of regions," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 26(4), pages 651-666, December.
    14. Vic Baston & Kensaku Kikuta, 2015. "Search games on a network with travelling and search costs," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(2), pages 347-365, May.
    15. D. M. Roberts & J. C. Gittins, 1978. "The search for an intelligent evader: Strategies for searcher and evader in the two‐region problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 25(1), pages 95-106, March.
    16. Wayne E. Smith, 1956. "Various optimizers for single‐stage production," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(1‐2), pages 59-66, March.
    17. Lidbetter, Thomas, 2013. "Search games with multiple hidden objects," LSE Research Online Documents on Economics 55103, London School of Economics and Political Science, LSE Library.
    18. Godinho, Pedro & Dias, Joana, 2013. "Two-player simultaneous location game: Preferential rights and overbidding," European Journal of Operational Research, Elsevier, vol. 229(3), pages 663-672.
    19. Edward Sewell & Jason Sauppe & David Morrison & Sheldon Jacobson & Gio Kao, 2012. "A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times," Journal of Global Optimization, Springer, vol. 54(4), pages 791-812, December.
    20. Godinho, Pedro & Dias, Joana, 2010. "A two-player competitive discrete location model with simultaneous decisions," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1419-1432, December.
    21. 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.
    Full references (including those not matched with items on IDEAS)

    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. Lidbetter, Thomas, 2020. "Search and rescue in the face of uncertain threats," European Journal of Operational Research, Elsevier, vol. 285(3), pages 1153-1160.
    2. Garrec, Tristan & Scarsini, Marco, 2020. "Search for an immobile hider on a stochastic network," European Journal of Operational Research, Elsevier, vol. 283(2), pages 783-794.
    3. Lisa Hellerstein & Thomas Lidbetter & Daniel Pirutinsky, 2019. "Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games," Operations Research, INFORMS, vol. 67(3), pages 731-743, May.
    4. Steve Alpern & Thomas Lidbetter, 2019. "Approximate solutions for expanding search games on general networks," Annals of Operations Research, Springer, vol. 275(2), pages 259-279, April.
    5. 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.
    6. Steve Alpern, 2017. "Hide-and-Seek Games on a Network, Using Combinatorial Search Paths," Operations Research, INFORMS, vol. 65(5), pages 1207-1214, October.
    7. Baston, Vic & Kikuta, Kensaku, 2019. "A search problem on a bipartite network," European Journal of Operational Research, Elsevier, vol. 277(1), pages 227-237.
    8. Lidbetter, Thomas & Lin, Kyle Y., 2019. "Searching for multiple objects in multiple locations," European Journal of Operational Research, Elsevier, vol. 278(2), pages 709-720.
    9. Robbert Fokkink & Thomas Lidbetter & László A. Végh, 2019. "On Submodular Search and Machine Scheduling," Management Science, INFORMS, vol. 44(4), pages 1431-1449, November.
    10. Alpern, Steve & Lidbetter, Thomas, 2020. "Search and Delivery Man Problems: When are depth-first paths optimal?," European Journal of Operational Research, Elsevier, vol. 285(3), pages 965-976.
    11. 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.
    12. Garrec, Tristan, 2019. "Continuous patrolling and hiding games," European Journal of Operational Research, Elsevier, vol. 277(1), pages 42-51.
    13. Robbert Fokkink & Ken Kikuta & David Ramsey, 2017. "The search value of a set," Annals of Operations Research, Springer, vol. 256(1), pages 63-73, September.
    14. David R. Morrison & Jason J. Sauppe & Wenda Zhang & Sheldon H. Jacobson & Edward C. Sewell, 2017. "Cyclic best first search: Using contours to guide branch‐and‐bound algorithms," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(1), pages 64-82, February.
    15. Steve Alpern & Thomas Lidbetter, 2014. "Searching a Variable Speed Network," Mathematics of Operations Research, INFORMS, vol. 39(3), pages 697-711, August.
    16. Jake Clarkson & Kevin D. Glazebrook & Kyle Y. Lin, 2020. "Fast or Slow: Search in Discrete Locations with Two Search Modes," Operations Research, INFORMS, vol. 68(2), pages 552-571, March.
    17. Dilek, Hande & Karaer, Özgen & Nadar, Emre, 2018. "Retail location competition under carbon penalty," European Journal of Operational Research, Elsevier, vol. 269(1), pages 146-158.
    18. Ramirez-Marquez, José Emmanuel & Li, Qing, 2018. "Locating and protecting facilities from intentional attacks using secrecyAuthor-Name: Zhang, Chi," Reliability Engineering and System Safety, Elsevier, vol. 169(C), pages 51-62.
    19. 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.
    20. Bruni, M.E. & Khodaparasti, S. & Beraldi, P., 2020. "The selective minimum latency problem under travel time variability: An application to post-disaster assessment operations," Omega, Elsevier, vol. 92(C).

    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:289:y:2021:i:1:p:338-349. See general information about how to correct material in RePEc.

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

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.