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. Sacha Bourgeois-Gironde, 2017. "How regret moves individual and collective choices towards rationality," Chapters, in: Morris Altman (ed.), Handbook of Behavioural Economics and Smart Decision-Making, chapter 11, pages 188-204, Edward Elgar Publishing.
    6. 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.
    7. Jhunjhunwala, Tanushree, 2021. "Searching to avoid regret: An experimental evidence," Journal of Economic Behavior & Organization, Elsevier, vol. 189(C), pages 298-319.
    8. 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.
    9. Ming Li & Dipjyoti Majumdar, 2010. "A Psychologically Based Model of Voter Turnout," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 12(5), pages 979-1002, October.
    10. Kobana Abukari & Isaac Otchere, 2020. "Dominance of hybrid contratum strategies over momentum and contrarian strategies: half a century of evidence," Financial Markets and Portfolio Management, Springer;Swiss Society for Financial Market Research, vol. 34(4), pages 471-505, December.
    11. Qin, Jie, 2015. "A model of regret, investor behavior, and market turbulence," Journal of Economic Theory, Elsevier, vol. 160(C), pages 150-174.
    12. Sugden, Robert & Wang, Mengjie & Zizzo, Daniel John, 2019. "Take it or leave it: Experimental evidence on the effect of time-limited offers on consumer behaviour," Journal of Economic Behavior & Organization, Elsevier, vol. 168(C), pages 1-23.
    13. 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.
    14. 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.
    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. 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.
    17. Starmer, Chris, 1999. "Experimental Economics: Hard Science or Wasteful Tinkering?," Economic Journal, Royal Economic Society, vol. 109(453), pages 5-15, February.
    18. Ryan, Mandy, 1998. "Valuing psychological factors in the provision of assisted reproductive techniques using the economic instrument of willingness to pay," Journal of Economic Psychology, Elsevier, vol. 19(2), pages 179-204, April.
    19. Alarie, Yves, 2000. "L’importance de la procédure dans les choix de loteries," L'Actualité Economique, Société Canadienne de Science Economique, vol. 76(3), pages 321-340, septembre.
    20. Arianna Degan & Antonio Merlo, 2011. "A Structural Model Of Turnout And Voting In Multiple Elections," Journal of the European Economic Association, European Economic Association, vol. 9(2), pages 209-245, April.

    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.