IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2008.09653.html
   My bibliography  Save this paper

Search for a moving target in a competitive environment

Author

Listed:
  • Benoit Duvocelle
  • J'anos Flesch
  • Hui Min Shi
  • Dries Vermeulen

Abstract

We consider a discrete-time dynamic search game in which a number of players compete to find an invisible object that is moving according to a time-varying Markov chain. We examine the subgame perfect equilibria of these games. The main result of the paper is that the set of subgame perfect equilibria is exactly the set of greedy strategy profiles, i.e. those strategy profiles in which the players always choose an action that maximizes their probability of immediately finding the object. We discuss various variations and extensions of the model.

Suggested Citation

  • Benoit Duvocelle & J'anos Flesch & Hui Min Shi & Dries Vermeulen, 2020. "Search for a moving target in a competitive environment," Papers 2008.09653, arXiv.org, revised Aug 2020.
    • Handle: RePEc:arx:papers:2008.09653
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2008.09653
    File Function: Latest version
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. 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.
    2. Bogdan C. Bichescu & Michael J. Fry, 2009. "Vendor-managed inventory and the effect of channel power," Springer Books, in: Herbert Meyr & Hans-Otto Günther (ed.), Supply Chain Planning, pages 247-280, Springer.
    3. Tobias Harks & Max Klimm, 2012. "On the Existence of Pure Nash Equilibria in Weighted Congestion Games," Mathematics of Operations Research, INFORMS, vol. 37(3), pages 419-436, August.
    4. Rahul Savani & Bernhard Stengel, 2006. "Hard-to-Solve Bimatrix Games," Econometrica, Econometric Society, vol. 74(2), pages 397-429, March.
    5. 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.
    6. Stephen M. Pollock, 1970. "A Simple Model of Search for a Moving Target," Operations Research, INFORMS, vol. 18(5), pages 883-903, October.
    7. János Flesch & Emin Karagözoǧlu & Andrés Perea, 2009. "Optimal search for a moving target with the option to wait," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(6), pages 526-539, September.
    8. Tobias Harks & Veerle Timmermans, 2018. "Uniqueness of equilibria in atomic splittable polymatroid congestion games," Journal of Combinatorial Optimization, Springer, vol. 36(3), pages 812-830, October.
    9. Stanley J. Benkoski & Michael G. Monticino & James R. Weisinger, 1991. "A survey of the search theory literature," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(4), pages 469-494, August.
    10. Koller, Daphne & Megiddo, Nimrod & von Stengel, Bernhard, 1996. "Efficient Computation of Equilibria for Extensive Two-Person Games," Games and Economic Behavior, Elsevier, vol. 14(2), pages 247-259, June.
    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. 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.
    2. Mikhail Khachumov & Vyacheslav Khachumov, 2023. "Modeling the Solution of the Pursuit–Evasion Problem Based on the Intelligent–Geometric Control Theory," Mathematics, MDPI, vol. 11(23), pages 1-26, December.

    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. 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.
    2. Delavernhe, Florian & Jaillet, Patrick & Rossi, André & Sevaux, Marc, 2021. "Planning a multi-sensors search for a moving target considering traveling costs," European Journal of Operational Research, Elsevier, vol. 292(2), pages 469-482.
    3. Conitzer, Vincent & Sandholm, Tuomas, 2008. "New complexity results about Nash equilibria," Games and Economic Behavior, Elsevier, vol. 63(2), pages 621-641, July.
    4. Jun Honda, 2015. "Games with the Total Bandwagon Property," Department of Economics Working Papers wuwp197, Vienna University of Economics and Business, Department of Economics.
    5. Tami Tamir, 2023. "Cost-sharing games in real-time scheduling systems," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(1), pages 273-301, March.
    6. Sung, Shao-Chin & Dimitrov, Dinko, 2010. "Computational complexity in additive hedonic games," European Journal of Operational Research, Elsevier, vol. 203(3), pages 635-639, June.
    7. Bernhard von Stengel & Antoon van den Elzen & Dolf Talman, 2002. "Computing Normal Form Perfect Equilibria for Extensive Two-Person Games," Econometrica, Econometric Society, vol. 70(2), pages 693-715, March.
    8. Khan, M. Ali & Pedersen, Arthur Paul & Schrittesser, David, 2024. "Two-Person Adversarial Games are Zero-Sum: An elaboration of a folk theorem," Economics Letters, Elsevier, vol. 242(C).
    9. Morales, Dolores Romero & Vermeulen, Dries, 2009. "Existence of equilibria in a decentralized two-level supply chain," European Journal of Operational Research, Elsevier, vol. 197(2), pages 642-658, September.
    10. Joseph B. Kadane, 2015. "Optimal discrete search with technological choice," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 81(3), pages 317-336, June.
    11. Rahul Savani & Bernhard von Stengel, 2016. "Unit vector games," International Journal of Economic Theory, The International Society for Economic Theory, vol. 12(1), pages 7-27, March.
    12. Corine M. Laan & Ana Isabel Barros & Richard J. Boucherie & Herman Monsuur & Judith Timmer, 2019. "Solving partially observable agent‐intruder games with an application to border security problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(2), pages 174-190, March.
    13. Luciano De Castro, 2012. "Correlation of Types in Bayesian Games," Discussion Papers 1556, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    14. Peter Godfrey-Smith & Manolo Martínez, 2013. "Communication and Common Interest," PLOS Computational Biology, Public Library of Science, vol. 9(11), pages 1-6, November.
    15. Tim Roughgarden, 2018. "Complexity Theory, Game Theory, and Economics: The Barbados Lectures," Papers 1801.00734, arXiv.org, revised Feb 2020.
    16. Phan, Dinh Anh & Vo, Thi Le Hoa & Lai, Anh Ngoc & Nguyen, Thi Lan Anh, 2019. "Coordinating contracts for VMI systems under manufacturer-CSR and retailer-marketing efforts," International Journal of Production Economics, Elsevier, vol. 211(C), pages 98-118.
    17. Sobel, Joel, 2009. "ReGale: Some memorable results," Games and Economic Behavior, Elsevier, vol. 66(2), pages 632-642, July.
    18. Tim Roughgarden, 2010. "Computing equilibria: a computational complexity perspective," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 193-236, January.
    19. Takuya Masuzawa, 2008. "Computing the cores of strategic games with punishment–dominance relations," International Journal of Game Theory, Springer;Game Theory Society, vol. 37(2), pages 185-201, June.
    20. Steven M. Shechter & Farhad Ghassemi & Yasin Gocgun & Martin L. Puterman, 2015. "Technical Note—Trading Off Quick versus Slow Actions in Optimal Search," Operations Research, INFORMS, vol. 63(2), pages 353-362, April.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:arx:papers:2008.09653. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.