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

Searching for multiple objects in multiple locations

Author

Listed:
  • Lidbetter, Thomas
  • Lin, Kyle Y.

Abstract

Many practical search problems concern the search for multiple hidden objects or agents, such as earthquake survivors. In such problems, knowing only the list of possible locations, the Searcher needs to find all the hidden objects by visiting these locations one by one. To study this problem, we formulate new game-theoretic models of discrete search between a Hider and a Searcher. The Hider hides k balls in n boxes, and the Searcher opens the boxes one by one with the aim of finding all the balls. Every time the Searcher opens a box she must pay its search cost, and she either finds one of the balls it contains or learns that it is empty. If the Hider is an adversary, an appropriate payoff function may be the expected total search cost paid to find all the balls, while if the Hider is Nature, a more appropriate payoff function may be the difference between the total amount paid and the amount the Searcher would have to pay if she knew the locations of the balls a priori (the regret). We give a full solution to the regret version of this game, and a partial solution to the search cost version. We also consider variations on these games for which the Hider can hide at most one ball in each box. The search cost version of this game has already been solved in previous work, and we give a partial solution in the regret version.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:278:y:2019:i:2:p:709-720
    DOI: 10.1016/j.ejor.2019.05.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719303868
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.05.002?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. David E. Bell, 1982. "Regret in Decision Making under Uncertainty," Operations Research, INFORMS, vol. 30(5), pages 961-981, October.
    2. 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.
    3. Loomes, Graham & Sugden, Robert, 1982. "Regret Theory: An Alternative Theory of Rational Choice under Uncertainty," Economic Journal, Royal Economic Society, vol. 92(368), pages 805-824, December.
    4. 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.
    5. 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.
    6. 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.
    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. 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.
    2. Bastián Bahamondes & Mathieu Dahan, 2024. "Hide-and-Seek Game with Capacitated Locations and Imperfect Detection," Decision Analysis, INFORMS, vol. 21(2), pages 110-124, June.
    3. Georgia Perakis & Guillaume Roels, 2008. "Regret in the Newsvendor Model with Partial Information," Operations Research, INFORMS, vol. 56(1), pages 188-203, February.
    4. Jinyi Hu, 2023. "Linguistic Multiple-Attribute Decision Making Based on Regret Theory and Minimax-DEA," Mathematics, MDPI, vol. 11(20), pages 1-14, October.
    5. Martín Egozcue & Xu Guo & Wing-Keung Wong, 2015. "Optimal output for the regret-averse competitive firm under price uncertainty," Eurasian Economic Review, Springer;Eurasia Business and Economics Society, vol. 5(2), pages 279-295, December.
    6. Jhunjhunwala, Tanushree, 2021. "Searching to avoid regret: An experimental evidence," Journal of Economic Behavior & Organization, Elsevier, vol. 189(C), pages 298-319.
    7. van Dijk, Wilco W. & van der Pligt, Joop, 1997. "The Impact of Probability and Magnitude of Outcome on Disappointment and Elation," Organizational Behavior and Human Decision Processes, Elsevier, vol. 69(3), pages 277-284, March.
    8. Enrico G. De Giorgi & Thierry Post, 2011. "Loss Aversion with a State-Dependent Reference Point," Management Science, INFORMS, vol. 57(6), pages 1094-1110, June.
    9. van Dijk, W.W. & Zeelenberg, M. & van der Pligt, J., 1999. "Not having what you want versus having what you don't want : The impact of the type of negative outcome on the experience of disappointment and related emotions," Other publications TiSEM 5d1661b1-db82-4773-8ac4-5, Tilburg University, School of Economics and Management.
    10. Olivier Chanel & Graciela Chichilnisky, 2009. "The influence of fear in decisions: Experimental evidence," Journal of Risk and Uncertainty, Springer, vol. 39(3), pages 271-298, December.
    11. Soora Rasouli & Harry Timmermans, 2017. "Specification of regret-based models of choice behaviour: formal analyses and experimental design based evidence," Transportation, Springer, vol. 44(6), pages 1555-1576, November.
    12. Pedro Bordalo & Nicola Gennaioli & Andrei Shleifer, 2013. "Salience and Consumer Choice," Journal of Political Economy, University of Chicago Press, vol. 121(5), pages 803-843.
    13. Raquel M. Gaspar & Paulo M. Silva, 2023. "Investors’ perspective on portfolio insurance," Portuguese Economic Journal, Springer;Instituto Superior de Economia e Gestao, vol. 22(1), pages 49-79, January.
    14. Yuval Rottenstreich & Alex Markle & Johannes Müller-Trede, 2023. "Risky Sure Things," Management Science, INFORMS, vol. 69(8), pages 4707-4720, August.
    15. Ulrich Schmidt & Stefan Traub, 2009. "An Experimental Investigation of the Disparity Between WTA and WTP for Lotteries," Theory and Decision, Springer, vol. 66(3), pages 229-262, March.
    16. Herweg, Fabian, 2013. "The expectation-based loss-averse newsvendor," Economics Letters, Elsevier, vol. 120(3), pages 429-432.
    17. Meimei Xia & Jian Chen & Juliang Zhang, 2015. "Multi-criteria decision making based on relative measures," Annals of Operations Research, Springer, vol. 229(1), pages 791-811, June.
    18. Gang Chen & Mark S. Daskin & Zuo‐Jun Max Shen & Stanislav Uryasev, 2006. "The α‐reliable mean‐excess regret model for stochastic facility location modeling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(7), pages 617-626, October.
    19. Broll, Udo & Welzel, Peter & Wong, Kit Pong, 2014. "Multinational firm, exchange rate risk and the impact of regret on trade," Dresden Discussion Paper Series in Economics 04/14, Technische Universität Dresden, Faculty of Business and Economics, Department of Economics.
    20. Emerson Melo, 2021. "Learning in Random Utility Models Via Online Decision Problems," Papers 2112.10993, arXiv.org, revised Aug 2022.

    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:278:y:2019:i:2:p:709-720. 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.