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
    File URL: https://libkey.io/10.1016/j.ejor.2020.06.046?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. Thomas L. Morin & Roy E. Marsten, 1976. "Branch-and-Bound Strategies for Dynamic Programming," Operations Research, INFORMS, vol. 24(4), pages 611-627, August.
    2. 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.
    3. Steve Alpern, 2011. "Find-and-Fetch Search on a Tree," Operations Research, INFORMS, vol. 59(5), pages 1258-1268, October.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Steve Alpern & Thomas Lidbetter, 2013. "Mining Coal or Finding Terrorists: The Expanding Search Paradigm," Operations Research, INFORMS, vol. 61(2), pages 265-279, April.
    9. Steve Alpern, 2017. "Hide-and-Seek Games on a Network, Using Combinatorial Search Paths," Operations Research, INFORMS, vol. 65(5), pages 1207-1214, October.
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    15. Gio Kao & Edward Sewell & Sheldon Jacobson & Shane Hall, 2012. "New dominance rules and exploration strategies for the 1|r i |∑U i scheduling problem," Computational Optimization and Applications, Springer, vol. 51(3), pages 1253-1274, April.
    16. 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.
    17. 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.
    18. 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.
    19. 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.
    20. 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.
    21. 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.
    22. 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.
    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. Hellerstein, Lisa & Lidbetter, Thomas, 2023. "A game theoretic approach to a problem in polymatroid maximization," European Journal of Operational Research, Elsevier, vol. 305(2), pages 979-988.

    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. 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.
    2. Lidbetter, Thomas, 2020. "Search and rescue in the face of uncertain threats," European Journal of Operational Research, Elsevier, vol. 285(3), pages 1153-1160.
    3. 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.
    4. 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.
    5. 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.
    6. Baston, Vic & Kikuta, Kensaku, 2019. "A search problem on a bipartite network," European Journal of Operational Research, Elsevier, vol. 277(1), pages 227-237.
    7. Steve Alpern, 2017. "Hide-and-Seek Games on a Network, Using Combinatorial Search Paths," Operations Research, INFORMS, vol. 65(5), pages 1207-1214, October.
    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. Wenda Zhang & Jason J. Sauppe & Sheldon H. Jacobson, 2023. "Results for the close-enough traveling salesman problem with a branch-and-bound algorithm," Computational Optimization and Applications, Springer, vol. 85(2), pages 369-407, June.
    10. 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.
    11. 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.
    12. Duvocelle, Benoit & Flesch, János & Staudigl, Mathias & Vermeulen, Dries, 2022. "A competitive search game with a moving target," European Journal of Operational Research, Elsevier, vol. 303(2), pages 945-957.
    13. 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.
    14. 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.
    15. 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.
    16. Steve Alpern & Thomas Lidbetter, 2014. "Searching a Variable Speed Network," Mathematics of Operations Research, INFORMS, vol. 39(3), pages 697-711, August.
    17. 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.
    18. 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.
    19. Morrison, David R. & Sewell, Edward C. & Jacobson, Sheldon H., 2014. "An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset," European Journal of Operational Research, Elsevier, vol. 236(2), pages 403-409.
    20. 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.

    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.

    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.