Hide-and-Seek Game with Capacitated Locations and Imperfect Detection

References

• Abba AL, Awad M, Al-Qudah Z, Jallad AH (2017) Security analysis of current voting systems. Proc. Internat. Conf. Electronic Comput. Tech. Appl. (IEEE, Piscataway, NJ), 1–6.Crossref, Google Scholar
• Ahmadinejad A, Dehghani S, Hajiaghayi M, Lucier B, Mahini H, Seddighin S (2019) From duels to battlefields: Computing equilibria of Blotto and other games. Math. Oper. Res. 44(4):1304–1325.Link, Google Scholar
• Alpern S, Gal S (2003) The Theory of Search Games and Rendezvous (Springer, New York).Google Scholar
• Alpern S, Fokkink R, Lidbetter T, Clayton NS (2012) A search game model of the scatter hoarder’s problem. J. Royal Soc. Interface 9(70):869–879.Crossref, Google Scholar
• Alpern S, Fokkink R, op den Kelder J, Lidbetter T (2010) Disperse or unite? A mathematical model of coordinated attack. Alpcan T, Buttyán L, Baras JS, eds. Proc. Internat. Conf. Decision Game Theory Security (Springer, Berlin), 220–233.Google Scholar
• Alpern S, Gal S, Lee V, Casas J (2019) A stochastic game model of searching predators and hiding prey. J. Royal Soc. Interface 16(153):20190087.Crossref, Google Scholar
• Alpern S, Fokkink R, Gąsieniec L, Lindelauf R, Subrahmanian VS (2013) Search Theory: A Game Theoretic Perspective (Springer, New York).Crossref, Google Scholar
• Bahamondes B, Dahan M (2022) Network inspection from locations with imperfect detection capabilities. 2022 Amer. Control Conf. (IEEE, Piscataway, NJ), 613–620.Google Scholar
• Behnezhad S, Dehghani S, Derakhshan M, Hajiaghayi M, Seddighin S (2017) Faster and simpler algorithm for optimal strategies of Blotto game. Proc. 31st AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA).Google Scholar
• Behnezhad S, Blum A, Derakhshan M, HajiAghayi M, Mahdian M, Papadimitriou CH, Rivest RL, et al. (2018) From battlefields to elections: Winning strategies of Blotto and auditing games. Proc. 29th Annu. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2291–2310.Google Scholar
• Blocki J, Christin N, Datta A, Procaccia A, Sinha A (2015) Audit games with multiple defender resources. Proc. 29th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA).Google Scholar
• Bram J (1963) A 2-player n-region search game. Technical report, Center for Naval Analyses, Operations Evaluation Group, Alexandria, VA.Google Scholar
• Bui T, Lidbetter T, Lin KY (2023) Optimal pure strategies for a discrete search game. Preprint, submitted June 19, https://arxiv.org/abs/2306.10908.Google Scholar
• Cardei M, Du DZ (2005) Improving wireless sensor network lifetime through power aware organization. Wireless Networks 11(3):333–340.Crossref, Google Scholar
• Chan H, Jiang AX, Leyton-Brown K, Mehta R (2016) Multilinear games. Cai Y, Vetta A, eds. Proc. 12th Internat. Conf. Web Internet Econom. (Springer, Berlin), 44–58.Google Scholar
• Clarkson J, Lin KY (2023) Computing optimal strategies for a search game in discrete locations. Preprint, submitted May 17, https://arxiv.org/abs/2305.10342.Google Scholar
• Clarkson J, Lin KY, Glazebrook KD (2023) A classical search game in discrete locations. Math. Oper. Res. 48(2):687–707.Link, Google Scholar
• Crawford VP, Iriberri N (2007) Fatal attraction: Salience, naïveté, and sophistication in experimental “hide-and-seek” games. Amer. Econom. Rev. 97(5):1731–1750.Crossref, Google Scholar
• Creasey PE (2022) Two hide-search games with rapid strategies for multiple parallel searches. Open Comput. Sci. 12(1):171–180.Crossref, Google Scholar
• Csóka E, Lidbetter T (2016) The solution to an open problem for a caching game. Naval Res. Logist. 63(1):23–31.Crossref, Google Scholar
• Dahan M, Sela L, Amin S (2022) Network inspection for detecting strategic attacks. Oper. Res. 70(2):1008–1024.Link, Google Scholar
• Dziubiński M, Roy J (2018) Hide and seek game with multiple resources. Deng X, ed. Proc. 11th Internat. Sympos. Algorithmic Game Theory 2018 (Springer, Cham, Switzerland), 82–86.Google Scholar
• Flood MM (1972) The hide and seek game of von Neumann. Management Sci. 18(5-part-2):107–109.Link, Google Scholar
• Fokkink R, Kikuta K, Ramsey D (2017) The search value of a set. Ann. Oper. Res. 256(1):63–73.Crossref, Google Scholar
• Fokkink R, Lidbetter T, Végh LA (2019) On submodular search and machine scheduling. Math. Oper. Res. 44(4):1431–1449.Link, Google Scholar
• Freund Y, Schapire RE (1999) Adaptive game playing using multiplicative weights. Games Econom. Behav. 29(1):79–103.Crossref, Google Scholar
• Gal S, Casas J (2014) Succession of hide-seek and pursuit-evasion at heterogeneous locations. J. Royal Soc. Interface 11(94):20140062.Crossref, Google Scholar
• Gal S, Alpern S, Casas J (2015) Prey should hide more randomly when a predator attacks more persistently. J. Royal Soc. Interface 12(113):20150861.Crossref, Google Scholar
• Gittins J, Roberts D (1979) The search for an intelligent evader concealed in one of an arbitrary number of regions. Naval Res. Logist. Quart. 26(4):651–666.Crossref, Google Scholar
• Hellerstein L, Lidbetter T, Pirutinsky D (2019) Solving zero-sum games using best-response oracles with applications to search games. Oper. Res. 67(3):731–743.Link, Google Scholar
• Hohzaki R (2016) Search games: Literature and survey. J. Oper. Res. Soc. Japan 59(1):1–34.Crossref, Google Scholar
• Hohzaki R (2017) A search game with incomplete information on detective capability of searcher. Contributions Game Theory Management 10:129–142.Google Scholar
• Hohzaki R, Iida K, Komiya T (2002) Discrete search allocation game with energy constraints. J. Oper. Res. Soc. Japan 45(1):93–108.Crossref, Google Scholar
• Iida K, Hohzaki R, Sato K (1994) Hide-and-search game with the risk criterion. J. Oper. Res. Soc. Japan 37(4):287–296.Google Scholar
• Immorlica N, Kalai AT, Lucier B, Moitra A, Postlewaite A, Tennenholtz M (2011) Dueling algorithms. Proc. 43rd ACM Sympos. Theoretical Comput. (ACM, New York), 215–224.Google Scholar
• Jezierski T, Adamkiewicz E, Walczak M, Sobczyńska M, Górecka-Bruzda A, Ensminger J, Papet E (2014) Efficacy of drug detection by fully-trained police dogs varies by breed, training level, type of drug and search environment. Forensic Sci. Internat. 237:112–118.Crossref, Google Scholar
• Karlin AR, Peres Y (2017) Game Theory, Alive (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• Kiekintveld C, Jain M, Tsai J, Pita J, Ordóñez F, Tambe M (2009) Computing optimal randomized resource allocations for massive security games. Proc. 8th Internat. Conf. Autonomic Agents Multiagent Systems (IFAAMAS, Richland, SC), 689–696.Google Scholar
• Kikuta K, Ruckle WH (1997) Accumulation games, part 1: Noisy search. J. Optim. Theory Appl. 94:395–408.Crossref, Google Scholar
• Kikuta K, Ruckle WH (2002) Continuous accumulation games on discrete locations. Naval Res. Logist. 49(1):60–77.Crossref, Google Scholar
• Koller D, Megiddo N, von Stengel B (1994) Fast algorithms for finding randomized strategies in game trees. Proc. 26th ACM Sympos. Theoretical Comput. (ACM, New York), 750–759.Google Scholar
• Korzhyk D, Conitzer V, Parr R (2010) Complexity of computing optimal stackelberg strategies in security resource allocation games. Proc. 24th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 805–810.Google Scholar
• Korzhyk D, Conitzer V, Parr R (2011) Security games with multiple attacker resources. Walsh T, ed. Proc. 22nd Internat. Joint Conf. Artificial Intelligence (AAAI Press/IJCAI, Menlo Park, CA), 273–279.Google Scholar
• Leonard TJ, Gallo P, Véronneau S (2015) Security challenges in United States sea ports: An overview. J. Transportation Security 8:41–49.Crossref, Google Scholar
• Letchford J, Conitzer V (2013) Solving security games on graphs via marginal probabilities. Proc. 27th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 591–597.Google Scholar
• Lidbetter T (2013) Search games with multiple hidden objects. SIAM J. Control Optim. 51(4):3056–3074.Crossref, Google Scholar
• Lidbetter T, Lin KY (2019) Searching for multiple objects in multiple locations. Eur. J. Oper. Res. 278(2):709–720.Crossref, Google Scholar
• Lin KY, Singham DI (2016) Finding a hider by an unknown deadline. Oper. Res. Lett. 44(1):25–32.Crossref, Google Scholar
• Lipton RJ, Markakis E, Mehta A (2003) Playing large games using simple strategies. Proc. 4th ACM Conf. Electronic Commerce (ACM, New York), 36–41.Google Scholar
• Meuter RFI, Lacherez PF (2016) When and why threats go undetected: Impacts of event rate and shift length on threat detection accuracy during airport baggage screening. Human Factors 58(2):218–228.Crossref, Google Scholar
• Musegaas M, Schlicher L, Blok H (2022) Stackelberg production-protection games: Defending crop production against intentional attacks. Eur. J. Oper. Res. 297(1):102–119.Crossref, Google Scholar
• Nakai T (1988) Search models with continuous effort under various criteria. J. Oper. Res. Soc. Japan 31(3):335–352.Google Scholar
• Pirani M, Taylor JA, Sinopoli B (2021) Strategic sensor placement on graphs. Systems Control Lett. 148:104855.Crossref, Google Scholar
• Roberts DM, Gittins JC (1978) The search for an intelligent evader: Strategies for searcher and evader in the two-region problem. Naval Res. Logist. Quart. 25(1):95–106.Crossref, Google Scholar
• Ruckle WH (1991) A discrete search game. Raghavan TES, Ferguson TS, Parthasarathy T, Vrieze OJ, eds. Stochastic Games and Related Topics: In Honor of Professor L. S. Shapley (Springer, Dordrecht, Netherlands), 29–43.Crossref, Google Scholar
• Sakaguchi M (1973) Two-sided search games. J. Oper. Res. Soc. Japan 16(4):207–225.Google Scholar
• Staring R, Bisschop L, Roks R, Brein E, van de Bunt H (2023) Drug crime and the port of Rotterdam: About the phenomenon and its approach. Nelen H, Siegel D, eds. Organized Crime in the 21st Century: Motivations, Opportunities, and Constraints (Springer, Cham, Switzerland), 43–61.Crossref, Google Scholar
• Subelman EJ (1981) A hide–search game. J. Appl. Probability 18(3):628–640.Crossref, Google Scholar
• von Neumann J (1928) Zur theorie der gesellschaftsspiele. Math. Ann. 100(1):295–320.Crossref, Google Scholar
• von Neumann J (1953) A certain zero-sum two-person game equivalent to the optimal assignment problem. Kuhn HW, Tucker AW, eds. Contributions to the Theory of Games, vol. 2 (Princeton University Press, Princeton, NJ), 5–12.Crossref, Google Scholar
• von Neumann J, Morgenstern O (2004) Theory of Games and Economic Behavior (60th Anniversary Commemorative Edition) (Princeton University Press, Princeton, NJ).Google Scholar
• Wang WQ, Shao H (2014) Radar-to-radar interference suppression for distributed radar sensor networks. Remote Sensing 6(1):740–755.Crossref, Google Scholar
• Washburn A (2014) Two-Person Zero-Sum Games (Springer, New York).Crossref, Google Scholar
• Washburn A, Wood K (1995) Two-person zero-sum games for network interdiction. Oper. Res. 43(2):243–251.Link, Google Scholar