AdONE Seminar: Thomas Lidbetter (Rutgers Business School)
Dr. Thomas Lidbetter (Rutgers Business School): "A search game on a hypergraph with booby traps" – 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 or search-and-rescue operation in which the rewards correspond to people who must be rescued, and a booby trapped box being opened corresponds to the Searcher being caught or incapacitated. It could also model a machine scheduling problem, in which rewards are obtained from successfully processing jobs but the machine may crash. Although solving the game is NP-hard in general, we give the solution in some special cases and make a conjecture about the form of a general solution.
Joint work with Kyle Lin.
Date: Monday, October 21st , 2019 (starting at 14:00)