IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v66y2019i2p174-190.html
   My bibliography  Save this article

Solving partially observable agent‐intruder games with an application to border security problems

Author

Listed:
  • Corine M. Laan
  • Ana Isabel Barros
  • Richard J. Boucherie
  • Herman Monsuur
  • Judith Timmer

Abstract

In this paper, we introduce partially observable agent‐intruder games (POAIGs). These games model dynamic search games on graphs between security forces (an agent) and an intruder given possible (border) entry points and high value assets that require protection. The agent faces situations with dynamically changing, partially observable information about the state of the intruder and vice versa. The agent may place sensors at selected locations, while the intruder may recruit partners to observe the agent's movement. We formulate the problem as a two‐person zero‐sum game, and develop efficient algorithms to compute each player's optimal strategy. The solution to the game will help the agent choose sensor locations and design patrol routes that can handle imperfect information. First, we prove the existence of ϵ‐optimal strategies for POAIGs with an infinite time horizon. Second, we introduce a Bayesian approximation algorithm to identify these ϵ‐optimal strategies using belief functions that incorporate the imperfect information that becomes available during the game. For the solutions of large POAIGs with a finite time horizon, we use a solution method common to extensive form games, namely, the sequence form representation. To illustrate the POAIGs, we present several examples and numerical results.

Suggested Citation

  • 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.
  • Handle: RePEc:wly:navres:v:66:y:2019:i:2:p:174-190
    DOI: 10.1002/nav.21834
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.21834
    Download Restriction: no

    File URL: https://libkey.io/10.1002/nav.21834?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
    ---><---

    References listed on IDEAS

    as
    1. von Stengel, Bernhard, 1996. "Efficient Computation of Behavior Strategies," Games and Economic Behavior, Elsevier, vol. 14(2), pages 220-246, June.
    2. Daniel S. Bernstein & Robert Givan & Neil Immerman & Shlomo Zilberstein, 2002. "The Complexity of Decentralized Control of Markov Decision Processes," Mathematics of Operations Research, INFORMS, vol. 27(4), pages 819-840, November.
    3. 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.
    4. Jenelius, Erik & Westin, Jonas & Holmgren, Åke J., 2010. "Critical infrastructure protection under imperfect attacker perception," International Journal of Critical Infrastructure Protection, Elsevier, vol. 3(1), pages 16-26.
    5. John C. Harsanyi, 1967. "Games with Incomplete Information Played by "Bayesian" Players, I-III Part I. The Basic Model," Management Science, INFORMS, vol. 14(3), pages 159-182, November.
    6. Kyle Y. Lin & Michael P. Atkinson & Kevin D. Glazebrook, 2014. "Optimal patrol to uncover threats in time when detection is imperfect," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(8), pages 557-576, December.
    7. James N. Eagle, 1984. "The Optimal Search for a Moving Target When the Search Path Is Constrained," Operations Research, INFORMS, vol. 32(5), pages 1107-1115, October.
    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. Wang, Jian & Cui, Lei, 2023. "Patrolling games with coordination between monitoring devices and patrols," Reliability Engineering and System Safety, Elsevier, vol. 233(C).

    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. Aurélien Delage & Olivier Buffet & Jilles S. Dibangoye & Abdallah Saffidine, 2024. "HSVI Can Solve Zero-Sum Partially Observable Stochastic Games," Dynamic Games and Applications, Springer, vol. 14(4), pages 751-805, September.
    2. 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.
    3. Pahl, Lucas, 2023. "Polytope-form games and index/degree theories for extensive-form games," Games and Economic Behavior, Elsevier, vol. 141(C), pages 444-471.
    4. Edouard Kujawski, 2016. "A Probabilistic Game‐Theoretic Method to Assess Deterrence and Defense Benefits of Security Systems," Systems Engineering, John Wiley & Sons, vol. 19(6), pages 549-566, November.
    5. Srihari Govindan & Robert Wilson, 2008. "Metastable Equilibria," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 787-820, November.
    6. Samid Hoda & Andrew Gilpin & Javier Peña & Tuomas Sandholm, 2010. "Smoothing Techniques for Computing Nash Equilibria of Sequential Games," Mathematics of Operations Research, INFORMS, vol. 35(2), pages 494-512, May.
    7. Etessami, Kousha, 2021. "The complexity of computing a (quasi-)perfect equilibrium for an n-player extensive form game," Games and Economic Behavior, Elsevier, vol. 125(C), pages 107-140.
    8. Bernhard von Stengel & Françoise Forges, 2008. "Extensive-Form Correlated Equilibrium: Definition and Computational Complexity," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 1002-1022, November.
    9. Itzhak Rasooly & Carlos Gavidia-Calderon, 2020. "The importance of being discrete: on the inaccuracy of continuous approximations in auction theory," Papers 2006.03016, arXiv.org, revised Aug 2022.
    10. F. Forges & B. von Stengel, 2002. "Computionally Efficient Coordination in Games Trees," THEMA Working Papers 2002-05, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
    11. Yanling Chang & Alan Erera & Chelsea White, 2015. "A leader–follower partially observed, multiobjective Markov game," Annals of Operations Research, Springer, vol. 235(1), pages 103-128, December.
    12. Govindan, Srihari & Wilson, Robert B., 2007. "Stable Outcomes of Generic Games in Extensive Form," Research Papers 1933r, Stanford University, Graduate School of Business.
    13. Shimoji, Makoto & Watson, Joel, 1998. "Conditional Dominance, Rationalizability, and Game Forms," Journal of Economic Theory, Elsevier, vol. 83(2), pages 161-195, December.
    14. Conitzer, Vincent & Sandholm, Tuomas, 2008. "New complexity results about Nash equilibria," Games and Economic Behavior, Elsevier, vol. 63(2), pages 621-641, July.
    15. Martin Meier & Burkhard Schipper, 2014. "Bayesian games with unawareness and unawareness perfection," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 56(2), pages 219-249, June.
    16. Rosenbaum, Janet, 2002. "The Computational Complexity of Nash Equilibria," SocArXiv h63mz_v1, Center for Open Science.
    17. Huseyin Cavusoglu & Srinivasan Raghunathan, 2004. "Configuration of Detection Software: A Comparison of Decision and Game Theory Approaches," Decision Analysis, INFORMS, vol. 1(3), pages 131-148, September.
    18. Strzalecki, Tomasz, 2014. "Depth of reasoning and higher order beliefs," Journal of Economic Behavior & Organization, Elsevier, vol. 108(C), pages 108-122.
    19. 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.
    20. Yoo, Seung Han, 2014. "Learning a population distribution," Journal of Economic Dynamics and Control, Elsevier, vol. 48(C), pages 188-201.

    More about this item

    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:wly:navres:v:66:y:2019:i:2:p:174-190. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.