Network Coloring and Colored Coin Games - Search Theory: A Game Theoretic Perspective - page 61

1

3 ( k − h )+ 2
4

that with probability ≥

2 , the cardinality of Z is less than

, by Theorem 2 .

k − f − 2

1
2

k − h − 2

| |≥ ≥

That is, with probability more than we have that Y , since the

4 4

number of happy players can only increase.

τ v is the number of rounds needed for player v to become happy in
the Network Coloring Game.

Recall that

Lemma 5. For every player, v, in the Network Coloring Game we have that

1
2 9 .

P [ τ v ≤ t + 2 | τ v > t ] ≥

Proof. Suppose that v is unhappy after round t has been played. Let Y be the set of
available colors to v after round t 1and f the number of happy neighbors after

this round. So v is choosing a color with probability

+

1

. Suppose that U is the set of

| Y |

unhappy neighbors of v after round t + 1. Thus | U |≤ k − f − 2. For each u ∈ U ,let

be the probability with which player u chooses color i . Define also Y u to be the
set of available colors to each u

p u ( i )

∈ U . From the previous lemma we know that with

k − f − 2

1
2 the cardinality of Y is more than

probability more than . The probability

4

that a fixed color i ∈ Y is not chosen by the neighbors is

∏
{ u ∈ U : i ∈ Y u }

( − ( )) .

1 p u i

Thus the probability P v that v is happy in the next round equals

1
| Y |

1

| i ∈ Y

∏ i ∈ Y ∏

P v =

Y u (

1 − p u ( i )) ≥

Y u (

1 − p u ( i )) ,

| Y

u ∈ U : i ∈ u ∈ U : i ∈

∈

by the arithmetic-geometric mean inequality. For each player in u U that has i as

1

− ( ) − ≥

a choice we have that 1 p u i equals to 1 ,forsome 2. If i is not a choice

1 1

2

of u ∈ U ,then p u ( i )= 0. Thus 1 − p u ( i )= 1 −

Y u | ≥

for every i and so

|

1
| Y |

1
| Y |

i ∈ Y ∏ u ∈ U i ∈ Y u ( 1 − p u ( i ))

Y u (

1 − p u ( i )) ≥

u ∈ U : i ∈

| Y u |

1

1
| Y |

1

u ∈ U

≥ −

| Y u |

1
4 | U |/| Y | ,

≥

k − f − 2

since | Y u |≥ 2. Now on the event | Y |≥ , and since | U |≤ k − f − 2, we find

4

1
4 | U |/| Y | ≥

1
4 4

1
2 8 . The result follows by noticing that P

= [ τ v ≤ t + 2 | τ v > t ] is at least

P P t .

k − f − 2
4

k − f − 2
4

τ v ≤ t + 2 | τ v > t ,| Y |≥ · | Y |≥ | τ v >