A Location Game On Disjoint Circles

size of the newly created red interval (which has the size < 1/bN/K c).¹⁰
Analogically it can be shown that G wins when R creates a red interval
on the group of circles for which dN/Ke key positions are assigned.¹¹ This
completes the proof. ■

Some footnotes used in the proof of the above theorem suggest that
although G, the second mover can win the game, R may be able to make the
difference between their scores arbitrarily small. In the following theorem
we show that the winning strategy Y * for the second mover, with a slight
modification and called Y⁰ , can be used by the first mover R to achieve this
independent of the strategy used by G.

A strategy X is a virtually tying strategy for player p if X is not a
winning strategy and for any ε > 0, if player p uses X , then no matter what
player q does, player p can guarantee that Sq - Sp < ε.

Theorem 7 Let hN, {Cj}_j^K₌₁i define a game on the family of disjoint circles
with N > K ≥ 2 and assume that players face a very strict resource mobility
constraint so that they are allowed to place exactly one point at a time. Then
there is a virtually tying strategy for G.

Proof. Consider strategy Y^* as defined before with option (c) replaced
by option (c’) (this modified strategy will be called Y⁰).

Y 0: Modification of Y * for player R

(c’) place a point in a maximal bichromatic interval at distance ε from

its green endpoint

¹⁰ Notice that the advantage of G may be arbitrarily small and depends on how big the
red interval is.

¹¹Analogical remark on the G’s advantage applies here.

21

<<   21   22   23   24   25   26   27   >>

More intriguing information