Before revision:  and short-run fairness, where the algorithm is audited for its fairness on a single realization. We focus on the known-IID model of online arrivals and analyze, under both objectives, the competitive ratio for two classes of algorithms: non-rejecting algorithms, which must match an online node as long as a neighbor is available; and general online algorithms , which are allowed to reject online nodes to improve fairness .
After revision:  and short-run . For these fairness objectives, we analyze how competitive online algorithms can be, in comparison to offline algorithms which know the sequence of demands in advance .