Infiltration games on arbitrary graphs
type: Item
instance of: scholarly article
title: Infiltration games on arbitrary graphs
zbMATH Open document ID: 0784.90112
DOI: 10.1016/0022-247X(92)90295-O
published in: Journal of Mathematical Analysis and Applications
publication date: 1992-09-27T00:00:00Z
review text: In an infiltration game a graph \(G\) is given. One of the players, the Infiltrator, chooses a path \(a= p(0),\;p(1),\;\dots,\;p(T)= b\) in \(G\) that connects a given point \(a\) with another point \(b\). The other player, the Guard, chooses for every time moment a vertex \(g(t)\neq a,b\). If at some time moment \(p(t)= g(t)\) the Infiltrator is captured with probability \(1-\lambda\). In the zero-sum game \(\Gamma\) the payoff to the Infiltrator is the probability that he reaches his target \(b\). In some versions of the problem the Infiltrator is only allowed to choose paths that reach \(b\) in at most \(n\) steps. If \(k\) is the minimal number of vertices that must be removed to disconnect \(a\) from \(b\) the following is true: The value of the (unrestricted) game is \(1-{1-\lambda\over k}\) and the value of the restricted game is between \[ \lambda^{z+1}\left( {n- 1\over w}-z\right)+ \lambda^ z\left( 1+ z-{n-1\over w}\right)\quad\text{and}\quad 1-{1-\lambda\over k} \] with \(w= kn-\#(V)\) and \(z=\Bigl\lfloor{n-1\over w}\Bigr\rfloor\). This result was known for some special classes of graphs.
Mathematics Subject Classification ID: 91A43
Mathematics Subject Classification ID: 91A05
zbMATH DE Number: 62883
zbMATH Keywords: infiltration game
zbMATH Keywords: graph
zbMATH Keywords: value
zbMATH Keywords: restricted game
author: Steve Alpern
reviewed by: Jos Potters
MaRDI profile type: Publication
cites work: Q3363109
cites work: A basic searchlight game
cites work: Search games
cites work: Parallel concepts in graph theory
cites work: Q3799847
cites work: About when to use the searchlight
cites work: A Markov chain game with dynamic information
cites work: Q3670933
full work available at URL: 0022-247x(92)90295-o
OpenAlex ID: W1995830743
description: scientific article; zbMATH DE number 62883