Computer Science 789 Online Algorithms
Fall 1999 Assignment 3
Due in class November 18, 1999.
-
Two players, Red and Black, are playing a zero-sum game G.
Some of the possible moves that Red can make are called ``regular,''
and some of the possible moves that Black can make are also
called ``regular.'' Moves that are not regular are called ``bizzare.''
We are trying to solve this game. We think that bizarre moves are never
used, and we have somehow managed to prove the following two lemmas:
Lemma 1: If Red makes only regular moves, then Black can do no
better than to make only regular moves.
Lemma 2: If Black makes only regular moves, then Red can do no
better than to make only regular moves.
Prove that, in solving G, we may ignore bizzare strategies by
both players. More precisely stated: define "regular G"
to be the same as G except that no bizzare strategies are
permitted. Then the value of regular G is the same as
the value of G.
An alternative definition is that, if a player has an optimal
strategy for G, then that player has an optimal strategy
for G that uses no bizzare moves.
-
Consider the buzzer problem.
Set it up as a metrical task system.
-
Draw the offset function game graph.
You may ignore nodes that you can prove are useless.
-
Then, prove matching upper and lower bounds on the competitiveness
of this problem, using the potential and anti-potential arguments given
in the handouts.
-
Compute the competitiveness of the work function algorithm for this
problem. Is it optimally competitive?

Back to
Course Page
Back to
Assignment Page