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. To address these, we introduce a new network search game with consideration given to the weights at different locations. A hider can hide multiple objects and there may be multiple search teams. For a special case of the problem, we prove that the game has a closed-form Nash equilibrium. For the general case, we develop an algorithm based on column and row generation. We show that the Searcher's subproblem is NP-hard and propose a branch and price algorithm to solve it. We also present 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.
Original language | English (US) |
---|---|
Pages (from-to) | 338-349 |
Number of pages | 12 |
Journal | European Journal of Operational Research |
Volume | 289 |
Issue number | 1 |
DOIs | |
State | Published - Feb 16 2021 |
All Science Journal Classification (ASJC) codes
- Computer Science(all)
- Modeling and Simulation
- Management Science and Operations Research
- Information Systems and Management
Keywords
- Column and row generation
- Multiple search teams
- Search games
- Weighted locations
- Zero-sum games