Making Online Predictions from K-Lists

We explore the problem of combining the heads of k lists, each of size n, into a single prediction of size n. We present a deterministic algorithm and a bound for the noise-free case, when we know that there is some consistent partition of the k-lists that makes no mistakes. For the noisy case, we describe a randomized algorithm and the corresponding bound. If switching between partitions has a cost, a deterministic algorithm may perform better than a randomized one. We discuss our search for a deterministic algorithm that has a similar bound. We also describe the problem as a Metrical Task Problem to account for the cost of switching between partition predictions. 1