A Location Game On Disjoint Circles



red interval of the size 1/dN/Ke.

Consider now stage (c), where both players place their last points. The
following situations are possible after
R places his point in that round: (i)
there are two or more red intervals, or (ii) there is one red interval. Assume
that case (i) holds. Then
G places a point in the largest red interval. If the
size of the newly created red interval was
≥ dN/K e, then the green point
was placed within this interval, as after the stage (b) there is no red interval
of the size
1/dN/Ke. Thus after the last round there is no red interval
of the size
1/dN/K e. Since, also, by Lemma 1, there is the same amount
of green and red intervals and, moreover, each of green intervals is a key
interval (as by strategy
Y*, G never created a green interval apart from the
first stage), so
G must be winning (recall that the size of a key interval is
1/dN/Ke).9

Now assume that case (ii) holds. Consider the situation before R’s move.
It must be that there is no red interval. Consider the group of circles for
which
dN/Ke key positions are assigned. It cannot be that R has more
points than
G on these circles (as otherwise, by Lemma 1 there would be
a red interval there). Similarly
R cannot have more points on the group of
the circles with
bN/Kc key positions assigned. Thus on each such group of
circles, classified by the number of key positions,
G and R have the same
number of points. Suppose that after
R’s move, a red interval is created in
the group of circles for which
bN/K c key positions are assigned (notice that
such red interval may have the size
1/dN/Ke). Then, by Lemma 2, there
must be a bichromatic key interval in that group of circles (i.e. a bichromatic
key interval of the size 1
/bN/Kc). Thus G can win by placing a point in
that key interval and creating a green interval of the size bigger than the

9Notice that G’s advantage may be arbitrarily small, as non-key intervals created by
R may be arbitrarily close in size to that of key intervals.

20



More intriguing information

1. Auction Design without Commitment
2. Bridging Micro- and Macro-Analyses of the EU Sugar Program: Methods and Insights
3. The Global Dimension to Fiscal Sustainability
4. The name is absent
5. Secondary stress in Brazilian Portuguese: the interplay between production and perception studies
6. Palvelujen vienti ja kansainvälistyminen
7. The name is absent
8. Segmentación en la era de la globalización: ¿Cómo encontrar un segmento nuevo de mercado?
9. Biological Control of Giant Reed (Arundo donax): Economic Aspects
10. Automatic Dream Sentiment Analysis