Hide-and-Seek Game with Capacitated Locations and Imperfect Detection
- 1 June 2024
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Decision Analysis
- Vol. 21 (2) , 110-124
Abstract
We consider a variant of the hide-and-seek game in which a seeker inspects multiple hiding locations to find multiple items hidden by a hider. Each hiding location has a maximum hiding capacity and a probability of detecting its hidden items when an inspection by the seeker takes place. The objective of the seeker (respectively, hider) is to minimize (respectively, maximize) the expected number of undetected items. This model is motivated by strategic inspection problems, where a security agency is tasked with coordinating multiple inspection resources to detect and seize illegal commodities hidden by a criminal organization. To solve this large-scale zero-sum game, we leverage its structure and show that its mixed-strategy Nash equilibria can be characterized using their unidimensional marginal distributions, which are pure equilibria of a lower dimensional continuous zero-sum game. This leads to a two-step approach for efficiently solving our hide-and-seek game: First, we analytically solve the continuous game and derive closed-form expressions of the equilibrium marginal distributions. Second, we design a combinatorial algorithm to coordinate the players’ resources and compute equilibrium mixed strategies that satisfy the marginal distributions. We show that this solution approach computes a Nash equilibrium of the hide-and-seek game in quadratic time with linear support. Our analysis reveals novel equilibrium behaviors driven by a complex interplay between the game parameters, captured by our closed-form solutions. Funding: This work was supported by the Georgia Tech Stewart Fellowship and the Georgia Tech New Faculty Start Up Grant. Supplemental Material: The online appendix is available at https://doi.org/10.1287/deca.2023.0012 .Keywords
All Related Versions
This publication has 41 references indexed in Scilit:
- Radar-to-Radar Interference Suppression for Distributed Radar Sensor NetworksRemote Sensing, 2014
- Search Games with Multiple Hidden ObjectsSIAM Journal on Control and Optimization, 2013
- A search game model of the scatter hoarder's problemJournal of The Royal Society Interface, 2011
- Fatal Attraction: Salience, Naïveté, and Sophistication in Experimental “Hide-and-Seek” GamesAmerican Economic Review, 2007
- Improving Wireless Sensor Network Lifetime through Power Aware OrganizationWireless Networks, 2005
- Continuous accumulation games on discrete locationsNaval Research Logistics (NRL), 2002
- Adaptive Game Playing Using Multiplicative WeightsGames and Economic Behavior, 1999
- A hide–search gameJournal of Applied Probability, 1981
- The search for an intelligent evader: Strategies for searcher and evader in the two‐region problemNaval Research Logistics Quarterly, 1978
- Zur Theorie der GesellschaftsspieleMathematische Annalen, 1928