Stopping Times and Online Algorithms

Contents

• Introduction and overview
• 0. Review: maxima, conditioning, linear programming and matchings
• 1. Online algorithms and competitive analysis
• 2. Stopping times and the secretary problem
• 3. Prophet inequalities
• 4. Pandora’s box, posted prices and online auctions
• 5. Online bipartite matching
• 6. Budgets: b-matching, AdWords, resource allocation and delays
• 7. Paging, caching and metrical task systems
• 8. The k-server problem and tree reductions
• 9. Convex body chasing and online transportation
• 10. Research directions and open problems
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: a student with an M1 in mathematics, computer science or economics who is at ease with probability and linear programming, and who wants to learn how to decide when to act while the data arrive one at a time.

Empirical first: interview 100 candidates in a uniformly random order and hire on the spot or never. Rejecting the first 37 and then taking the first candidate better than all of them hires the very best one 37.1 % of the time, and 37.0 % of 100,000 simulated orders agree. On a ski trip of unknown length, renting until the rent paid reaches the price of the skis and then buying never costs more than twice the hindsight optimum. This course explains both numbers, and many more of the same kind.

The course studies algorithms that discover the data one item after the other and must commit at once, with decisions that weigh on the future: a budget spent, a vertex matched, a server moved. Their quality is measured against an offline optimum that knows everything in advance. The three families of problems are stopping problems (secretaries, prophets, Pandora’s boxes), online matching and allocation, and metrical task systems such as paging and the k-server problem. The tools are linear programming duality, stochastic approximation and reductions to trees.

It sits at the junction of probability, theoretical computer science and economics. It shares bandits and regret with Sequential Learning and dynamic programming with Reinforcement Learning. LP duality and mirror descent come from Convex Optimization, and the transport problem from Optimal Transport for Machine Learning.

What you will be able to do

• Define an online problem, its offline optimum and the competitive ratio of a deterministic or randomized algorithm, and tell it apart from the regret of online learning.
• Prove upper bounds by potential functions and by weak LP duality, and lower bounds with adversarial inputs and Yao’s principle.
• Solve finite-horizon optimal stopping problems by backward induction, and the secretary problem in its classical, LP and odds forms.
• State and prove the prophet inequality with the factor 1/2, its i.i.d. version with 1 − 1/e, and an online contention resolution scheme.
• Derive Weitzman’s index policy for Pandora’s box, and turn stopping rules into posted-price mechanisms for online auctions.
• Analyse greedy and RANKING for online bipartite matching, and the AdWords algorithm, with a randomized or deterministic primal–dual argument.
• Learn dual prices online by stochastic approximation to allocate budgets under stochastic arrivals.
• Analyse LRU, FIFO and marking for paging, define metrical task systems and compute work functions.
• Prove the k lower bound for k-server and the k-competitiveness of Double Coverage on the line, and use tree embeddings to reduce a metric problem to trees.
• Describe convex body chasing and online metric matching, and read current research papers on online decision making.

Official objectives and syllabus (2026–2027)

The course description on master-mva.com sets the objective of understanding and mastering how to take sequential decisions that may have a strong impact on the future, typically the depletion of a budget, at the junction of mathematics, theoretical computer science and economics. The goal is to construct and analyse algorithms that discover, then treat, data one after the other rather than as a whole batch.

The quality of a sequence of decisions is compared with the optimal decisions that know everything in advance. The description announces three typical cases (prophet inequalities, online matching, metrical task systems), the main techniques (linear optimisation, stochastic approximation, tree reductions), as many open questions as possible, and a disclaimer separating online algorithms from online learning. Classes are taught on the blackboard. The Université Paris-Saclay course detail displays only the nature of the assessment.

Extensions beyond the syllabus: Yao’s principle and the randomized ski rental (ch. 1), the odds theorem (ch. 2.3), online contention resolution (ch. 3.5), Myerson’s virtual values (ch. 4.3) and the research chapter (ch. 10, self-study).

Where this course fits in the programme

Official prerequisites: none (“the course is more or less self-contained”). In practice, the proofs use discrete probability, conditional expectation and linear programming duality at M1 level, recalled in ch. 0.

• Refreshers — Probability and Statistics (conditional expectation; its chapter on martingales and stopping times), Linear Algebra, Analysis and Optimization (linear programming and duality) and Scientific Python (NumPy and SciPy for every Python block).
• Semester 1 courses that prepare it — Convex Optimization and Applications in Machine Learning (duality, mirror descent), Optimal Transport for Machine Learning (the offline transport problem behind ch. 9.2) and Stochastic Calculus in Machine Learning (stopping times in continuous time).
• Related courses of semester 2 — Sequential Learning (bandits and regret, the other side of the disclaimer of ch. 1.4), Reinforcement Learning (dynamic programming), Algorithms for Network Optimization and Management (online admission control), Detection Theory and Industrial Applications (sequential detection rules are stopping times) and Interactions: Complexity, Stochasticity, Extrema and Rare Events (maxima of random sequences).
• After the course — the Research Internship; the open problems of ch. 10 are typical internship subjects in theoretical computer science and algorithmic economics.

Course outline

• Review: maxima, conditioning, linear programming and matchings — the expectation of a maximum, independence of the future, weak duality, maximal matchings and metrics.
• Online algorithms and competitive analysis — the online model, the competitive ratio, ski rental, Yao’s principle, and why this is not online learning.
• Stopping times and the secretary problem — filtrations, backward induction, the 1/e law, its LP and the odds theorem.
• Prophet inequalities — the factor 1/2 and its proof, i.i.d. values and 1 − 1/e, random order, the ex-ante LP and contention resolution.
• Pandora’s box, posted prices and online auctions — Weitzman’s index, its short proof, and stopping rules turned into prices.
• Online bipartite matching — greedy, RANKING and its randomized primal–dual proof, and the matching upper bound.
• Budgets — b-matching, AdWords, online resource allocation with learned dual prices, and matching with delays.
• Paging, caching and metrical task systems — Belady, LRU, marking, and the general model with work functions.
• The k-server problem and tree reductions — the k lower bound, Double Coverage, the work function algorithm, HST embeddings.
• Convex body chasing and online transportation — chasing in high dimension, and online metric matching.
• Research directions and open problems — the open constants, learning-augmented algorithms and the bridges with online learning (self-study).

Session plan

24 h in class = 8 sessions of 3 h.

The volume is the 24 h of lectures of the Université Paris-Saclay programme table. master-mva.com announces “7 (or 8) courses of 3h” in a blackboard research course; the split below into 8 sessions is a proposal, and with 7 sessions the material of session 8 becomes self-study.

Level 1 = foundations, 2 = core results and algorithms, 3 = advanced and research-level material; the level never decreases.

Self-study, outside the 24 h (about 5 h in total): ch. 10 Research directions and open problems (≈ 3 h, with Ex. 15 and 17) · running and modifying the Python blocks of the in-class chapters (≈ 2 h).

How to study this module

• Read ch. 0 before session 1: the inequality on the expectation of a maximum and weak duality are used in almost every proof.
• Keep the three questions of the course in mind for every problem: what the offline optimum is, which algorithm is proposed, and which input makes every algorithm fail.
• Redo each central proof on paper after the session (Theorems 2.2, 3.2, 4.2, 5.3, 6.3, 7.2, 8.2 and 8.3); the written exam is likely to ask for one of them.
• Run the Python block of each chapter and change one parameter: the size of the input, the order of arrivals, the threshold.
• The environment is NumPy and SciPy, whose linprog (HiGHS solver) computes the offline LP optima; nothing else is needed.
• Do the ★ exercises the week of the session and the ★★ proofs before the exam; the ★★★ exercises and ch. 10 point to research questions.

0. Review: maxima, conditioning, linear programming and matchings

Every proof of the course compares an online algorithm with an omniscient optimum. This chapter gathers the M1-level tools of those comparisons: the expectation of a maximum, the independence of the future, weak LP duality, matchings and metrics.

0.1 Expectations of maxima

0.2 Independence of the future

An online algorithm decides at step i with what it saw before. With independent values, “still active at step i” says nothing about X_i.

0.3 Linear programming and weak duality

Weak duality drives the primal–dual method of ch. 5 and 6: an online algorithm builds a primal solution and a dual one of value at most c times larger. If the dual is feasible, it bounds the optimum, and the algorithm is 1/c-competitive.

0.4 Maximal matchings and metric spaces

A metric space (X, d) is a set with a distance that is symmetric, zero exactly on the diagonal and satisfies the triangle inequality. The servers of ch. 8 and the requests of ch. 9 live in such spaces; the line, with d(x, y) = |x - y|, and the uniform metric, with all distances equal to 1, are the two running examples.

1. Online algorithms and competitive analysis

An online algorithm receives its input one piece at a time and must answer each piece before seeing the next. This chapter defines how such an algorithm is judged, solves the simplest non-trivial example, ski rental, and gives the standard tool for lower bounds.

1.1 The online model

Ratios are above 1 for costs (paging, k-server) and below 1 for gains (prophets, matching). Against an adaptive offline adversary, who sees the coins as they fall, randomization brings nothing (Ben-David, Borodin, Karp, Tardos and Wigderson, 1994).

1.2 Ski rental

Renting skis costs 1 per day and buying them costs B days of rent. The trip lasts d days, unknown in advance, and the skier learns each morning whether the trip goes on. The offline optimum is \mathrm{OPT}(d) = \min(d, B).

A deterministic algorithm is a day k on which to buy if the trip is still going. It pays d if d < k, and k - 1 + B otherwise.

Randomization helps. In continuous time, buy at a random time t \in [0, B] with density p(t) = \frac{e^{t/B}}{B\,(e - 1)} . For a trip of length d \leq B, the expected cost is \int_0^d (t + B)\, p(t)\, dt + d \int_d^B p(t)\, dt = \frac{e}{e-1}\, d , by an integration by parts, and for d > B it is the value at d = B. The ratio e/(e - 1) \approx 1.582 is optimal (Karlin, Manasse, McGeoch and Owicki, 1994); the lower bound comes from the principle below.

1.3 Yao’s principle

A randomized lower bound thus only needs one distribution of hard inputs. Exercise 8 applies it to ski rental with B = 2, where the optimal randomized ratio is 4/3.

import numpy as np
from scipy.optimize import linprog

B = 10                      # price of the skis, in days of rent
days = np.arange(1, B + 1)  # d >= B behaves like d = B (OPT = B)

def cost(k, d):             # buy on the morning of day k, ski for d days
    return d if d < k else (k - 1) + B

def opt(d):
    return min(d, B)

# Deterministic: worst-case ratio of "buy on day k"
for k in [1, 5, B, 15]:
    worst = max(cost(k, d) / opt(d) for d in range(1, 3 * B))
    print(f"buy on day {k:2d}: worst ratio {worst:.3f}")

# Randomized: the best distribution over k = 1..B solves an LP
# variables (p_1..p_B, c); minimise c s.t. E[cost(d)] <= c * opt(d) for all d
A, b = [], []
for d in days:
    A.append([cost(k, d) for k in days] + [-opt(d)])
    b.append(0.0)
res = linprog(c=[0] * B + [1], A_ub=A, b_ub=b,
              A_eq=[[1] * B + [0]], b_eq=[1], bounds=[(0, None)] * (B + 1), method="highs")
p, ratio = res.x[:B], res.x[B]
print("optimal randomized ratio:", round(ratio, 4))
print("closed form 1/(1-(1-1/B)^B):", round(1 / (1 - (1 - 1 / B) ** B), 4), " limit e/(e-1):", round(np.e / (np.e - 1), 4))
print("p_k ratios p_{k+1}/p_k:", np.round(p[1:] / p[:-1], 4)[:4])

With B = 10, buying on day 10 has worst ratio 1.900, while buying on day 1 or day 15 is far worse. The LP over distributions of the buying day returns 1.5353, the discrete form of e/(e-1): \frac{1}{1 - (1 - 1/B)^B} = 1.5353 . The optimal probabilities grow geometrically, by the factor 1/(1 - 1/B) per day, the discrete twin of the density p(t).

1.4 Online algorithms are not online learning

The course description insists on a disclaimer: online algorithms are related to online learning and bandits, but the question is when to make a decision rather than which decision to make.

• Online learning repeats the same decision problem. The benchmark is the best fixed action in hindsight, decisions do not change future problems, and regret grows sublinearly (see Sequential Learning).
• Online algorithms carry a state: a budget spent, a vertex matched, a server position. The benchmark is the best sequence of decisions in hindsight, with a multiplicative guarantee on every input.

In ski rental there is no fixed action to learn: the whole problem is one decision of when to buy. Bridges exist all the same, and ch. 6.3 and ch. 8.4 use online convex optimization inside online algorithms.

2. Stopping times and the secretary problem

A stopping problem asks for the best moment to take an irrevocable action while information keeps arriving. This chapter solves it by backward induction and applies the method to the secretary problem.

2.1 Filtrations and stopping times

The first time X_t exceeds a fixed threshold is a stopping time. The time of the overall maximum is not, since recognizing it requires later values; the prophet of ch. 3 is the player allowed to use it.

2.2 Backward induction

Let Y_t be the reward for stopping at time t, a function of X_1, \dots, X_t, with \mathbb{E}|Y_t| < \infty. The problem is to maximize \mathbb{E}[Y_\tau] over stopping times \tau \leq n.

The process (V_t), the Snell envelope, is the smallest supermartingale above (Y_t).

When the X_t are independent and non-negative and Y_t = X_t, the conditional expectations are constants. With v_{n+1} = 0, the values satisfy v_t = \mathbb{E}\big[\max(X_t,\ v_{t+1})\big], and the optimal rule stops at the first t with X_t \geq v_{t+1}, a sequence of decreasing thresholds.

2.3 The secretary problem

The threshold rule is optimal among all stopping rules. Call candidate i a record if it beats everybody before it; the indicators of records are independent, with probabilities 1/i (Rényi). A record at position i is the overall best with probability i/n, increasing in i, while the value of continuing decreases, so backward induction stops at the first record after a fixed position.

The same structure solves a larger family. Bruss’s odds theorem (2000) considers independent events I_1, \dots, I_n of probabilities p_j and odds r_j = p_j / (1 - p_j), and the goal of stopping on the last event that occurs. The optimal rule stops at the first event from index s on, where s is the largest index with \sum_{j \geq s} r_j \geq 1 . It wins exactly when one event occurs among I_s, \dots, I_n, with probability \prod_{j \geq s}(1 - p_j) \sum_{j \geq s} r_j, and this probability is at least 1/e whenever the total odds reach 1 (Bruss, 2003). Records give p_j = 1/j and recover Theorem 2.5.

2.4 The secretary problem as a linear program

Buchbinder, Jain and Singh (2014) write every stopping rule as a point of a polytope. Let x_i be the probability that a rule hires the candidate at position i. Hiring candidate i requires that nobody was hired before and that i is a record, two independent events, so x_i \leq \frac{1}{i} \Big(1 - \sum_{j < i} x_j\Big). A rule that only hires records wins with probability \sum_i (i/n)\, x_i. Conversely, every feasible x is realized by the rule that hires a record at position i with the right conditional probability.

import numpy as np
from scipy.optimize import linprog

n = 100

def success(r, n):          # reject the first r-1, then take the first record
    if r == 1:
        return 1 / n
    return (r - 1) / n * sum(1 / (i - 1) for i in range(r, n + 1))

r_star = max(range(1, n + 1), key=lambda r: success(r, n))
print(f"n={n}: best r = {r_star}, P(best) = {success(r_star, n):.4f}, 1/e = {1/np.e:.4f}")

# The LP of Buchbinder, Jain and Singh: x_i = P(select the i-th candidate)
#   max sum_i (i/n) x_i   s.t.   i * x_i + sum_{j<i} x_j <= 1,  x >= 0
A = np.tril(np.ones((n, n)), -1) + np.diag(np.arange(1, n + 1))
res = linprog(-np.arange(1, n + 1) / n, A_ub=A, b_ub=np.ones(n),
              bounds=[(0, None)] * n, method="highs")
x = res.x
print(f"LP value = {-res.fun:.4f}; first index with x_i > 0: {np.argmax(x > 1e-9) + 1}")

# Monte Carlo check of the threshold rule
rng = np.random.default_rng(0)
trials, wins = 100_000, 0
for _ in range(trials):
    ranks = rng.permutation(n)          # rank 0 = best candidate
    best_seen = ranks[: r_star - 1].min()
    later = ranks[r_star - 1:]
    pick = later[np.argmax(later < best_seen)] if (later < best_seen).any() else None
    wins += (pick == 0)
print(f"simulated success: {wins / trials:.4f}")

For n = 100, the best rule rejects the first 37 candidates and wins with probability 0.3710, slightly above 1/e. The LP returns the same value, positive from position 38 on, and 100,000 simulated orders give 0.3703.

3. Prophet inequalities

A gambler sees independent values one at a time and may stop once; a prophet sees them all and takes the largest. This chapter shows that a stopping rule secures half of the prophet’s expected gain in general, and 1 - 1/e for identically distributed values.

3.1 The gambler and the prophet

The course description writes the ratio as \mathbb{E}[X_\tau] / \max_i X_i; the standard benchmark is the expectation of the maximum. Backward induction (Theorem 2.2) gives the optimal gambler, but its value is hard to compare with the prophet. Threshold rules, which stop at the first X_i \geq T, are easier to analyse and nearly as good.

3.2 The factor one half

The rule with T = \mathbb{E}[\max]/2 needs only one number about the distributions, a robustness that matters for the auctions of ch. 4.

3.3 Identically distributed values

For i.i.d. values, a single threshold already does better than 1/2.

Adaptive thresholds do even better in the i.i.d. case. Hill and Kertz (1982) began the study of the optimal i.i.d. constant, Kertz (1986) identified the candidate value \approx 0.745, and Correa, Foncea, Hoeksma, Oosterwijk and Vredeveld (2017) proved that it is the exact worst-case ratio of the optimal gambler.

3.4 Random order: the prophet secretary

In the prophet secretary, the distributions differ but the values arrive in a uniformly random order. Esfandiari, Hajiaghayi, Liaghat and Monemizadeh (2015) reached 1 - 1/e with decreasing thresholds, and Correa, Saona and Ziliotto (2019) went beyond it with “blind” strategies. The optimal constant is open, as in the free order model, where the gambler chooses the order.

3.5 The ex-ante relaxation and contention resolution

The linear-optimisation view of ch. 2.4 also bounds the prophet. Let x_i be the probability that the prophet takes X_i, so that \sum_i x_i \leq 1.

For continuous distributions, among all events of probability x_i, the one that maximizes the expected gain from X_i is “X_i lies in its top x_i-quantile”; call r_i(x_i) that gain. This gives the ex-ante relaxation: \mathbb{E}\big[\max_i X_i\big] \leq \max \Big\{ \sum_{i=1}^n r_i(x_i) : \sum_i x_i \leq 1,\ x \geq 0 \Big\}.

An online algorithm then tries to select each i with probability close to x_i. Call i active if X_i falls in its top x_i-quantile.

Feldman, Svensson and Zenklusen (2016) extend contention resolution to matroids, matchings and knapsacks, the route to prophet inequalities for many items.

import numpy as np

n = 3                        # X_1, X_2, X_3 i.i.d. uniform on [0, 1]
E_max = n / (n + 1)

# Optimal gambler (backward induction of ch. 2.2): v_n = 1/2, v_t = E[max(U, v_{t+1})]
v = 0.5
for _ in range(n - 1):
    v = (1 + v ** 2) / 2
print(f"prophet E[max] = {E_max:.4f}, optimal gambler = {v:.4f}, ratio {v / E_max:.3f}")

def threshold_value(T):      # E[X_tau] for 'stop at the first X_i >= T'
    return (1 - T ** 2) / 2 * sum(T ** i for i in range(n))

rules = {"T = E[max]/2": E_max / 2,
         "median of max": 0.5 ** (1 / n),
         "P(X >= T) = 1/n": 1 - 1 / n}
Ts = np.linspace(0, 1, 100_001)
rules["best single T"] = Ts[np.argmax(threshold_value(Ts))]
for name, T in rules.items():
    print(f"{name:16s} T = {T:.4f}  E[X_tau] = {threshold_value(T):.4f}  ratio {threshold_value(T) / E_max:.3f}")

# Ex-ante LP + online contention resolution scheme (OCRS), by simulation
rng = np.random.default_rng(1)
x = np.full(n, 1 / n)                       # LP solution (symmetric)
LP = n * (x[0] - x[0] ** 2 / 2)             # sum_i E[X_i ; X_i >= 1 - x_i]
X = rng.random((200_000, n))
gain = np.zeros(len(X))
free = np.ones(len(X), dtype=bool)
for i in range(n):
    active = X[:, i] >= 1 - x[i]
    accept = rng.random(len(X)) < 1 / (2 * (1 - x[:i].sum() / 2))
    take = free & active & accept
    gain[take] = X[take, i]
    free &= ~take
print(f"ex-ante LP = {LP:.4f} >= E[max]; OCRS value = {gain.mean():.4f} (LP/2 = {LP / 2:.4f})")

The run confirms Example 3.4. The 1/n-quantile threshold of Theorem 3.5 gets 0.782 of the prophet, above its guarantee 0.704, and the best single threshold, T \approx 0.455, gets 0.879. The ex-ante LP is worth 5/6, and contention resolution collects half of it, 0.416: weak here, but robust to combinatorial constraints.

4. Pandora’s box, posted prices and online auctions

In Pandora’s problem, the decision maker chooses which value to inspect next and pays for each inspection. This chapter derives the optimal policy, then turns stopping rules into prices, the modern motivation of prophet inequalities.

4.1 Pandora’s box

The reservation value is the price at which Pandora is indifferent between holding a sure value \sigma_i and paying c_i to see whether the box beats it.

The reservation value of a box depends on that box only. Variants break this: when Pandora may take a box without opening it (Doval, 2018; Beyhaghi and Kleinberg, 2019), index-based policies only approximate the optimum.

4.2 From stopping rules to posted prices

A seller has one item and buyers arrive one by one, with independent private values V_i \sim F_i. The seller posts a price p_i to buyer i, who buys if V_i \geq p_i. One price T for everybody is the threshold rule of ch. 3, seen from the buyers’ side.

• Welfare. By Theorem 3.2, the price T = \mathbb{E}[\max_i V_i]/2 gives the item to a buyer worth at least half the best one in expectation, the welfare of an auction with all buyers present (Hajiaghayi, Kleinberg and Sandholm, 2007).
• Simplicity. Each buyer faces a take-it-or-leave-it offer, so truth-telling is trivial and buyers need not be present together (Lucier, 2017).

4.3 Revenue and virtual values

For revenue, Myerson’s theory supplies the right variables. Let F_i have a density f_i and define the virtual value \varphi_i(v) = v - \frac{1 - F_i(v)}{f_i(v)} . The distribution is regular if \varphi_i is non-decreasing.

Apply the prophet inequality to the independent variables \varphi_i(V_i)^+. A threshold T on virtual values is the price \varphi_i^{-1}(T) for buyer i, and its revenue is the virtual value it collects. Chawla, Hartline, Malec and Sivan (2010) deduce that sequential posted prices earn half the optimal revenue, and extend this to several items.

import numpy as np
from scipy.optimize import brentq

rng = np.random.default_rng(2)
N = 400_000
# Box 1: V ~ U[0,1], cost 0.08.  Box 2: V = 2 w.p. 1/2, else 0, cost 0.4.
samplers = [lambda m: rng.random(m), lambda m: 2.0 * (rng.random(m) < 0.5)]
costs = np.array([0.08, 0.4])
excess = [lambda s: max(1 - s, 0) ** 2 / 2, lambda s: 0.5 * max(2 - s, 0)]   # E[(V - s)^+]
sigma = np.array([brentq(lambda s, i=i: excess[i](s) - costs[i], 0, 2) for i in range(2)])
print("reservation values sigma =", np.round(sigma, 4))

V = np.column_stack([f(N) for f in samplers])

def run(order):              # open in 'order', stop when best >= max remaining sigma
    best, paid = np.zeros(N), np.zeros(N)
    stopped = np.zeros(N, dtype=bool)
    for j, i in enumerate(order):
        rest = sigma[order[j:]].max()
        stopped |= best >= rest
        go = ~stopped
        paid[go] += costs[i]
        best[go] = np.maximum(best[go], V[go, i])
    return (best - paid).mean()

print(f"Weitzman order {np.argsort(-sigma) + 1}: utility {run(np.argsort(-sigma)):.4f}")
print(f"reverse order: utility {run(np.argsort(sigma)):.4f}")
kappa = np.minimum(V, sigma)
print(f"E[max capped value] = {kappa.max(axis=1).mean():.4f}")

# Posted prices for one item and two buyers with values U[0,1]
p = np.linspace(0, 1, 100_001)
single = p * (1 - p ** 2)                          # same price for both buyers
adaptive = p * (1 - p) + p * 0.25                  # price p, then 1/2 to buyer 2
print(f"one price: best p = {p[single.argmax()]:.4f}, revenue {single.max():.4f}")
print(f"two prices: best p1 = {p[adaptive.argmax()]:.4f}, revenue {adaptive.max():.4f}")
print(f"Myerson optimal auction revenue = {5 / 12:.4f}")

The simulation recovers the reservation values 0.6 and 1.2, a utility of 0.809 for Weitzman’s order against 0.769 for the reverse order, and \mathbb{E}[\max_i \kappa_i] = 0.810; the pricing part reproduces Example 4.5.

5. Online bipartite matching

In online matching, one side of a bipartite graph is known and the other arrives vertex by vertex, each matched at once or never. Deterministic algorithms lose half of the optimum; one random permutation recovers 1 - 1/e.

5.1 The model

In advertising, offline vertices are advertisers, online vertices are queries, and an edge means the ad is relevant.

5.2 Greedy and its limit

A uniformly random free neighbour does not fix this: on some graphs that rule matches only about half of the optimum (Karp, Vazirani and Vazirani, 1990).

5.3 RANKING

RANKING (Karp, Vazirani and Vazirani, 1990) draws one random order of U at the start and matches every arriving vertex to its free neighbour of highest priority. Equivalently, each u \in U draws y_u uniform on [0, 1], independently, and smaller y_u means higher priority.

import numpy as np

rng = np.random.default_rng(3)
n, h, trials = 200, 100, 200

def trap():
    """v_i ~ u_i for all i; the first h online vertices also see u_h, ..., u_{n-1}."""
    return [np.r_[i, np.arange(h, n)] if i < h else np.array([i]) for i in range(n)]

def upper_triangular():
    """v_j sees u_pi(j), ..., u_pi(n-1) for a hidden random relabelling pi."""
    pi = rng.permutation(n)
    return [pi[j:] for j in range(n)]

def run(neigh, rule):
    rank = rng.permutation(n)          # used by RANKING only, drawn once
    matched, size = np.zeros(n, dtype=bool), 0
    for nb in neigh:                   # online vertices arrive one by one
        free = nb[~matched[nb]]
        if len(free) == 0:
            continue
        if rule == "greedy":           # a deterministic greedy rule
            u = free.max()
        elif rule == "random":         # uniformly random free neighbour
            u = rng.choice(free)
        else:                          # RANKING: smallest rank
            u = free[np.argmin(rank[free])]
        matched[u], size = True, size + 1
    return size

for name, make in [("trap", trap), ("upper triangular", upper_triangular)]:
    res = {r: np.mean([run(make(), r) for _ in range(trials)]) / n
           for r in ["greedy", "random", "ranking"]}
    print(f"{name:17s}", "  ".join(f"{r} {v:.3f}" for r, v in res.items()))
print(f"1 - 1/e = {1 - 1 / np.e:.3f}")

On the trap, early vertices may take shared vertices that late vertices need. Greedy, which prefers them, matches 0.500 of the optimum and the random rule 0.517, while RANKING reaches 0.684. On the graph of Proposition 5.4, all three are stuck at 0.633, the bound 1 - 1/e up to finite-size effects.

5.4 Beyond the adversary

The bound 1 - 1/e is a worst case over both the graph and the arrival order. Weaker adversaries allow more.

• Random order. Goel and Mehta (2008) show that greedy is (1 - 1/e)-competitive when the online vertices arrive in random order, and Mahdian and Yan (2011) show that RANKING then reaches at least 0.696.
• Known i.i.d. arrivals. When online vertices are drawn from a known distribution, Feldman, Mehta, Mirrokni and Muthukrishnan (2009) beat 1 - 1/e by solving offline the expected instance and following two matchings computed from it.
• Open questions. The exact random-order ratio of RANKING, and the best ratios when both sides arrive online, are open (ch. 10).

6. Budgets: b-matching, AdWords, resource allocation and delays

In advertising, an offline vertex is an advertiser matched many times until a budget runs out: spending now leaves less for later. This chapter extends ch. 5 to capacities and bids, then studies learned prices and matching with delays.

6.1 b-matching and BALANCE

In b-matching, each offline vertex can be matched up to b times. Greedy is still 1/2-competitive (Exercise 10). BALANCE matches each arriving vertex to the neighbour that has used the smallest fraction of its capacity.

Large capacities let a deterministic algorithm match what RANKING achieves with randomness for b = 1.

6.2 AdWords

Greedy, which gives each query to the highest remaining bid, is 1/2-competitive. Mehta, Saberi, Vazirani and Vazirani (2007) trade off bid and spent fraction f_u: give q to the advertiser that maximizes b_{uq}\, \psi(f_u), \qquad \psi(f) = 1 - e^{f - 1} .

The same LP with unit bids and budgets b is b-matching, and the rule becomes BALANCE. Aggarwal, Goel, Karande and Mehta (2011) handle weights on the offline vertices, with one bid per advertiser, by perturbing RANKING’s priorities with \psi.

6.3 Online resource allocation by stochastic approximation

In practice, a campaign spreads its budget over the day, and queries look like i.i.d. draws from an unknown distribution. The dual of ch. 6.2 suggests a policy driven by prices: with a price \alpha_u per unit of budget, give each query to the advertiser maximizing b_{uq}(1 - \alpha_u), if positive.

The right prices minimize the dual. With T i.i.d. queries and target spending rates \rho_u = B_u / T, the dual per query is the convex function D(\alpha) = \sum_u \rho_u\, \alpha_u + \mathbb{E}_q\Big[\max\big(0,\ \max_u b_{uq}(1 - \alpha_u)\big)\Big]. Its gradient is an expectation over an unknown distribution of queries, the setting of stochastic approximation.

Here the noise is the query q. The advertiser who maximizes b_{uq}(1 - \alpha_u), if positive, spends its bid, ignoring the budget cap. The vector g = \rho - \text{spend}(q) is then an unbiased stochastic subgradient of D, and the projected step is \alpha_u \leftarrow \big[\alpha_u + \eta\, (\text{spend}_u(q) - \rho_u)\big]^+ . Overspending raises an advertiser’s price; underspending lowers it.

Balseiro, Lu and Mirrokni (2020) turn this bound, in mirror-descent form and with the budget caps, into a revenue within O(\sqrt{T}) of the optimum under i.i.d. arrivals, so the ratio tends to 1. Devanur and Hayes (2009) learn the prices once on a first fraction of a randomly ordered input.

Under an adversarial order, learned prices can be badly wrong (Exercise 14), while the rule of Theorem 6.3 keeps 1 - 1/e.

import numpy as np
from scipy.optimize import linprog

rng = np.random.default_rng(4)

def allocate(bids, budgets, rule, eta=0.0):
    """Online AdWords: each query goes to one advertiser, who pays min(bid, remaining budget)."""
    T, m = bids.shape
    spent, alpha = np.zeros(m), np.zeros(m)
    rho = budgets / T                                # target spending rate per query
    for t in range(T):
        left = budgets - spent
        b = np.where(left > 0, np.minimum(bids[t], left), 0.0)
        if rule == "greedy":                         # highest bid
            score = b
        elif rule == "msvv":                         # b * psi(f), psi(f) = 1 - e^(f-1)
            score = b * (1 - np.exp(spent / budgets - 1))
        else:                                        # dual prices learned online
            score = b * (1 - alpha)
        u = int(np.argmax(score + 1e-9 * np.arange(m)))   # ties go to the last index
        pay = b[u] if score[u] > 0 else 0.0
        spent[u] += pay
        if rule == "dual":                           # stochastic subgradient step on the dual,
            x = np.zeros(m); x[u] = pay              # with the step of advertiser u scaled by 1/rho_u
            alpha = np.maximum(0.0, alpha + eta * (x - rho) / rho)
    return spent.sum()

def offline_opt(bids, budgets):                     # LP relaxation = upper bound on OPT
    T, m = bids.shape
    c = -bids.ravel()                                # x[t, u] flattened
    A_q = np.kron(np.eye(T), np.ones(m))             # each query allocated at most once
    A_b = np.kron(np.ones(T), np.eye(m)) * bids.ravel()   # budget of each advertiser
    res = linprog(c, A_ub=np.vstack([A_q, A_b]), b_ub=np.r_[np.ones(T), budgets],
                  bounds=(0, 1), method="highs")
    return -res.fun

# (a) adversarial: advertisers 0..m-1, budget B; query group j is bid on by advertisers j..m-1
m, B = 10, 50
bids = np.vstack([np.tile((np.arange(m) >= j).astype(float), (B, 1)) for j in range(m)])
budgets = np.full(m, float(B))
opt = m * B
for rule in ["greedy", "msvv"]:
    print(f"(a) {rule:6s} revenue / OPT = {allocate(bids, budgets, rule) / opt:.3f}")

# (b) i.i.d. queries of two types: type X (bids 1 and 0.99), type Y (only advertiser 0 bids)
T = 2000
is_x = rng.random(T) < 0.5
bids = np.column_stack([np.ones(T), np.where(is_x, 0.99, 0.0)])
budgets = np.array([500.0, 1000.0])
lp = offline_opt(bids, budgets)
print(f"(b) offline LP bound = {lp:.1f}")
for rule, eta in [("greedy", 0), ("msvv", 0), ("dual", 0.01)]:
    print(f"(b) {rule:6s} revenue / LP = {allocate(bids, budgets, rule, eta) / lp:.3f}")

On the adversarial instance (a), with ties broken against the algorithm, greedy earns 0.500 of the optimum and the rule of Mehta et al. 0.658, close to 1 - (1 - 1/10)^{10} = 0.651. On the i.i.d. instance (b), greedy spends advertiser 0’s budget on queries that advertiser 1 values almost as much and earns 0.849 of the LP bound; the rule of Mehta et al. earns 0.998 and the learned prices 1.000.

6.4 Matching with delays

Emek, Kutten and Wattenhofer (2016) let the algorithm wait. Requests appear over time at points of a metric space and must eventually be matched in pairs; a pair costs the distance between its points, and every request pays the time it waits.

A good algorithm waits until the waiting cost of a candidate pair is comparable with its distance, a rent-or-buy rule as in ski rental. On general metrics, Emek et al. combine it with a random tree embedding (defined in ch. 8.4) and obtain a ratio polylogarithmic in the number of points and the aspect ratio; Azar, Chiplunkar and Kaplan (2017) improve the bounds.

7. Paging, caching and metrical task systems

The third family of the course moves from gains to costs. An algorithm holds a state, such as a cache content or server positions, and pays to serve requests or to change state. This chapter treats paging, then the general model of metrical task systems.

7.1 Paging

The offline optimum is explicit: evicting the page whose next request is furthest in the future minimizes the number of faults (Belady, 1966), by an exchange argument.

The usual online rules are LRU (evict the least recently used page) and FIFO (evict the page that entered first). To compare them with the optimum, cut the request sequence into phases: each phase is a maximal segment containing requests to exactly k distinct pages.

The same phase argument proves that FIFO is k-competitive. Yet FIFO is not monotone in k: on the sequence 1 2 3 4 1 2 5 1 2 3 4 5, FIFO makes 9 faults with 3 slots and 10 with 4 slots (Belady’s anomaly), while LRU makes 10 and 8.

7.2 Randomized paging

The marking algorithm works in phases too. A page is marked when it is requested; on a fault with a full cache, it evicts an unmarked page chosen uniformly at random, and when every cached page is marked, it unmarks them all and starts a new phase.

The proof counts, in each phase, the new pages, those not requested in the previous phase; say there are m of them. The optimum pays at least half of the total number of new pages over all phases.

The marking algorithm pays 1 for each new page. The j-th old page requested in the phase has been evicted with probability at most m/(k - j + 1), and summing over j bounds the expected cost of the phase by m H_k. Randomization thus brings the ratio from k down to a logarithm.

import numpy as np
from collections import OrderedDict

def lru(seq, k):
    cache, faults = OrderedDict(), 0
    for p in seq:
        if p in cache:
            cache.move_to_end(p)
            continue
        faults += 1
        if len(cache) == k:
            cache.popitem(last=False)        # least recently used
        cache[p] = True
    return faults

def fifo(seq, k):
    cache, order, faults = set(), [], 0
    for p in seq:
        if p not in cache:
            faults += 1
            if len(cache) == k:
                cache.remove(order.pop(0))   # first in, first out
            cache.add(p); order.append(p)
    return faults

def marking(seq, k, rng):
    cache, marked, faults = set(), set(), 0
    for p in seq:
        if p not in cache:
            faults += 1
            if len(cache) == k:
                if marked >= cache:          # every page marked: a new phase starts
                    marked = set()
                cache.remove(rng.choice(sorted(cache - marked)))
            cache.add(p)
        marked.add(p)
    return faults

def belady(seq, k):                          # offline optimum: evict the furthest next use
    cache, faults = set(), 0
    for t, p in enumerate(seq):
        if p in cache:
            continue
        faults += 1
        if len(cache) == k:
            def next_use(q):
                rest = seq[t + 1:]
                return rest.index(q) if q in rest else len(seq)
            cache.remove(max(cache, key=next_use))
        cache.add(p)
    return faults

seq = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
rng = np.random.default_rng(5)
print("k=3:", {"LRU": lru(seq, 3), "FIFO": fifo(seq, 3), "OPT": belady(seq, 3)})
print("k=4:", {"LRU": lru(seq, 4), "FIFO": fifo(seq, 4), "OPT": belady(seq, 4)})

# A cyclic scan of k+1 pages: the worst case for LRU and FIFO
k = 10
scan = list(range(k + 1)) * 30
mark = np.mean([marking(scan, k, rng) for _ in range(20)])
print(f"scan, k={k}: LRU {lru(scan, k)}, FIFO {fifo(scan, k)}, "
      f"marking {mark:.0f}, OPT {belady(scan, k)}")

On the cyclic scan of 11 pages with 10 slots, LRU and FIFO fault on all 330 requests, the optimum 42 times, and marking about 102 times: ratios 7.9 and 2.4, within the bounds k = 10 and 2H_{10} \approx 5.9.

7.3 Metrical task systems

Paging is a task system whose states are the possible cache contents. The offline optimum is computed by dynamic programming on the work function w_t(s), the least cost of serving the first t tasks and ending in state s: w_t(s) = c_t(s) + \min_{s'} \big( w_{t-1}(s') + d(s', s) \big), \qquad w_0(s) = d(s_0, s).

Good task-system algorithms balance, in each state, the task costs paid there against the cost of moving away: the rent-or-buy principle of ski rental and of ch. 6.4, applied state by state.

8. The k-server problem and tree reductions

In the k-server problem, k servers move in a metric space to cover requests, and the question is how much more than the optimum an online algorithm must move. This chapter proves the lower bound k, reaches it on the line, and introduces the tree reduction behind the randomized results.

8.1 The problem and the conjecture

Paging is the k-server problem on the uniform metric, where every distance is 1 and the points are the pages. The k-server problem is also a task system whose states are the configurations of the servers.

The k-server conjecture states that a ratio of k is achievable on every metric. It holds for k = 2, for k + 1 points, on trees and on the line, and is open in general.

8.2 Double Coverage on the line

Double Coverage (DC) serves a request outside the interval spanned by the servers with the nearest server. A request between two adjacent servers moves both towards it at the same speed, until one of them reaches it.

Moving the nearest server is not competitive: two close alternating requests make greedy shuttle one server forever, while the optimum brings the second server once.

import numpy as np

def greedy(servers, reqs):                   # move the nearest server
    s, cost = np.array(servers, float), 0.0
    for r in reqs:
        i = np.argmin(abs(s - r))
        cost += abs(s[i] - r); s[i] = r
    return cost

def double_coverage(servers, reqs):          # DC on the line
    s, cost = np.sort(np.array(servers, float)), 0.0
    for r in reqs:
        if r <= s[0] or r >= s[-1]:          # outside the hull: nearest extreme server
            i = 0 if r <= s[0] else len(s) - 1
            cost += abs(s[i] - r); s[i] = r
        else:                                # between neighbours: both move by delta
            j = np.searchsorted(s, r)        # s[j-1] < r <= s[j]
            delta = min(r - s[j - 1], s[j] - r)
            cost += 2 * delta
            s[j - 1] += delta; s[j] -= delta
        s.sort()
    return cost

def opt_two_servers(servers, reqs):          # offline optimum for k = 2 by dynamic programming
    pts = list(servers) + list(reqs)         # after request t one server sits at reqs[t]
    a, b = servers
    V = {1: abs(a - reqs[0]), 0: abs(b - reqs[0])}   # key = index in pts of the other server
    for t in range(1, len(reqs)):
        prev, cur, W = reqs[t - 1], reqs[t], {}
        for j, c in V.items():
            W[j] = min(W.get(j, np.inf), c + abs(prev - cur))                  # move the server at prev
            W[2 + t - 1] = min(W.get(2 + t - 1, np.inf), c + abs(pts[j] - cur))  # move the other one
        V = W
    return min(V.values())

rng = np.random.default_rng(6)
start = (0.0, 10.0)
trap = [4.9, 5.1] * 500 + [9.0]              # greedy oscillates, DC brings the far server in
rand = list(rng.uniform(0, 10, 300))
for name, reqs in [("trap", trap), ("random", rand)]:
    o = opt_two_servers(start, reqs)
    print(f"{name:6s}: OPT {o:7.2f}   greedy/OPT {greedy(start, reqs) / o:5.2f}"
          f"   DC/OPT {double_coverage(start, reqs) / o:4.2f}  (k = 2)")

On the trap, greedy pays 15 times the optimum, a ratio that grows with the length of the sequence, while DC is optimal. On 300 uniform requests greedy does better than DC (1.08 against 1.50): a competitive ratio guarantees the worst case, it does not predict typical inputs.

8.3 The work function algorithm

The work function algorithm (WFA) moves to the configuration C that minimizes w_t(C) + d(C_{t-1}, C), with w_t the work function of ch. 7.3 on configurations: a balance between the cheapest move and the offline optimum.

The proof is long and is surveyed by Koutsoupias (2009). Closing the gap between k and 2k - 1 is the deterministic k-server conjecture.

8.4 Tree reductions

Many online problems have good algorithms on trees, and random trees transfer them to every metric.

Bansal, Buchbinder, Mądry and Naor (2015) gave the first randomized k-server algorithm with a ratio polylogarithmic in k and n. Bubeck, Cohen, Lee, Lee and Mądry (2018) reached O(\log^2 k) on HSTs with online mirror descent, the bridge with online learning of ch. 1.4. Bubeck, Coester and Rabani (2023) showed that some metrics force \Omega(\log^2 k), refuting the conjectured O(\log k).

9. Convex body chasing and online transportation

The last in-class chapter takes metrical problems to continuous spaces and to transport.

9.1 Convex body chasing

It is a task system with infinitely many states, where the cost of a task is 0 inside K_t and infinite outside. Friedman and Linial proved a lower bound \sqrt{d} and asked whether a ratio depending on d only is possible.

Sellke’s algorithm moves to the Steiner point of a suitable body, the average over random directions of the extreme points of that body. The Steiner point always lies in the body and moves little when the body shrinks, the property behind the guarantee. The right dependence on d is open (ch. 10.3).

9.2 Online metric matching and online transportation

The online transportation problem of Kalyanasundaram and Pruhs (2000) gives each server site a capacity, so that it serves several requests: optimal transport in an online fashion.

Randomization and trees help again: on HSTs, randomized algorithms reach polylogarithmic ratios, which the reduction of Proposition 8.7 transfers to every metric (Meyerson, Nanavati and Poplawski, 2006; Bansal, Buchbinder, Gupta and Naor, 2014, with O(\log^2 k)).

import numpy as np
from scipy.optimize import linear_sum_assignment

def match_cost(reqs, servers):               # offline min-cost matching on the line
    C = abs(np.subtract.outer(reqs, servers))
    r, c = linear_sum_assignment(C)
    return C[r, c].sum()

def greedy(reqs, servers):
    free, cost = list(servers), 0.0
    for r in reqs:
        j = int(np.argmin([abs(r - s) for s in free]))
        cost += abs(r - free.pop(j))
    return cost

def permutation(reqs, servers):              # Kalyanasundaram-Pruhs / Khuller-Mitchell-Vazirani
    used, cost = [], 0.0
    for t, r in enumerate(reqs):
        cand = [s for s in range(len(servers)) if s not in used]
        best = min(cand, key=lambda s: match_cost(reqs[: t + 1], servers[used + [s]]))
        used.append(best)                    # the optimum for r_1..r_t uses one new server
        cost += abs(r - servers[best])       # r_t takes that new server
    return cost

rng = np.random.default_rng(7)
k = 30
ratios = {"greedy": [], "permutation": []}
for _ in range(10):
    servers = np.sort(rng.uniform(0, 1, k))
    reqs = rng.uniform(0, 1, k)
    opt = match_cost(reqs, servers)
    ratios["greedy"].append(greedy(reqs, servers) / opt)
    ratios["permutation"].append(permutation(reqs, servers) / opt)
for name, r in ratios.items():
    print(f"{name:12s} mean ratio {np.mean(r):.2f}, worst {np.max(r):.2f}  (2k - 1 = {2 * k - 1})")

servers, reqs = np.array([0.0, 2.0]), np.array([1.01, 2.0])   # the two-server trap
print("trap: greedy", greedy(reqs, servers), " permutation", permutation(reqs, servers),
      " OPT", match_cost(reqs, servers))

On random instances both rules stay within a factor 1.8 of the optimum, far from 2k - 1 = 59. On the two-server trap, a request just right of the midpoint lures both rules to the right server; the next request sits on that server, and both pay 2.99 against 1.01, close to 2k - 1 = 3.

10. Research directions and open problems

This self-study chapter collects the open questions announced along the course, with pointers to the papers where they are stated. Each section can seed an internship subject or one of the projects below.

10.1 Stopping problems: constants, combinatorics and samples

• Open constants. The worst-case ratio of the optimal gambler is known for adversarial order (1/2) and for i.i.d. values (about 0.745, Correa et al., 2017). For the prophet secretary and the free-order model, the gap between the best known algorithms and the best known impossibility results is still open.
• Combinatorial selection. When the gambler may keep several values subject to a matroid constraint, Kleinberg and Weinberg (2012) keep the factor 1/2. Online contention resolution schemes (Feldman, Svensson and Zenklusen, 2016) give constant factors for matchings and knapsacks, and the best constants are an active topic.
• Matroid secretary conjecture. Babaioff, Immorlica and Kleinberg (2007) conjectured that the secretary problem on every matroid admits a constant ratio. The best known ratios are of order \log \log of the rank (Lachish, 2014; Feldman, Svensson and Zenklusen, 2015); the conjecture is open.
• Learning the distributions. The prophet inequality assumes known distributions. Azar, Kleinberg and Weinberg (2014) study what limited information suffices, and Rubinstein, Wang and Weinberg (2020) show that a single sample from each distribution already gives the factor 1/2. How many samples suffice for the i.i.d. constants is a natural question.

10.2 Online matching and allocation

• Weights and general bids. For edge-weighted matching with free disposal, Fahrbach, Huang, Tao and Zadimoghaddam (2020) beat the greedy factor 1/2; Huang, Zhang and Zhang (2020) do the same for AdWords without the small-bids assumption. The optimal ratios in both settings are open.
• Both sides online. In fully online matching, every vertex arrives and must be matched before a deadline (Huang, Kang, Tang, Wu, Zhang and Zhu, 2018); the tight ratio of RANKING-like rules is only partly known.
• Random order. The exact random-order ratio of RANKING lies between 0.696 (Mahdian and Yan, 2011) and known upper bounds; closing that interval is open.
• Learning and robustness. Dual-price learning (ch. 6.3) is near-optimal for i.i.d. inputs and fragile for adversarial ones. Algorithms that are good in both worlds at once, and the price of that robustness, are studied in the line of Balseiro, Lu and Mirrokni (2020).

10.3 k-server, task systems and chasing

• The deterministic k-server conjecture. The ratio k is reached on lines, trees and spaces with k + 1 points, and 2k - 1 everywhere (Theorem 8.4). Whether k is achievable on every metric is open, even for k = 3 on general metrics.
• Randomized k-server. After Bubeck, Coester and Rabani (2023), the question is the exact randomized ratio: between \Omega(\log^2 k) on some metrics and the best known polylogarithmic upper bounds, and how it depends on the metric.
• Convex body chasing. The best ratio in \mathbb{R}^d lies between \sqrt{d} (Proposition 9.2) and O(\min(d, \sqrt{d \log T})) (Argue et al., 2020; Sellke, 2020); the right dependence on d is open, and so is the analogous question for chasing convex functions, the smoothed online convex optimization of Chen, Goel and Wierman (2018).
• Online transport and matching on metrics. For online metric matching, randomized ratios are polylogarithmic in k, while the best lower bounds are logarithmic; on the line, the right order is still open.

10.4 Learning-augmented online algorithms

A recent line of work gives the online algorithm a prediction of the future, possibly wrong, and asks for two guarantees at once: consistency, a ratio close to 1 when the prediction is correct, and robustness, a bounded ratio whatever the prediction.

• Lykouris and Vassilvitskii (2018) predict, for paging, the next request time of each page, and adapt the marking algorithm.
• Purohit, Svitkina and Kumar (2018) predict the length of a ski trip. With a trust parameter \lambda \in (0, 1], they buy on day \lceil \lambda B \rceil if the prediction exceeds B and on day \lceil B/\lambda \rceil otherwise. The rule is (1 + \lambda)-consistent and (1 + 1/\lambda)-robust (Exercise 15).

Open directions include the best consistency–robustness trade-offs for matching and k-server, the value of a limited number of queries to the prediction, and predictions learned from data with statistical guarantees.

10.5 Bridges with online learning

The disclaimer of ch. 1.4 separates two theories, yet their tools meet. Mirror descent with entropic regularizers is the engine of the recent randomized results for task systems and k-server (Bubeck, Cohen, Lee and Lee, 2019; Bubeck et al., 2018). Dual descent for budgets (ch. 6.3) is an online convex optimization algorithm whose regret bound becomes a competitive guarantee. Bandit feedback inside stopping problems, where the distributions must be learned while stopping, and regret bounds for repeated prophet or secretary problems, are active questions at the frontier between the two fields.

Exercises

Exercises are sorted by level: ★ applies the course, ★★ combines results or asks for a short proof, ★★★ is open-ended or research-flavoured. The session plan says which exercises follow which session.

1. ★ Ski rental by hand. Take B = 4. For each buying day k = 1, \dots, 6, compute the worst-case ratio of “buy on day k” and find the best k.

   Solution: for k \leq B the worst trip stops on day k, with ratio (k - 1 + B)/k: 4, 2.5, 2 and 1.75 for the first four days.

   For k > B the worst ratio is (k - 1 + B)/B: 2 on day 5 and 2.25 on day 6. The best day is k = B = 4, with ratio 2 - 1/B = 1.75 (Theorem 1.3).

2. ★ Ten secretaries. With n = 10 candidates, compute P_{10}(r) for r = 2, \dots, 6 and the optimal number of candidates to reject.

   Solution: by Theorem 2.5, P_{10}(r) = 0.283, 0.366, 0.399, 0.398, 0.373 for r = 2, \dots, 6. The best rule rejects the first 3 candidates (r = 4) and wins with probability P_{10}(4) = \tfrac{3}{10}\big(\tfrac13 + \tfrac14 + \dots + \tfrac19\big) = 0.3987 .

3. ★ Two uniform values. Let X_1, X_2 be i.i.d. uniform on [0, 1]. Compute the prophet’s gain, the optimal gambler’s gain, and the gain of the threshold rule T = \mathbb{E}[\max]/2.

   Solution: \mathbb{E}[\max] = 2/3. Backward induction stops at X_1 if X_1 \geq 1/2, for a gain \mathbb{E}[\max(U, 1/2)] = 5/8, a ratio of 15/16. With T = 1/3, Example 3.4’s formula gives \frac{1 - T^2}{2}\,(1 + T) = \frac{16}{27} \approx 0.593, a ratio of 8/9 \approx 0.889.

4. ★ Three boxes. Box A holds an exponential value of mean 1 and costs 0.1; box B a uniform value on [0, 4], cost 0.5; box C the value 3 or 0 with probability 1/2 each, cost 0.6. Compute the reservation values and run Weitzman’s rule if A reveals 1.0 and B reveals 1.9.

   Solution: \mathbb{E}[(V - \sigma)^+] = e^{-\sigma} for A, so \sigma_A = \ln 10 \approx 2.30. For B, (4 - \sigma)^2/8 = 0.5 gives \sigma_B = 2; for C, (3 - \sigma)/2 = 0.6 gives \sigma_C = 1.8.

   Open A first; 1.0 is below \sigma_B = 2, so open B. Now 1.9 is above \sigma_C = 1.8: stop and keep 1.9. Had A revealed 2.1, Pandora would have stopped at once.

5. ★ RANKING on four vertices. Let U = \{u_1, u_2\}, v_1 adjacent to both, and v_2 adjacent to u_1 only. Compute the expected size of RANKING’s matching and of the matching of a greedy rule that prefers u_1.

   Solution: with probability 1/2, u_1 has the higher priority; the first online vertex takes it and the second stays unmatched. Otherwise the first takes u_2 and the second takes u_1.

   RANKING matches 3/2 edges in expectation, a ratio of 3/4 to \mathrm{OPT} = 2. The greedy rule matches 1 edge, a ratio of 1/2.

6. ★ Paging by hand. On the sequence 1 2 3 4 1 2 5 1 2 3 4 5, count the faults of LRU, FIFO and Belady’s rule with k = 3 and k = 4.

   Solution: with k = 3: LRU 10, FIFO 9, optimum 7. With k = 4: LRU 8, FIFO 10, optimum 6. FIFO faults more with a larger cache (Belady’s anomaly), which cannot happen to LRU or to the optimum. The block of ch. 7 checks these counts.

7. ★ Double Coverage by hand. Two servers start at 0 and 10 on the line. Requests alternate 4, 5, 4, 5, … for m rounds. Compute the costs of DC, of greedy and of the optimum for m = 1, m = 2 and large m.

   Solution: DC pays 8 for the first request (both servers to 4 and 6), 2 for the second (both to 5), 1 for the third, then nothing. Greedy shuttles one server: 4 + (2m - 1). The optimum is the smaller of greedy’s cost and 4 + 5 = 9.

   For m = 1: DC 10, greedy 5, optimum 5. For m = 2: DC 11, greedy 7, optimum 7. For large m: DC 11, optimum 9, while greedy grows without bound.

8. ★★ Randomized ski rental with B = 2. (a) Show that buying on day 1 with probability 1/3 and on day 2 otherwise has ratio 4/3. (b) Use Yao’s principle with trips of 1 day or of many days, each with probability 1/2, to show that no randomized algorithm does better.

   Solution: (a) For a 1-day trip the expected cost is 2/3 + 2/3 = 4/3 against 1. For longer trips it is 2/3 + 3 \cdot 2/3 = 8/3 against 2. Both ratios are 4/3.

   2. \mathbb{E}[\mathrm{OPT}] = (1 + 2)/2 = 3/2. Buying on day 1 costs 2; buying on day 2 costs (1 + 3)/2 = 2; buying later costs at least (1 + 4)/2. Every deterministic rule has ratio at least 2/(3/2) = 4/3, and Theorem 1.4 concludes.

9. ★★ The median rule and tightness. (a) Deduce the factor 1/2 of the median rule from the first inequality of Theorem 3.2. (b) On the instance of Proposition 3.3, compute the gain of every threshold rule and of the optimal gambler. (c) Which rule does T = \mathbb{E}[\max]/2 select there?

   Solution: (a) With p = 1/2 the bound reads T/2 + (\mathbb{E}[\max] - T)/2 = \mathbb{E}[\max]/2, whatever T.

   2. A threshold T \leq 1 stops at X_1 = 1; a threshold in (1, 1/\varepsilon] skips X_1 and gets \mathbb{E}[X_2] = 1; a larger one gets 0. The optimal gambler also gets 1, against 2 - \varepsilon for the prophet.

   3. The threshold is 1 - \varepsilon/2 < 1: the rule stops at the first value, which is optimal here.

10. ★★ Greedy b-matching. Prove that any rule that matches an online vertex whenever one of its neighbours has spare capacity is 1/2-competitive for b-matching, and that the factor 1/2 is tight for some of these rules.

    Solution: call an offline vertex full if greedy uses all its capacity. Take an optimal b-matching. Each of its edges uv either has v matched by greedy, or u full when v arrived, otherwise greedy would have matched v.

    The first kind number at most |M_{\text{greedy}}|, and the second at most the total capacity of full vertices, which is also at most |M_{\text{greedy}}|. Hence \mathrm{OPT} \leq 2\, |M_{\text{greedy}}|.

    Tightness: give two offline vertices capacity b. Send b online vertices adjacent to both, then b adjacent to the first one only. The rule that prefers the first one fills it with the first group, and matches b vertices against \mathrm{OPT} = 2b.

    Not every such rule is that bad: BALANCE (Theorem 6.1) also matches whenever it can.

11. ★★ FIFO is k-competitive. Prove that on any segment of requests involving at most k distinct pages, FIFO faults at most k times, and conclude with the phase argument of Theorem 7.2.

    Solution: suppose FIFO faults k + 1 times on the segment. Some page faults twice; let p be the page whose second fault comes first. Between its insertion and its eviction, FIFO inserted k other pages, all faulting in the segment.

    None of them faults twice before p’s second fault, so they are distinct, and distinct from p. The segment would involve k + 1 distinct pages, a contradiction. Step 1 of Theorem 7.2 used only this property, and step 2 concerns the optimum, so FIFO \leq k\, \mathrm{OPT} + k.

12. ★★ The odds theorem in Python. (a) Prove that stopping at the first success from index s on wins with probability \prod_{j \geq s}(1 - p_j) \sum_{j \geq s} r_j. (b) Write a function returning Bruss’s index s and this probability, and apply it to records with n = 30 and to constant p_j = 0.1 with n = 30.

    Hints and expected result: (a) the rule wins exactly when one success occurs among indices s, \dots, n; sum over the index of that success. (b) Walk back from n until the tail odds reach 1. Records: s = 12, so reject the first 11 candidates, and win with probability 0.3787. Constant 0.1: the odds are 1/9, s = 22, and the probability is 0.9^9 \approx 0.387.

13. ★★ Trees for a cycle. The 4-cycle has unit edges, so opposite points are at distance 2. (a) Show that deleting one edge leaves a path whose metric dominates the cycle metric. (b) Deleting a uniformly random edge, compute the expected distortion of every pair. (c) Conclude, as in Proposition 8.7, for k-server on the 4-cycle.

    Solution: (a) Path distances are lengths of paths in the cycle, hence at least the shortest ones. (b) An edge is deleted with probability 1/4 and then has length 3, otherwise 1: expected length 3/4 + 3/4 = 1.5. Opposite points stay at distance 2 in every path.

    3. The expected distortion is 1.5, so an \alpha-competitive algorithm on paths, deterministic or randomized, gives a 1.5\,\alpha ratio on the cycle against an oblivious adversary. DC is k-competitive on paths, which gives 1.5\,k.

14. ★★ Learned prices under adversarial orders. In instance (b) of the block of ch. 6.3, sort the queries so that all type X queries come first, then the reverse. Compare greedy, the rule of Mehta et al. and the dual descent with \eta = 0.01, and explain the failures.

    Hints and expected result: with type X first, greedy earns 0.663 of the LP bound (advertiser 0 spends its budget on X), the rule of Mehta et al. 0.781, above 1 - 1/e, and dual descent 0.707. With type Y first, greedy and Mehta et al. are optimal, but dual descent still earns 0.707.

    The dual step holds advertiser 0 to its average rate of 0.25 per query during the Y phase, so half of its budget is never spent. Learned prices assume stationarity.

15. ★★★ Ski rental with a prediction. A predictor announces a trip length y. With a trust parameter \lambda \in (0, 1], buy on day \lceil \lambda B \rceil if y \geq B, and on day \lceil B/\lambda \rceil otherwise (Purohit, Svitkina and Kumar, 2018).

    Show that the ratio is at most 1 + 1/\lambda whatever the prediction, and at most 1 + \lambda when the prediction is exact, up to rounding. Discuss randomized versions.

    Hints and expected result: robustness. Buying early costs at most \lambda B + B when the trip reaches the buying day, against an optimum of at least \lambda B. Buying late costs at most B/\lambda + B against B. Both ratios are at most 1 + 1/\lambda.

    Consistency: if y = d \geq B, the cost is at most \lambda B + B against B; if d < B, the algorithm never buys and pays d. The paper gives a randomized rule with a better trade-off; finding the optimal one is a good research exercise.

16. ★★★ Chasing two lines. In the plane, two lines cross at a point P at angle \theta, and the requests alternate between them forever. Start on the first line at distance L from P. (a) Compute the total movement of the greedy rule that projects onto each new line. (b) Compare with the optimum and simulate. (c) Propose a competitive rule for chasing lines in the plane.

    Hints and expected result: (a) each projection moves r \sin\theta when at distance r from P, and multiplies the distance by \cos\theta, so the total is L \sin\theta \sum_{j \geq 0} \cos^j \theta = L \cot(\theta/2) \approx 2L/\theta .

    2. The optimum moves to P at cost L: the ratio \cot(\theta/2) is 19.98 for \theta = 0.1, unbounded as \theta \to 0. (c) Greedy fails because its moves are nearly perpendicular to the direction of P: a good rule moves towards the intersection of the last two lines. Friedman and Linial (1993) give a constant-competitive algorithm for chasing lines in the plane.

17. ★★★ Prophet secretary experiments. For n = 10 independent values with different distributions (uniform, exponential, two-point) in uniformly random order, compare by simulation: the single threshold \mathbb{E}[\max]/2, the 1/n-type single threshold of Theorem 3.5, and decreasing thresholds T_i chosen by backward induction for a random order. Search for distributions that make each rule bad.

    Hints and expected result: estimate \mathbb{E}[\max] by Monte Carlo and every rule over at least 10^5 orders. The single threshold always keeps its 1/2; good decreasing thresholds stay above 1 - 1/e (Esfandiari et al., 2015). Hard instances mix one rare large value with many moderate ones, as in Proposition 3.3; the worst ratio found by search is a lower estimate of the open constant of ch. 3.4.

Projects and assessment

master-mva.com announces a written exam (“Mode de validation”), and the Université Paris-Saclay course detail describes the assessment as “Evaluation Continue non Intégrale” (non-integral continuous assessment); no weights are displayed. The written exam below is a proposal in the spirit of a blackboard course: a course question, a computation and proofs. The projects are practice beyond the official assessment, in the MVA tradition of reproducing a research paper; each is evaluated with the rubric at the end of the section.

Solo projects

1. [Solo · ≈ 20 h] Prophet secretary and blind strategies (paper study: Esfandiari, Hajiaghayi, Liaghat and Monemizadeh, 2015; Correa, Saona and Ziliotto, 2019). How much do time-dependent thresholds gain over a single threshold when independent values arrive in random order?
   • Implement: the single threshold of Theorem 3.2, the decreasing thresholds of Esfandiari et al., one blind strategy of Correa et al., and the optimal policy for a known order by backward induction (ch. 2, 3).
   • Data: synthetic families (uniform, exponential, two-point and mixtures), n from 2 to 50.
   • Deliverables: code, a 4–6 page report, a 10-minute talk.
   • Success criterion: every rule above its proven guarantee on every instance, and a table of the worst ratios found by a random search over distributions.
2. [Solo · ≈ 20 h] The randomized primal–dual proof of RANKING (paper study: Devanur, Jain and Kleinberg, 2013). Can the dual certificate of Theorem 5.3 be checked exactly?
   • Prove: the monotonicity lemma used in step 3, in full; then the vertex-weighted extension of Aggarwal, Goel, Karande and Mehta (2011) (ch. 0, 5).
   • Implement: exact expectations of the duals on small bipartite graphs, by enumerating all priority orders and arrival orders.
   • Deliverables: code, a 4–6 page report with the proofs, a 10-minute talk.
   • Success criterion: \mathbb{E}[\alpha_u + \beta_v] \geq 1 - 1/e verified for every edge of every bipartite graph with at most four vertices per side, with a discrete analogue of g(y) = e^{y - 1}.
3. [Solo · ≈ 20 h] Caching with predictions (paper study: Lykouris and Vassilvitskii, 2018). How does the predictive marking algorithm degrade when the predicted next-request times are noisy?
   • Implement: LRU, marking, Belady’s optimum and the predictive marker, with predictions corrupted by noise of increasing level (ch. 7, 10.4).
   • Data: synthetic request traces with locality (Zipf popularity, working sets that drift).
   • Deliverables: code, a 4–6 page report, a 10-minute talk.
   • Success criterion: a curve of faults relative to the optimum against the prediction error, close to 1 for exact predictions and never far above the marking algorithm.

Group projects

1. [Group of 3 · ≈ 30 h each] Budget pacing under three arrival models (paper study: Mehta, Saberi, Vazirani and Vazirani, 2007; Devanur and Hayes, 2009; Balseiro, Lu and Mirrokni, 2020). Which allocation rule should a platform use when it does not know whether queries are adversarial, randomly ordered or i.i.d.?
   • Data: synthetic queries with heterogeneous bids and budgets, every bid below 1 % of every budget (the small-bids regime of Theorem 6.3), presented in adversarial, random and i.i.d. orders, T up to 10^4.
   • Split: member A implements the rule of Mehta et al. and adversarial instances; member B the sampling-based prices of Devanur and Hayes; member C dual mirror descent and the offline LP benchmark (ch. 6).
   • Deliverables: shared code, one report of 8–10 pages, a 20-minute talk.
   • Success criterion: a table of ratios to the LP bound, three rules by three arrival models, with Mehta et al. above 1 - 1/e everywhere and the learned prices above 0.95 on i.i.d. inputs.
2. [Group of 2–3 · ≈ 30 h each] k-server on lines, trees and random trees (paper study: Chrobak, Karloff, Payne and Vishwanathan, 1991; Koutsoupias and Papadimitriou, 1995; Fakcharoenphol, Rao and Talwar, 2004). How far from their worst-case ratios are DC and the work function algorithm, and what does a random tree cost?
   • Data: synthetic request sequences on the line, on random trees and on random point sets in the plane, including adversarial sequences from Theorem 8.2.
   • Split: member A computes the offline optimum by minimum-cost flow and implements DC on lines and trees; member B implements the work function algorithm for k \leq 3 on finite metrics; member C builds random HST embeddings and measures their distortion (ch. 8).
   • Deliverables: shared code, one report of 8–10 pages, a 20-minute talk.
   • Success criterion: on every input, the bound \mathrm{DC} \leq k\, \mathrm{OPT} + \Phi_0 of Theorem 8.3 checked with the initial potential, and ratios below 2k - 1 for the work function algorithm on long sequences. The average distortion of the trees should grow like \log n. Short inputs can exceed k because of the additive constant.
3. [Group of 2–3 · ≈ 30 h each] Chasing convex bodies with the Steiner point (paper study: Sellke, 2020; Argue, Gupta, Guruganesh and Tang, 2020). Does the Steiner point move much less than greedy projection on nested and general convex sequences?
   • Data: synthetic sequences of polytopes in dimensions 2 to 10, nested and non-nested, plus the lower-bound sequences of Proposition 9.2 and Exercise 16.
   • Split: member A estimates Steiner points of polytopes by random directions and linear programs; member B implements the chasing algorithms; member C builds hard instances and the offline optimum as a convex program (ch. 9).
   • Deliverables: shared code, one report of 8–10 pages, a 20-minute talk.
   • Success criterion: a plot of the cost ratio against the dimension for each rule, with greedy failing on the line-chasing instances and the Steiner rule staying bounded.

Written exam (proposal)

Format (proposal): 3 hours, one handwritten A4 sheet allowed, no electronic device, four exercises.

1. Question (4 points). Define the competitive ratio of a randomized online algorithm against an oblivious adversary. Explain, on ski rental and on a bandit problem, how it differs from the regret of online learning. State Yao’s principle and say what it is used for.

   Expected: Definition 1.2 with the expectation over the coins and the input fixed in advance; regret compares with the best fixed action and decisions carry no state, while competitive analysis compares with the best sequence and decisions are irrevocable (ch. 1.4); Theorem 1.4, used to prove lower bounds for randomized algorithms.

2. Computation (6 points). (a) In the secretary problem with n = 6, compute the success probability of every threshold rule and find the best one.

   2. Let X_1 be uniform on [0, 1] and X_2 uniform on [0, 2], independent, observed in this order. Compute the prophet’s gain, the optimal gambler’s gain, and the gain of the threshold T = \mathbb{E}[\max]/2.

   Expected: (a) Theorem 2.5 gives 0.381, 0.428, 0.392, 0.300 and 0.167 for r = 2, \dots, 6, and r = 1 wins with probability 1/6. Reject the first two candidates: success 0.428.

   2. The tail formula gives \mathbb{E}[\max] = 5/6 + 1/4 = 13/12. The gambler stops at the first value only if it exceeds \mathbb{E}[X_2] = 1, so he gets 1, a ratio of 12/13. With T = 13/24, the gain is \frac{1 - T^2}{2} + T\, \frac{4 - T^2}{4} \approx 0.855, a ratio of about 0.79.

3. Short proof (5 points). Prove that stopping at the first X_i \geq \mathbb{E}[\max_j X_j]/2 secures half of the prophet’s gain for independent non-negative values, and show that no stopping rule secures more than half in general.

   Expected: Theorem 3.2: the split into threshold and excess, independence of the future (Proposition 0.4), the bound of Proposition 0.2; tightness with Proposition 3.3.

4. Problem (5 points). (a) Prove that no deterministic paging algorithm with a cache of size k is better than k-competitive. (b) Prove that LRU faults at most k times per phase and conclude that it is k-competitive. (c) State, without proof, what randomization changes, and name an algorithm that achieves it.

   Expected: (a) k + 1 pages, the adversary requests the missing page, Belady’s rule faults at most once every k requests. (b) Theorem 7.2, both steps. (c) Theorem 7.3: the marking algorithm is 2H_k-competitive, and H_k is the optimal randomized ratio.

Grading rubric (proposal)

References

Official references

• Neither the master-mva.com course page nor the Université Paris-Saclay course detail lists a bibliography for 2026–2027. The references below are standard sources for the topics of the official description.

Books and surveys

• A. Borodin, R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998 — ch. 1, 7, 8.
• Y. S. Chow, H. Robbins, D. Siegmund, Great Expectations: The Theory of Optimal Stopping, Houghton Mifflin, 1971 — ch. 2.
• G. Peskir, A. N. Shiryaev, Optimal Stopping and Free-Boundary Problems, Birkhäuser, 2006 — ch. 2.
• N. Buchbinder, J. Naor, “The design of competitive online algorithms via a primal–dual approach”, Foundations and Trends in Theoretical Computer Science 3(2–3), 2009 — ch. 5, 6.
• A. Mehta, “Online matching and ad allocation”, Foundations and Trends in Theoretical Computer Science 8(4), 2013 — ch. 5, 6.
• E. Koutsoupias, “The k-server problem”, Computer Science Review 3(2), 2009 — ch. 8.
• B. Lucier, “An economic view of prophet inequalities”, ACM SIGecom Exchanges 16(1), 2017 — ch. 4.
• J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, T. Vredeveld, “Recent developments in prophet inequalities”, ACM SIGecom Exchanges 17(1), 2018 — ch. 3.
• T. Roughgarden (ed.), Beyond the Worst-Case Analysis of Algorithms, Cambridge University Press, 2021 — ch. 5.4, 10.
• D. Bertsimas, J. N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997 — ch. 0.

Competitive analysis, ski rental and lower bounds (ch. 1)

• A. C.-C. Yao, “Probabilistic computations: toward a unified measure of complexity”, FOCS, 1977.
• A. R. Karlin, M. S. Manasse, L. A. McGeoch, S. Owicki, “Competitive randomized algorithms for nonuniform problems”, Algorithmica 11(6), 1994.
• S. Ben-David, A. Borodin, R. Karp, G. Tardos, A. Wigderson, “On the power of randomization in on-line algorithms”, Algorithmica 11(1), 1994.

Stopping, secretaries, prophets and Pandora (ch. 2–4)

• D. V. Lindley, “Dynamic programming and decision theory”, Applied Statistics 10(1), 1961.
• E. B. Dynkin, “The optimum choice of the instant for stopping a Markov process”, Soviet Mathematics Doklady 4, 1963.
• T. S. Ferguson, “Who solved the secretary problem?”, Statistical Science 4(3), 1989.
• F. T. Bruss, “Sum the odds to one and stop”, Annals of Probability 28(3), 2000.
• F. T. Bruss, “A note on bounds for the odds theorem of optimal stopping”, Annals of Probability 31(4), 2003.
• N. Buchbinder, K. Jain, M. Singh, “Secretary problems via linear programming”, Mathematics of Operations Research 39(1), 2014.
• U. Krengel, L. Sucheston, “Semiamarts and finite values”, Bulletin of the American Mathematical Society 83(4), 1977.
• E. Samuel-Cahn, “Comparison of threshold stop rules and maximum for independent nonnegative random variables”, Annals of Probability 12(4), 1984.
• T. P. Hill, R. P. Kertz, “Comparisons of stop rule and supremum expectations of i.i.d. random variables”, Annals of Probability 10(2), 1982.
• R. P. Kertz, “Stop rule and supremum expectations of i.i.d. random variables: a complete comparison by conjugate duality”, Journal of Multivariate Analysis 19(1), 1986.
• R. Kleinberg, S. M. Weinberg, “Matroid prophet inequalities”, STOC, 2012.
• J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, T. Vredeveld, “Posted price mechanisms for a random stream of customers”, EC, 2017.
• H. Esfandiari, M. Hajiaghayi, V. Liaghat, M. Monemizadeh, “Prophet secretary”, ESA, 2015.
• J. Correa, R. Saona, B. Ziliotto, “Prophet secretary through blind strategies”, SODA, 2019.
• M. Feldman, O. Svensson, R. Zenklusen, “Online contention resolution schemes”, SODA, 2016.
• M. L. Weitzman, “Optimal search for the best alternative”, Econometrica 47(3), 1979.
• R. Kleinberg, B. Waggoner, E. G. Weyl, “Descending price optimally coordinates search”, EC, 2016.
• L. Doval, “Whether or not to open Pandora’s box”, Journal of Economic Theory 175, 2018.
• H. Beyhaghi, R. Kleinberg, “Pandora’s problem with nonobligatory inspection”, EC, 2019.
• R. B. Myerson, “Optimal auction design”, Mathematics of Operations Research 6(1), 1981.
• M. T. Hajiaghayi, R. Kleinberg, T. Sandholm, “Automated online mechanism design and prophet inequalities”, AAAI, 2007.
• S. Chawla, J. D. Hartline, D. L. Malec, B. Sivan, “Multi-parameter mechanism design and sequential posted pricing”, STOC, 2010.

Online matching and allocation (ch. 5–6)

• R. M. Karp, U. V. Vazirani, V. V. Vazirani, “An optimal algorithm for on-line bipartite matching”, STOC, 1990.
• N. R. Devanur, K. Jain, R. D. Kleinberg, “Randomized primal-dual analysis of RANKING for online bipartite matching”, SODA, 2013.
• G. Goel, A. Mehta, “Online budgeted matching in random input models with applications to Adwords”, SODA, 2008.
• M. Mahdian, Q. Yan, “Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs”, STOC, 2011.
• J. Feldman, A. Mehta, V. Mirrokni, S. Muthukrishnan, “Online stochastic matching: beating 1 − 1/e”, FOCS, 2009.
• B. Kalyanasundaram, K. Pruhs, “An optimal deterministic algorithm for online b-matching”, Theoretical Computer Science 233, 2000.
• A. Mehta, A. Saberi, U. Vazirani, V. Vazirani, “AdWords and generalized online matching”, Journal of the ACM 54(5), 2007.
• N. Buchbinder, K. Jain, J. Naor, “Online primal-dual algorithms for maximizing ad-auctions revenue”, ESA, 2007.
• G. Aggarwal, G. Goel, C. Karande, A. Mehta, “Online vertex-weighted bipartite matching and single-bid budgeted allocations”, SODA, 2011.
• H. Robbins, S. Monro, “A stochastic approximation method”, Annals of Mathematical Statistics 22(3), 1951.
• N. R. Devanur, T. P. Hayes, “The adwords problem: online keyword matching with budgeted bidders under random permutations”, EC, 2009.
• S. Balseiro, H. Lu, V. Mirrokni, “Dual mirror descent for online allocation problems”, ICML, 2020.
• Y. Emek, S. Kutten, R. Wattenhofer, “Online matching: haste makes waste!”, STOC, 2016.
• Y. Azar, A. Chiplunkar, H. Kaplan, “Polylogarithmic bounds on the competitiveness of min-cost perfect matching with delays”, SODA, 2017.

Paging, task systems, k-server and chasing (ch. 7–9)

• L. A. Belady, “A study of replacement algorithms for a virtual-storage computer”, IBM Systems Journal 5(2), 1966.
• D. D. Sleator, R. E. Tarjan, “Amortized efficiency of list update and paging rules”, Communications of the ACM 28(2), 1985.
• A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, N. E. Young, “Competitive paging algorithms”, Journal of Algorithms 12(4), 1991.
• L. A. McGeoch, D. D. Sleator, “A strongly competitive randomized paging algorithm”, Algorithmica 6, 1991.
• A. Borodin, N. Linial, M. E. Saks, “An optimal on-line algorithm for metrical task system”, Journal of the ACM 39(4), 1992.
• M. S. Manasse, L. A. McGeoch, D. D. Sleator, “Competitive algorithms for server problems”, Journal of Algorithms 11(2), 1990.
• M. Chrobak, H. Karloff, T. Payne, S. Vishwanathan, “New results on server problems”, SIAM Journal on Discrete Mathematics 4(2), 1991.
• E. Koutsoupias, C. H. Papadimitriou, “On the k-server conjecture”, Journal of the ACM 42(5), 1995.
• Y. Bartal, “Probabilistic approximation of metric spaces and its algorithmic applications”, FOCS, 1996.
• J. Fakcharoenphol, S. Rao, K. Talwar, “A tight bound on approximating arbitrary metrics by tree metrics”, Journal of Computer and System Sciences 69(3), 2004.
• N. Bansal, N. Buchbinder, A. Mądry, J. Naor, “A polylogarithmic-competitive algorithm for the k-server problem”, Journal of the ACM 62(5), 2015.
• S. Bubeck, M. B. Cohen, Y. T. Lee, J. R. Lee, A. Mądry, “k-server via multiscale entropic regularization”, STOC, 2018.
• S. Bubeck, M. B. Cohen, J. R. Lee, Y. T. Lee, “Metrical task systems on trees via mirror descent and unfair gluing”, SODA, 2019.
• S. Bubeck, C. Coester, Y. Rabani, “The randomized k-server conjecture is false!”, STOC, 2023.
• J. Friedman, N. Linial, “On convex body chasing”, Discrete & Computational Geometry 9, 1993.
• S. Bubeck, Y. T. Lee, Y. Li, M. Sellke, “Competitively chasing convex bodies”, STOC, 2019.
• C. J. Argue, A. Gupta, G. Guruganesh, Z. Tang, “Chasing convex bodies with linear competitive ratio”, SODA, 2020.
• M. Sellke, “Chasing convex bodies optimally”, SODA, 2020.
• B. Kalyanasundaram, K. Pruhs, “Online weighted matching”, Journal of Algorithms 14(3), 1993.
• S. Khuller, S. G. Mitchell, V. V. Vazirani, “On-line algorithms for weighted bipartite matching and stable marriages”, Theoretical Computer Science 127(2), 1994.
• B. Kalyanasundaram, K. Pruhs, “The online transportation problem”, SIAM Journal on Discrete Mathematics 13(3), 2000.
• A. Meyerson, A. Nanavati, L. Poplawski, “Randomized online algorithms for minimum metric bipartite matching”, SODA, 2006.
• N. Bansal, N. Buchbinder, A. Gupta, J. Naor, “A randomized O(log² k)-competitive algorithm for metric bipartite matching”, Algorithmica 68(2), 2014.

Research directions (ch. 10)

• M. Babaioff, N. Immorlica, R. Kleinberg, “Matroids, secretary problems, and online mechanisms”, SODA, 2007.
• O. Lachish, “O(log log rank) competitive ratio for the matroid secretary problem”, FOCS, 2014.
• M. Feldman, O. Svensson, R. Zenklusen, “A simple O(log log(rank))-competitive algorithm for the matroid secretary problem”, SODA, 2015.
• P. D. Azar, R. Kleinberg, S. M. Weinberg, “Prophet inequalities with limited information”, SODA, 2014.
• A. Rubinstein, J. Z. Wang, S. M. Weinberg, “Optimal single-choice prophet inequalities from samples”, ITCS, 2020.
• M. Fahrbach, Z. Huang, R. Tao, M. Zadimoghaddam, “Edge-weighted online bipartite matching”, FOCS, 2020.
• Z. Huang, Q. Zhang, Y. Zhang, “AdWords in a panorama”, FOCS, 2020.
• Z. Huang, N. Kang, Z. G. Tang, X. Wu, Y. Zhang, X. Zhu, “How to match when all vertices arrive online”, STOC, 2018.
• N. Chen, G. Goel, A. Wierman, “Smoothed online convex optimization in high dimensions via online balanced descent”, COLT, 2018.
• T. Lykouris, S. Vassilvitskii, “Competitive caching with machine learned advice”, ICML, 2018.
• M. Purohit, Z. Svitkina, R. Kumar, “Improving online algorithms via ML predictions”, NeurIPS, 2018.