Extension for Problem Set 3


You can submit Problem set 3 until Feb 27th, 18:30. Late submission until March 3rd at 18:30 will incur penalty of 5 points from the grade of this problem set.

Good luck,


Problem set 2 is online


Problem set 2 is online and due on Sunday, January 13. at 18:30.

The final problem set will be posted in about two weeks.

If you have any difficulties with the material, we will be happy to see you in our office hours. Please use the slides that are posted online.

Good luck,

Regarding question 3 in problem set 1

You can think of deterministic algorithms as follows:

At time t=1, the first bus arrives at one of the resorts (A, B, or C). Moshe then *immediately* learns the location of this bus and must *immediately* send one of his two trucks *from its current location* (recall that one truck is in A and another is in C) to the location of the bus.

At time t=2, a second bus arrives at one of the 3 resorts. If the second bus arrives at the same resort as the first bus then Moshe need not do anything. Otherwise, Moshe has to send his *other* truck to the location of the second bus (the truck sent at time 1 cannot be re-sent). Observe that the algorithm’s decision at t=1 thus fully determines what happens at t=2.

So, a deterministic algorithm simply specifies, for every possible location of the first bus, which truck to send to that location.

(I am deliberately ignoring the case that both busses arrive at the same time as the optimal decision for the algorithm in this case is obvious)

The difference between a randomized algorithm and a deterministic one in this context is that a randomized algorithm can (at time t=1) output a probability distribution (e.g., send truck 1 with probability 1/3 and truck 2 with probability 2/3).

why is there a p such that p=pQ?

In class I showed how a no-swap-regret algorithm can be constructed from a no-external regret algorithm (actually, multiple such algorithms). The construction relies on the fact that for a specific n×n matrix Q (see slides) there exists a vector p such that p=pQ. I was asked after class why such a vector is guaranteed to exist. The reason is that as, by our construction, the sum of the entries in each row add up to 1, Q can be regarded as a transition probability matrix (i.e., where Q_ij is the probability of transitioning from state i to state j). One can therefore think of Q, Q^2, Q^3, … as a (aperiodic) markov chain. Such a chain is known to have a stationary distribution, which is exactly the vector p we’re interested in.