Computer Science 789 Online Algorithms

Fall 1999 Assignment 3

Due in class November 18, 1999.

  1. 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.
  2. Consider the buzzer problem. Set it up as a metrical task system.
    1. Draw the offset function game graph. You may ignore nodes that you can prove are useless.
    2. Then, prove matching upper and lower bounds on the competitiveness of this problem, using the potential and anti-potential arguments given in the handouts.
    3. Compute the competitiveness of the work function algorithm for this problem. Is it optimally competitive?

Back to Course Page

Back to Assignment Page