A search game on a hypergraph with booby traps

DOI10.1016/J.TCS.2020.03.011zbMATH Open1437.91104arXiv1903.12231OpenAlexW3013022787MaRDI QIDQ2173302FDOQ2173302

Authors: Kyle Y. Lin, Thomas Lidbetter 

Publication date: 22 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: A set of n boxes, located on the vertices of a hypergraph G, contain known but different rewards. A Searcher opens all the boxes in some hyperedge of G with the objective of collecting the maximum possible total reward. Some of the boxes, however, are booby trapped. If the Searcher opens a booby trapped box, the search ends and she loses all her collected rewards. We assume the number k of booby traps is known, and we model the problem as a zero-sum game between the maximizing Searcher and a minimizing Hider, where the Hider chooses k boxes to booby trap and the Searcher opens all the boxes in some hyperedge. The payoff is the total reward collected by the Searcher. This model could reflect a military operation in which a drone gathers intelligence from guarded locations, and a booby trapped box being opened corresponds to the drone being destroyed or incapacitated. It could also model a machine scheduling problem, in which rewards are obtained from successfully processing jobs but the machine may crash. We solve the game when G is a 1-uniform hypergraph (the hyperedges are all singletons), so the Searcher can open just 1 box. When G is the complete hypergraph (containing all possible hyperedges), we solve the game in a few cases: (1) same reward in each box, (2) k=1, and (3) n=4 and k=2. The solutions to these few cases indicate that a general simple, closed form solution to the game appears unlikely.

Full work available at URL: https://arxiv.org/abs/1903.12231

Recommendations

• Publication:3204351
• Search and rescue in the face of uncertain threats
• Ambush Strategies in Search Games on Graphs
• Search games with multiple hidden objects
• scientific article; zbMATH DE number 1006855

zbMATH Keywords

game theorydiscrete optimizationsearch games

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Hypergraphs (05C65) Games involving graphs (91A43)

Cites Work

• The theory of search games and rendezvous.
• Title not available (Why is that?)
• Sequencing unreliable jobs on parallel machines
• Search games with multiple hidden objects
• Search games: literature and survey
• Searching for multiple objects in multiple locations

Cited In (2)

• A search game on a cyclic graph
• A search game on the union of graphs with immobile hider

This page was built for publication: A search game on a hypergraph with booby traps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2173302)