Information Technology Reference
In-Depth Information
Lemma 3.
There exists an optimal pure strategy in which all searchers use a
doubleton.
Proof.
Any searcher,
S
j
, picks a color uniformly randomly from his own
Ω
j
,i.e.
1
|
Ω
j
|
with probability
j
uniformly
randomly and then equiprobably choose one of the two colors from that doubleton.
This means that every pure strategy of
S
j
is equivalent to a mixed strategy on (some)
doubletons. Now we prove that it is optimal for each searcher to choose one double-
ton. Since the game is finite, there exists an optimal mixed strategy for the searchers
which can be described by a probability distribution on doubletons (pure strategies).
Fix some searcher, say
S
1
, and suppose that he chooses a collection of doubletons,
D
1
,
. It is equivalent to first pick a doubleton from
Ω
p
k
that add up to 1. Let,
P
, denote the
winning probability of the searchers. Then
P
D
2
,...,
D
k
with probabilities
p
1
,
p
2
,...,
p
i
P
i
,where
P
i
denotes the prob-
ability that the searchers win, given that
S
1
chooses
D
i
and the other searchers do
not change their strategy. Choose an
i
0
for which
P
i
0
=
=
∑
p
i
P
i
.
This means that there is a doubleton such that if it is chosen by
S
1
, the expected
payoff does not decrease, provided that the rest of the searchers do not change their
strategy.
max
i
P
i
.Then
P
i
0
≥
∑
Theorem 1.
If
2
m
=
ad
+
b, for integers a and
0
<
b
<
d, then the value of the game
b
2
a
+
1
d
.
Proof.
Clearly, it is optimal for the searchers to use coins that contain every color
at least once. Let
Z
be the set of colors chosen by the searchers after flipping
their coins, let
X
d
,
m
=
|
2
d
−
equals
.Thatis,
X
d
,
m
is the number of different colors after
a toss. The value of the game is equal to the expected proportion of the com-
plement of
Z
,
Z
|
E
[
|
Z
c
E
[
X
d
,
m
d
. Fix some strategy,
s
, of the searchers, let
G
s
be the set of colors corresponding to this strategy and let
C
i
be the event that
color
i
is chosen by the searchers after they toss their coins. Note that
|
]
=
1
−
d
|
G
s
|
=
d
.
1
c
(
i
)
Then
E
is the number of
times that color
i
appears on a coin. The searchers seek to minimize the sum
∑
[
X
d
,
m
]=
∑
i
∈
G
s
P
[
C
i
]=
∑
i
∈
G
s
(
1
−
(
2
)
)
,where
c
(
i
)
G
s
2
c
(
i
)
under the constraint
∑
i
c
(
i
)=
2
m
. Note that whenever
l
−
j
≥
2then
i
∈
2
l
+
2
j
+
1
. Iteration of this inequality shows that the mini-
mum is achieved by choosing
G
s
such that all
c
+
2
j
≥
2
l
−
1
(
i
)
,
i
∈
G
s
, are as equal as possi-
ble, i.e.
b
of them equal to
a
+
1 and the remaining
d
−
b
equal to
a
.Thenweget
G
s
2
c
(
i
)
b
2
a
+
1
d
−
b
2
d
b
2
a
+
1
.
−
=
+
=
∑
i
∈
2
a
4.3 Maximizing the Median
Picking an element from a doubleton is just flipping a coin and so the searchers
are using
d
colors to create
m
coins that do not use the same color on both sides.
Note that for each array of coins used by the searchers, one can draw a
graph
whose vertices correspond to the colors and whose edges correspond to the coins.
Search WWH ::
Custom Search