Information Technology Reference
In-Depth Information
B
0
=
{
(
1
,
1
)
,
(
1
,
2
)
,...,
(
1
,
16
)
,
(
2
,
1
)
,
(
2
,
2
)
,...,
(
2
,
16
)
,
(
3
,
1
)
,
(
3
,
2
)
,...,
(
3
,
10
)
,
(
4
,
1
)
,
(
4
,
2
)
,...
(
4
,
10
)
,
(
5
,
1
)
,
(
5
,
2
)
,...,
(
5
,
10
)
,
(
6
,
1
)
,
(
6
,
2
)
,...,
(
6
,
10
)
,
(
7
,
1
)
,
(
7
,
2
)
,...,
(
7
,
8
)
,
(
8
,
1
)
,
(
8
,
2
)
,...,
(
8
,
5
)
}
and the value of the game is
13150
1000
.
v
=
3.5 Conclusions and Open Problems
In this chapter we develop a method to facilitate the resolution of games on a finite
set, and particularly games on the lattice
L
, satisfying certain invariance properties.
Two games are studied following the proposed method, the OEIG and the WIG.
Some seminal results for the first can be seen in [
8
], where a conjecture about the
value of the game is made. Here the OEIG is solved in closed form, showing that the
conjecture made in [
8
] was true. To solve the WIG we have to solve an interesting
problem of minima and once this problem is solved, the solution for the WIG is
straightforward. We develop a method to solve the problem of minima which can
be easily implemented in a program. This program gives the solution when
n
≤
7
and in a wide variety of cases for
n
7, but, unfortunately, we have not been able to
solve this game in closed form. The complete solution for the WIG with
c
1
=
>
c
2
=
...
=
c
is obtained in [
11
].
When we deal with games on the lattice we find many other open problems. Let
as consider the example in the introduction where a hacker tries to get information
from the computers of a big enterprise, the game that model this situation is studied
in [
11
] and, there, it is solved when some constraints on their parameters are satis-
fied, but the complete solution of the game is not obtained. The patrolling games on
line graphs over the time studied in [
3
] are solved in some particular cases, but the
general solutions have not been obtained. Other examples are the lattice games that
have been studied in [
7
]andin[
9
]. None of them has been completely solved. We
discuss these lattice games in Chap.
7
of the topic.
c
n
=
References
1.
Alpern, S., Asic M.: The search value of a network. Networks 15(2), 229-238 (1985)
2.
Alpern, S. and Gal, S.: The theory of search games and rendezvous. Kluwer Academic Pub-
lishers, Boston, Dordretch, London (2003)
3.
Alpern, S., Morton, A. and Papadaki, K.: Patrolling games. Oper. Res. 59, 1246-1257 (2011)
4.
Gal, S.: Search games with mobile and immobile hider. SIAM J. Control Optim. 17 99-122
(1979)
5.
Gal, S.: Search games. Academic Press, New York (1980)
Search WWH ::
Custom Search