Infiltration games on arbitrary graphs (Q1191856): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3363109 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A basic searchlight game / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Search games / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Parallel concepts in graph theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3799847 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: About when to use the searchlight / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Markov chain game with dynamic information / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3670933 / rank | |||
Normal rank |
Revision as of 12:52, 16 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Infiltration games on arbitrary graphs |
scientific article |
Statements
Infiltration games on arbitrary graphs (English)
0 references
27 September 1992
0 references
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.
0 references
infiltration game
0 references
graph
0 references
value
0 references
restricted game
0 references