Information Technology Reference
In-Depth Information
neighbors. We say that a player is 'happy' if she chooses a color that is different
from the colors of her neighbors, otherwise she is 'unhappy'. The game reaches a
proper coloring when all players are happy.
We assume that once a player is happy, she chooses the same color in the next
round. Knowing this, players will never choose a color that has been used by a
neighbor in the previous round. Therefore, once a player is happy, she continues to
be happy in all consecutive rounds by sticking to her color, i.e., happiness can only
increase. Note that happy players are essentially removed from the game.
Suppose each player adopts the following strategy: if the player is happy she
sticks to her color, if she is unhappy she changes her color and chooses equiprobably
between the remaining colors that are not used by her neighbors. We call this the
simple
strategy. In [
2
] it is shown that under this strategy the expected number of
unhappy players decays exponentially in each round. Note that the condition
k
≥
Δ
+
2 guarantees that for every unhappy player, there are always at least two colors
that are not chosen by the neighbors.
For an individual player,
v
τ
v
the first round in which she is
happy. The first round in which all players are happy,
∈
V
, denote by
τ
, is the maximum over all
τ
v
.
In particular, the main result of Chaudhuri et al. says that
P
O
log
n
δ
τ
≤
≥
1
−
δ
,
(4.1)
for arbitrary small
. It is remarkable that this estimate does not depend on the max-
imum degree of the network. The proof of this theorem depends on the following
key lemma [
2
, p. 526]
δ
Lemma 1 (Key Lemma).
There exists a constant c such that
P
[
τ
v
≤
t
+
2
|
τ
v
>
t
]
≥
c
,
(4.2)
for every v.
It turns out that the constant
c
according to the estimates of Chaudhuri et al. is
equal to
1
. Also notice that the
estimate is over two rounds instead of one, which is because of a two-step approach
to obtain the constant
c
.
The probability that an unhappy player
v
gets happy after the next round depends
on two factors: the number of colors that
v
can choose from and the number of
unhappy neighbors. Roughly, the proof of the Key Lemma is in two steps. The first
step concerns the event that
v
, who is unhappy after round
t
, gets many available
colors in round
t
050
e
9
. Notice that this estimate does not depend on
Δ
1
.
1. The second step concerns the event that such a
v
that has
many available colors gets happy in round
t
+
2. In both steps the probabilities are
estimated by using Markov's inequality. Now, using the Key Lemma, the main result
in [
2
] is proven by applying the so-called Bayes sequential formula and an union
bound. We also use a two step approach, but we avoid the use of Markov's inequality
(mean estimate), which is rather crude. Instead we use ideas from search games and
bound the probabilities using median estimates, which give much sharper bounds
and allow us to replace the constant
c
in the Key Lemma by
+
1
2
9
.
Search WWH ::
Custom Search