In an online problem the instance is revealed over time, and a schedule must be fixed as time passes. A revelation of a problem says, for every time $t \ge 0$, which instances look the same to the scheduler at time $t$, and which schedules of two instances have made the same decisions up to time $t$.

The competitive-ratio game is played by the scheduler and an adversary. The scheduler chooses an algorithm, a schedule for every instance, which must be non-anticipative: on two instances that look the same at time $t$ it makes the same decisions up to time $t$. The adversary then chooses an instance. For a ratio $\rho$ and an additive constant $\alpha$, the scheduler wins if its schedule is feasible and costs at most $\rho$ times the cost of every feasible schedule of the instance, plus $\alpha$; otherwise the adversary wins. An algorithm with which the scheduler always wins is $(\rho, \alpha)$-competitive.

A randomized algorithm is a finite probability distribution over non-anticipative algorithms; it is $(\rho, \alpha)$-competitive if all its algorithms schedule every instance feasibly and its expected cost is at most $\rho$ times the cost of every feasible schedule, plus $\alpha$. A distribution over instances, each with a feasible schedule as witness, defeats the ratio if every non-anticipative algorithm schedules some instance of it infeasibly or has positive expected excess, the cost minus $\rho$ times the witness's cost minus $\alpha$.

An embedding of one problem into another is causal for two revelations if instances that look the same at time $t$ are mapped to instances that look the same at time $t$, and schedules that made the same decisions up to time $t$ are translated back to schedules that made the same decisions up to time $t$.

Theorem.

1. The game is determined: the adversary wins against every non-anticipative algorithm exactly if the scheduler has no winning algorithm.
2. A deterministic competitive algorithm is a randomized one.
3. (Yao's principle, the direction used for lower bounds.) If a distribution over instances defeats a ratio, no randomized algorithm has that ratio.
4. Along a sound causal embedding of $A$ into $B$ and for $\rho \ge 0$, a $(\rho, \alpha)$-competitive algorithm for $B$ yields one for $A$, so that lower bounds pass from $A$ to $B$.