Premium
Search games on networks with travelling and search costs and with arbitrary searcher starting points
Author(s) -
Baston Vic,
Kikuta Kensaku
Publication year - 2013
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21504
Subject(s) - node (physics) , upper and lower bounds , mathematics , mathematical optimization , enhanced data rates for gsm evolution , search cost , computer science , artificial intelligence , economics , microeconomics , mathematical analysis , structural engineering , engineering
The authors analyze two‐person zero‐sum search games of the following type. Play takes place on a network; the hider must choose a node and remain there while the searcher can choose the node at which he starts. To detect the hider, the searcher needs to conduct a search at the node chosen by the hider. Searching a node involves a cost which can vary from node to node. In addition to the search costs, the searcher also incurs travelling costs represented by distances on the edges. The costs are known to both players and the searcher wants to minimize his total costs. An upper bound for the value of the game is obtained and a lower bound when the network has all its edge lengths the same. Restricting attention to networks which have all their edges of the same length, the upper, and lower bounds are shown to coincide for some networks including Hamiltonian ones. Some results for the star and line networks are also given. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013