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

Abdolmajid Yolmeh, Melike Baykal-Gürsoy

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)338-349
Number of pages12
JournalEuropean Journal of Operational Research
Volume289
Issue number1
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Weighted network search games with multiple hidden objects and multiple search teams'. Together they form a unique fingerprint.

Cite this