U.S. flag

An official website of the United States government, Department of Justice.

Weighted network search games with multiple hidden objects and multiple search teams

NCJ Number
304154
Journal
European Journal of Operational Research Volume: 289 Issue: 1 Dated: February 2021 Pages: 338-349
Date Published
February 2021
Length
12 pages
Annotation

This project introduced a new network search game with consideration given to the weights at different locations.

 

Abstract

Most search game models assume that the hiding locations are identical, and the players’ objective is to optimize the search time; however, there are some cases in which the players may differentiate the hiding locations from each other, and the objective is to optimize a weighted search time. In addition, the search may involve multiple search teams. In the proposed network search game, a hider can hide multiple objects and there may be multiple search teams. For a special case of the problem, this project proved that the game has a closed-form Nash equilibrium. For the general case, the project developed an algorithm based on column and row generation. It showed that the Searcher’s subproblem is NP-hard and proposed a branch and price algorithm to solve it.  The project also presents a polynomial time algorithm for the Hider’s subproblem. Numerical experiments demonstrate the efficiency of the proposed algorithms and reveal insights into the properties of this game. (publisher abstract modified)

 

Date Published: February 1, 2021