A Booby Trap Game

• 成果类型: Article; Early Access
• 署名作者: Lidbetter, Thomas; Lin, Kyle Y.
• 署名单位: Rutgers University New Brunswick; Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick; United States Department of Defense; United States Navy; Naval Postgraduate School
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2024.1518
• 发表日期: 2026
• 关键词: NETWORK SEARCH GAMES; objects

摘要

This paper presents a booby trap game played between a defender and an attacker on a search space, which may be a Lebesque measurable subset of Euclidean space or a network. The defender has several booby traps and chooses where to plant them. The attacker, aware of the presence of these booby traps but not their locations, chooses a subset of the space and collects a reward equal to the Lebesgue measure of the subset. If the attacker does not encounter any booby traps, then the attacker keeps the reward; otherwise, the attacker gets nothing. The attacker's objective is to maximize the expected reward, whereas the defender's objective is to minimize it. We solve this game in the case that the search space is a Lebesgue measurable, path-connected subset of Euclidean space and then turn our attention to the case where the search space is a network in which the attacker must choose a connected subset of the network. We solve the game when the network is a circle or a line. For the case of one booby trap, we solve the game for two-connected networks, and when the network is a tree, we present an upper bound and a lower bound for the value of the game whose ratio is at most 27/25. We also present an optimal solution for each player in a few cases where the tree is a star network.