Beyond competitive analysis

The competitive analysis of online algorithms has been criticized as being too crude and unrealistic. We propose refinements of competitive analysis i n two directions: The rst restricts the power of the adversary by allowing only certain input distributions, while the other allows for comparisons be tween information regimes for online decision-making. We illustrate the rst with an application to the paging problem; as a byproduct we characterize completely the work functions of this important special case of the k-serve r problem. We use the second refinement to explore the power of lookahead i n server and task systems.