Infiltration games on arbitrary graphs (Q1191856): Difference between revisions

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.