Proof of `Online scheduling as a game` (5th statement)
groundedproofs/Lax434175Proofs/Online.lean · lax-434175
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
The expected excess of the randomized algorithm over the distribution is positive when the algorithms are averaged first, and at most zero when the instances are averaged first.