Information Technology Reference
In-Depth Information
Our approach differs from that of [ 2 ] in the following way. First we consider a
new search game that turns out to be of use to estimate the constant c in the Key
Lemma. To the best of our knowledge, this is the first attempt to use search games
in the context of graph coloring. We find that the optimal strategy of the searchers
involves tossing colored coins. This leads to a combinatorial probability problem,
which we solve in the final section. We use the solution of this problem to obtain a
better estimate in the first step in the proof of the Key Lemma. Then we apply the
arithmetic-geometric mean inequality to obtain a better estimate of the second step
in the proof of the Key Lemma. Finally, we apply results on maximally dependent
random variables to show that the global time to equilibrium,
τ
, is stochastically
dominated by an exponential random variable.
There exists a vast literature on graph coloring algorithms. Some related work
is in [ 13 ], where a graph coloring is provided in O
(
log n
)
rounds via a distributed
algorithm which uses
1 colors, or more, but requires that the neighbors have
information on the status of a vertex. Attempts to properly color a graph via strategic
games can be found in [ 5 , 14 ]. Another line of research in which games are used
to model conflict situations that are similar to those that are modeled by network
coloring is in [ 1 ]. For a general discussion on the network coloring game see [ 3 ].
Δ +
4.2 A Related Search Game
In order to estimate the first time player v is happy,
τ v , we define the following
Search Game. A player, H , the hider, chooses an element from
Ω = {
1
,
2
,...,
d
}
with d
2. So the strategy space of H is the set
Ω
. The opponent of H consists of
a team of m
d searchers (agents) that each choose a subset
Ω j containing at least
two colors from
Ω
. We denote these searchers by S j ,
1
j
m . Subsequently, each
searcher draws a color
ω
j uniformly randomly from his own
Ω
j . The searchers may
communicate their choice of
j .If H has chosen a color that is different from all
ω j he wins, otherwise he looses. This is a finite, one round zero-sum game that has
a value, which is the probability that H wins under optimal play on both sides.
Ω
Lemma 2. The optimal strategy for H is to choose his color uniformly randomly.
Proof. This is a standard invariance argument (see [ 6 ], page 24). The game is in-
variant under the group,
π ( , Ω 1 , Ω 2 ,..., Ω m )
be the payoff to H (i.e. his winning probability) provided that H has chosen
S d , of permutations. To see this, let
and
S j has chosen
Ω j ,
j
=
1
,
2
,...,
m . Then, for any
σ ∈ S d we have that
π ( , Ω 1 , Ω 2 ,..., Ω m )= π ( σ ( ) , σ ( Ω 1 ) , σ ( Ω 2 ) ,..., σ ( Ω m )) .
As the game is invariant under the group
S d , there exist invariant optimal strategies
for the players. Since for any two
,
∈{
1
,
2
,...,
d
}
there exists a permutation
1
2
σ
2 ,amixedstrategyfor H is invariant if it assigns the same
probability to all elements of
that maps
1 to
Ω
.
The value of the game equals the expected proportion of the number of colors
chosen by the searchers.
Search WWH ::




Custom Search