Online Mechanisms

Motivation: mechanism design when agents come and go

Many allocation problems are inherently dynamic:

selling airline seats to buyers who arrive over time;
allocating CPU or bandwidth to arriving jobs;
selling search adverts when both buyers and future supply of search terms are uncertain;
assigning tasks to a changing team.

In each, either agents arrive and depart, or future feasible decisions are uncertain, or both. Decisions must be made online: now, without knowing future types or future supply, as in online algorithms.

IntuitionThe central question

When decisions can’t wait for everyone to show up, and agents can lie about when they are present as well as how much they value things, can we still make truthful reporting optimal — and how much efficiency or revenue must we give up relative to a mechanism that knew the future?

What is genuinely new

Offline MD	Online MD
all types reported before any decision	decide without types not yet arrived, and without knowing future feasibility
agents misreport values	agents also misreport arrival and departure; strategies are temporal
any type can be claimed	limited misreports: e.g. you can’t claim to arrive before you exist

More generally, an agent’s type may be revealed to itself over time, depending on the mechanism’s decisions. For example, you learn your value for a resource only by using it.

The running example: Jane’s ice cream

DefinitionCanonical expiring items environment

Periods $T = \{1, 2, \dots\}$ , with one indivisible item per period that perishes if unsold. Agent $i$ has private type $\theta_i = (a_i, d_i, w_i) \in T \times T \times \mathbb{R}_{>0}$ : arrival $a_i$ , departure $d_i$ , and value $w_i$ for one unit allocated in some $t \in [a_i, d_i]$ . Utility is $w_i - p$ if served in the window, and $-p$ otherwise.

The arrival $a_i$ is the first period the agent’s information can reach the mechanism. “Can” matters, because a strategic agent may delay.

ExampleExample 16.1 — the naive dynamic Vickrey auction fails

Auction 1: bids are reports $\hat\theta_i = (\hat a_i, \hat d_i, \hat w_i)$ , made in period $\hat a_i$ . Each period, allocate to the highest unassigned bid and charge the second-highest unallocated bid in that period.

Jane makes one cone per hour. Buyers $(1,2,100)$ , $(1,2,80)$ , $(2,2,60)$ .

Truthful: buyer 1 wins period 1 for 80, and buyer 2 wins period 2 for 60.
Buyer 1 shades to $(1,2,61)$ : buyer 2 wins period 1 for 61, then buyer 1 wins period 2 for 60.
Buyer 1 delays, reporting $(2,2,80)$ : buyer 2 wins period 1 for 0, then buyer 1 wins period 2 for 60.

WarningWhy static Vickrey logic breaks

Offline, Vickrey is truthful because your bid doesn’t affect your price. Sequentially, an agent chooses which period’s auction to enter, and hence which rivals and which price it faces. If every agent were impatient ( $d_i = a_i$ ), future prices would be irrelevant and truthful immediate bidding would be dominant. The manipulation here also depended on buyer 3’s bid, so it won’t always pay, but one failure is enough to kill dominant- strategy truthfulness.

Two analytical frameworks

Framework	Analysis	When appropriate	Chapter section
model-free	worst case, competitive ratio vs an offline benchmark	no good probabilistic model (e.g. a brand-new product)	§16.3
model-based	average case, expected value under a common-knowledge prior	data-rich (e.g. sponsored search, where arrivals and departures can be modeled)	§16.4

The online MD model

Agents are risk-neutral with quasilinear utility: they maximize expected value of the decision sequence minus total payment. Time is discrete, $T = \{1,2,\dots\}$ , possibly infinite. The mechanism makes decisions $k = (k^1, k^2, \dots)$ , writing $k^{[t_1,t_2]} = (k^{t_1},\dots,k^{t_2})$ . Decisions depend on agents’ messages and on uncertain environment events, such as the realized supply of search terms.

DefinitionTypes and valuations

$\theta_i = (a_i, d_i, w_i) \in \Theta_i$ defines a private valuation $v_i(\theta_i, k)$ that depends only on the window: $v_i(\theta_i, k) = v_i(\theta_i, k^{[a_i, d_i]}).$ The valuation component $w_i \in W_i$ can be rich. For example, it may express substitutes or complements in an online combinatorial auction, or discount future value by $\gamma^{t - a_i}$ .

Direct-revelation online mechanisms

Closed mechanisms give agents no feedback before they report, so a report can’t be conditioned on others’ reports.

Symbol	Meaning
$\omega \in \Omega = \prod_t \Omega^t$	exogenous stochastic events (e.g. supply); excludes agent types and the mechanism’s own coin flips
$\omega^t$ , $\theta^t$	information revealed and types reported in period $t$
$h^t = (\theta^1..\theta^t;\ \omega^1..\omega^t;\ k^1..k^{t-1})$	mechanism state (in practice a small sufficient statistic)
$K(h^t)$	feasible decisions now (finite)
$I(h^t)$	active agents: $t \in [a_i, d_i]$

DefinitionDefinition 16.2 — direct-revelation online mechanism

$M = (\pi, x)$ : each agent makes one claim about its type.

Decision policy $\pi = \{\pi^t\}$ , with $\pi^t(h^t) \in K(h^t)$ ; may be stochastic.
Payment policy $x = \{x^t\}$ , with $x_i^t(h^t)$ collected from active $i$ ; may be spread over periods.

Write $\pi(\theta,\omega)$ for the decision sequence and $p_i(\theta,\omega)$ for $i$ ‘s total payment.

ExampleExample 16.3 — ice cream as a mechanism

State $h^t$ : the reported types currently present, each flagged allocated or not. Decision: whether to give this period’s cone to some present, unallocated agent.

Limited misreports

DefinitionDefinition 16.4 — limited misreports

$C(\theta_i) \subseteq \Theta_i$ is the set of reports available to an agent of true type $\theta_i$ . Offline MD usually takes $C(\theta_i) = \Theta_i$ .

Assumption	$C(\theta_i)$	Why it is credible
no early arrival (always assumed)	$a_i \le \hat a_i \le \hat d_i$ , any $\hat w_i$	the agent doesn’t know its type, or about the mechanism, before $a_i$
+ no late departure (sometimes)	$a_i \le \hat a_i \le \hat d_i \le d_i$	e.g. no one claims to want a 7 p.m. Broadway ticket after 5 p.m. when travel takes 2 hours; or require presence for the whole reported window

ConventionTighter and weaker windows

$[a'_i, d'_i]$ is tighter than $[a_i, d_i]$ if $a'_i \ge a_i$ and $d'_i \le d_i$ . Under both no-early and no-late assumptions, an agent can only report tighter windows than its true one.

Incentive compatibility

DefinitionDefinition 16.5 — DSIC (“truthful”)

$M$ is DSIC given $C$ if for all $\hat\theta_i \in C(\theta_i)$ , all $\theta_i$ , all $\theta'_{-i} \in C(\theta_{-i})$ , all $\theta_{-i}$ , and all $\omega$ :

v_i(\theta_i, \pi(\theta_i, \theta'_{-i}, \omega)) - p_i(\theta_i, \theta'_{-i}, \omega) \ge v_i(\theta_i, \pi(\hat\theta_i, \theta'_{-i}, \omega)) - p_i(\hat\theta_i, \theta'_{-i}, \omega).

For stochastic $\pi$ this holds in expectation over the mechanism’s coins. Strong truthfulness requires it for every coin flip and every $\omega$ .

DefinitionDefinition 16.6 — BNIC

Assume a correct probabilistic model of types and events is common knowledge. $M$ is BNIC if for all $\hat\theta_i \in C(\theta_i)$ and all $\theta_i$ :

\mathbb{E}\big\{v_i(\theta_i, \pi(\theta_i,\theta_{-i},\omega)) - p_i(\theta_i,\theta_{-i},\omega)\big\} \ge \mathbb{E}\big\{v_i(\theta_i, \pi(\hat\theta_i,\theta_{-i},\omega)) - p_i(\hat\theta_i,\theta_{-i},\omega)\big\},

with expectation over $\theta_{-i}$ , $\omega$ , and the policy’s randomness.

Concept	Truth is best	Needs a common prior?
strong truthfulness	against any reports, every $\omega$ , every coin flip	no
DSIC	against any reports, every $\omega$ , in expectation over coins	no
BNIC	when others are truthful, in expectation over types and events	yes

The revelation principle can fail

ExampleExample 16.7 — an indirect mechanism no direct one can copy

Setup: no early arrival, but late-departure misreports allowed. $T=\{1,2\}$ , one item, one agent with type $(1,1,1)$ or $(1,2,1)$ . Messages: $\{1,2\}$ in period 1, $\{1\}$ in period 2 ( $\phi$ = silence).

Decisions: $\pi^1(1) = 0$ , $\pi^1(2) = 1$ , and nothing in period 2.
Payments: $x^1(2) = 3$ , $x^2(2,1) = -2.01$ , and $0$ otherwise.

Type $(1,2,1)$ sends $(2,1)$ : allocated in period 1, net payment $0.99$ , utility $0.01$ . Type $(1,1,1)$ sends $1$ and gets utility $0$ . Sending $2$ would cost $3$ with no period-2 refund, because it has departed and cannot send the second message.

A direct version must allocate type $(1,2,1)$ in period 1 for $0.99$ . But then type $(1,1,1)$ simply claims $(1,2,1)$ , a late-departure misreport, and gains $0.01$ . So it is not DSIC.

IntuitionWhy it fails

The indirect mechanism physically prevents claiming a later departure: you must be present in period 2 to send the refund message. A single report can’t enforce presence.

NoteRecovering the principle

The revelation principle does hold with no-early-arrival and no-late-departure misreports.
It can also be recovered with heartbeat messages: one type report, plus a noninformative message in every period of $[\hat a_i, \hat d_i]$ . The derivation is left as an exercise.

The chapter focuses on IC direct-revelation mechanisms from here on.

Single-valued domains: monotonicity plus critical value

The problem. We want a recipe for truthful online mechanisms. In offline single-parameter settings, truthful means monotone allocation plus threshold payments (compare mechanism-design). Does that survive time?

DefinitionDefinition 16.8 — single-valued online domain

Agent $i$ has type $\theta_i = (a_i, d_i, (r_i, L_i))$ , with reward $r_i \in \mathbb{R}$ and interesting set $L_i \in \mathcal{L}_i$ from a language of decision subsets, partially ordered by $\succeq_L$ :

v_i(\theta_i, k) = \begin{cases} r_i, & \text{if } k^t \in \bigcup_{L \in \mathcal{L}_i,\ L \succeq_L L_i} L \text{ for some } t \in [a_i, d_i],\\ 0, & \text{otherwise.}\end{cases} \tag{16.1}

The agent gets the same value for any interesting decision in its window, and wants at most one.

Known interesting sets. Assume the mechanism knows $L_i$ . Private information is then only arrival, departure and reward, which gives the partial order on types:

\theta_1 \preceq_\theta \theta_2 \iff (a_1 \ge a_2) \wedge (d_1 \le d_2) \wedge (r_1 \le r_2) \wedge (L_1 = L_2). \tag{16.2}

IntuitionReading $\preceq_\theta$

$\theta_1 \preceq_\theta \theta_2$ means $\theta_1$ is harder to serve and worth less: a tighter window and a lower reward. Monotonicity will say that moving up the order never loses you an allocation.

ExampleExample 16.9 — known single-minded combinatorial auction

Heterogeneous items $G$ in uncertain, non-storable supply. $L_i$ carries a bundle $S(L_i)$ and covers all decisions giving $i$ at least $S(L_i)$ . Order: $L_1 \succeq_L L_2 \iff S(L_1) \supseteq S(L_2)$ . The agent gets $r_i$ when it receives a superset of $S(L_i)$ in its window.

Policies are deterministic from here, with $\pi_i(\theta_i,\theta_{-i}, \omega) \in \{0,1\}$ indicating an interesting decision (“allocation”) for $i$ in its window. Stochastic policies are covered by folding coins into $\omega$ and demanding strong truthfulness; see Stochastic policies.

DefinitionDefinition 16.10 — critical value

v^c_{(a_i,d_i,L_i)}(\theta_{-i},\omega) = \begin{cases} \min r'_i \ \text{s.t.}\ \pi_i((a_i,d_i,(r'_i,L_i)), \theta_{-i},\omega)=1,\\ \infty, \ \text{if no such } r'_i.\end{cases} \tag{16.3}

Component	Detail
Signature	$v^c : (\text{window}, L_i) \times \Theta_{-i} \times \Omega \to \mathbb{R}\cup\{\infty\}$
Domain	the agent’s reported window and interesting set, plus everyone else and the environment
Codomain	the lowest reward at which this window still gets served
Not an input	the agent’s own reward $r_i$

DefinitionDefinition 16.11 — monotonic policy

$\pi$ is monotonic if for all $\theta_{-i}, \omega$ :

\big(\pi_i(\theta_i,\theta_{-i},\omega) = 1\big) \wedge \big(r_i > v^c_{(a_i,d_i,L_i)}(\theta_{-i},\omega)\big) \Rightarrow \pi_i(\theta'_i, \theta_{-i},\omega) = 1 \quad \forall\, \theta'_i \succeq_\theta \theta_i.

The strict profit condition $r_i > v^c$ just avoids knife-edge indifference when $r'_i = r_i$ .

LemmaLemma 16.12 — critical values behave

For a deterministic monotonic policy, the critical value is independent of $r_i$ and weakly increasing as the window tightens.

ProofSqueeze a reward between the two critical values

Step 1: Independence of $r_i$ . Immediate from (16.3): it is a minimum over rewards, with the window and the others fixed.

Step 2: Suppose tightening lowered it. Take windows with $[a_i,d_i]$ tighter than $[a'_i,d'_i]$ , but $v^c_{(a_i,d_i,L_i)} < v^c_{(a'_i,d'_i,L_i)}$ .

Step 3: Pick a reward in the gap. Choose $r$ strictly between the two critical values. The tight-window type $(a_i,d_i,(r,L_i))$ is served with strict profit. The weak-window type $(a'_i,d'_i,(r,L_i))$ sits above it in $\preceq_\theta$ but is not served, since $r$ is below its critical value. That contradicts monotonicity.

∎

TheoremTheorem 16.13 — monotone ⇒ truthful

A monotonic deterministic policy can be truthfully implemented (known interesting sets, single-valued, no early-arrival and no late-departure misreports) with the critical-value payment collected on departure:

x_i^t(h^t) = \begin{cases} v^c_{(\hat a_i,\hat d_i,L_i)}(\hat\theta_{-i}, \omega), & t = \hat d_i \text{ and } \pi_i(\hat\theta_i,\hat\theta_{-i}, \omega) = 1,\\ 0, & \text{otherwise.}\end{cases} \tag{16.4}

ProofCase analysis; limited misreports only tighten the window

Fix $\theta_{-i}, \omega$ and true $\theta_i = (a_i,d_i,(r_i,L_i))$ .

Case (a): truthful $i$ is not served, so $v^c_{(a_i,d_i,L_i)} > r_i$ . Any available report has a tighter window (limited misreports), so by Lemma 16.12 its critical value is at least as high. Being served under any report therefore costs more than $r_i$ , which gives negative utility.

Case (b): truthful $i$ is served at price $v^c \le r_i$ , so utility is nonnegative. A report that loses gives $0$ , no better. A report that still wins pays its own critical value. That value is independent of the reported reward and weakly higher for the necessarily tighter window (Lemma 16.12). No gain.

∎

Necessity. A mechanism is individually rational (IR) if every agent has nonnegative utility in equilibrium. This is needed when participation can’t be forced.

LemmaLemma 16.14 — payments must be critical values

Any truthful, IR online mechanism with a deterministic policy (known interesting set, single-valued) charges each allocated agent exactly its critical value.

ProofUndercharging invites misreports; overcharging breaks IR

Fix $\theta_{-i}, \omega$ .

Step 1: The price can’t depend on the reward. If two winning rewards $r_i \ne r'_i$ (both above critical, same window) paid different amounts, the type charged more would report the other reward.

Step 2: The price can’t be below critical. If a winner paid $p < v^c$ , a type with the same window and reward $r'_i \in (p, v^c)$ loses when truthful but profits by claiming the winning reward. (This works even with negative $p$ if rewards can be negative.)

Step 3: The price can’t be above critical. If $p > v^c$ , a type with reward in $(v^c, p)$ is served and pays more than its value, violating IR.

∎

Reasonable misreporting. An agent can at least report any tighter window with any reward.

TheoremTheorem 16.15 — truthful ⇒ monotone

With reasonable misreporting, any deterministic policy truthfully implementable by an IR mechanism that doesn’t pay losers must be monotonic.

ProofA non-served stronger type imitates a served weaker one

Step 1: Suppose monotonicity fails. Take $\theta_i \prec_\theta \theta'_i$ with $\theta_i$ served at strict profit ( $r_i > v^c$ ) and $\theta'_i$ not served.

Step 2: The weaker type profits. By Lemma 16.14, $\theta_i$ pays exactly $v^c_{(a_i,d_i,L_i)} < r_i \le r'_i$ .

Step 3: The stronger type can copy it. $\theta'_i$ is unserved and pays $\ge 0$ (losers aren’t paid), so its utility is $\le 0$ . But its window is weaker, so it can report $\theta_i$ and get $r'_i - v^c > 0$ . This contradicts truthfulness.

∎

Warning“Don’t pay losers” is load-bearing

Take no late departure, types $\{(1,1,\text{\textdollar}10), (1,2,\text{\textdollar}10)\}$ , with $\pi_i(1,1,\text{\textdollar}10) = 1$ and $\pi_i(1,2,\text{\textdollar}10) = 0$ . This is nonmonotonic: the patient type loses. Yet it is truthful with payments $8$ and $-100$ . The patient loser is paid $100 to stay put.

DefinitionMonotonic-late (arbitrary departure misreports)

The critical departure $d^c_{(a_i,d_i,L_i)}(\theta_{-i},\omega)$ is the earliest $d'_i \le d_i$ with the same critical value as $d_i$ . It is the earliest departure the agent could claim without raising its price. $\pi$ is monotonic-late if it is monotonic and never makes an interesting decision for $i$ before its critical departure.

TheoremMonotonic-late characterization

With no early arrival but arbitrary departure misreports, a deterministic policy is truthfully implementable iff it is monotonic-late, with critical-value payments.

IntuitionWhy “late” fixes late-departure lies

The danger is claiming a later departure to face a lower price. If service never comes before the critical departure, then overclaiming departure either doesn’t change the price or pushes service past your true departure, where it is worth nothing.

ImportantThe design recipe

In single-valued domains: design a monotone (or monotone-late) allocation rule, then charge critical values on departure. Truthfulness follows, and for IR mechanisms that don’t pay losers, nothing else works. This mirrors the offline single-parameter characterization; the time dimension enters only through the window part of $\preceq_\theta$ .

Expiring items: the greedy auction

Competitive analysis

Worst case: an adversary picks inputs to make the mechanism look bad. We compare against an offline benchmark that knows the future. This is justified when there is no model, it yields robust designs and lower bounds, and it often does well on average anyway. We need three ingredients:

Ingredient	Here
optimality criterion	efficiency (total value allocated)
adversary’s power	arbitrary values, arrivals, departures
offline benchmark	best allocation with perfect information

FormulaOffline optimum

V^*(\theta) = \max_{x,y} \sum_{i=1}^N y_i w_i \quad\text{s.t.}\quad \sum_{t=a_i}^{d_i} x_i^t \ge y_i\ \ \forall i,\qquad \sum_{i:\, t\in[a_i,d_i]} x_i^t \le 1\ \ \forall t \tag{16.5–16.7}

Here $y_i \in \{0,1\}$ means bid $i$ is served, and $x_i^t \in \{0,1\}$ is the serving period. Giving a winner extra units doesn’t change the objective.

Definition $c$ -competitive for efficiency

\min_{z \in Z} \mathbb{E}\left[\frac{\mathrm{Val}(\pi(\theta_z))} {V^*(\theta_z)}\right] \ge \frac1c, \qquad c \ge 1, \tag{16.8}

where $Z$ is the adversary’s input set. The expectation allows randomized policies or a randomized adversary.

The greedy auction

AlgorithmAuction 2 — greedy with critical-value payments

Bids $\hat\theta_i$ are made in period $\hat a_i$ .

Each period, give the item to the highest unassigned bid, breaking ties at random.
Each winner pays its critical value, collected at its reported departure.

The allocation rule is Auction 1’s; only the payment changes. With all agents impatient, it reduces to a sequence of Vickrey auctions.

ExampleExample 16.16 — Jane’s buyers again

Truthful $(1,2,100), (1,2,80), (2,2,60)$ : buyer 1 wins period 1, buyer 2 wins period 2. Both pay 60. For window $(1,2)$ , a bid just above 60 still wins (in period 2 rather than 1), so 60 is the critical value.

TheoremTheorem 16.17 — greedy is truthful and 2-competitive

Auction 2 is strongly truthful and 2-competitive for efficiency, with no early-arrival and no late-departure misreports.

ProofMonotonicity, then a charging argument

Step 1: Truthfulness via Theorem 16.13. Let tie-breaking be invariant to the reported window. If $i$ wins at some $t$ , it still wins, at the same period or earlier, with a higher value, an earlier arrival or a later departure. So the rule is monotone, and payments are critical values.

Step 2: Charge the offline winners to online winners. For each $i$ served offline in period $t$ :

if $i$ is also served online, charge $w_i$ to $i$ itself;
if not, $i$ was present and unassigned at $t$ , so greedy gave period $t$ to someone with value $\ge w_i$ ; charge $w_i$ to that agent.

The key step: each online winner receives at most two charges (itself, plus the offline winner of its own period), each at most its own value. So $V^*(\theta) \le 2\cdot\mathrm{Val}(\text{greedy})$ .

∎

NoteAuction 1 in hindsight

Auction 1’s allocation rule was already monotone. It failed only because the second-price-this-period payment is not the critical value.

WarningThe best online algorithm isn’t truthful

A 1.618-competitive online algorithm exists for this problem, but it is not monotone, so it can’t be made truthful. For truthful mechanisms, 2 is tight:

TheoremTheorem 16.18 — 2 is optimal for truthful deterministic auctions

No truthful, IR, deterministic online auction achieves a $(2-\epsilon)$ -approximation for efficiency (expiring items, no early arrival, no late departure), for any constant $\epsilon > 0$ .

ProofThree scenarios force an impatient agent to lie profitably

Take $T=\{1,2\}$ and $0 < \delta < \epsilon/(1-\epsilon)$ , so that $\frac{q(1+\delta)}{q(2+\delta)} < \frac{1}{2-\epsilon}$ . Serving only one of two agents worth about $q$ is then not $(2-\epsilon)$ -competitive.

Scenario (i): $\theta_1 = (1,1,q(1+\delta))$ and $\theta_2 = (1,2,q)$ . Both must be served, so agent 1 is served in period 1. Its price is its critical value, independent of its reported value. Taking the scale so this price is $\le q$ , agent 1 gets strictly positive utility.

Scenario (ii): $\theta'_1 = (1,2,q(1+\delta))$ , $\theta_2 = (1,2,q)$ , and $\theta_3 = (2,2,\infty)$ arriving in period 2.

Agent 1 must be served, else it would report $(1,1,q(1+\delta))$ (a tighter window, allowed) and profit as in (i).
It must be served in period 1, else period 2 can’t go to the infinite-value $\theta_3$ .
So agent 2 is not served.

Scenario (iii): $\theta'_1 = (1,2,q(1+\delta))$ and $\theta'_2 = (1,1,q)$ . Both must be served, so the impatient agent 2 gets period 1. WLOG $q$ strictly exceeds agent 2’s critical value here (else rescale $q \to \alpha q$ ). Then agent 2 has strictly positive utility.

The key step: return to (ii). Agent 2, with true type $(1,2,q)$ , is unserved. Period-1 decisions can’t depend on $\theta_3$ , who hasn’t arrived yet, so reporting $(1,1,q)$ reproduces (iii) in period 1. Agent 2 is then served at a profit. So the auction isn’t truthful.

∎

TheoremTheorem 16.19 — why no-late-departure is needed

With no early arrival but arbitrary departure misreports, no truthful, IR, deterministic online auction has a constant efficiency ratio.

ProofPatient agents must be served immediately, so only one can be

Take $M$ periods, fix $\theta_{-i}$ , and assume $v^c_{(1,1)}(\theta_{-i}) < \infty$ .

Step 1: A patient type above the impatient price must be served at once. Let $w_i = v^c_{(1,1)} + \epsilon$ . Monotonicity gives $v^c_{(1,M)} \le v^c_{(1,1)}$ , so type $(1,M,w_i)$ is served. It must be served in period 1. Otherwise the adversary adds bids $(t,t,\beta^{t-1})$ for $t = 2..M$ with large $\beta$ , all of which must be served to stay competitive. In that case $i$ would do better to claim $(1,1,w_i)$ and be served at once for $v^c_{(1,1)} < w_i$ .

Step 2: The two critical values coincide. Since $(1,M,w)$ is served in period 1, truthfulness and Lemma 16.14 force $v^c_{(1,M)} = v^c_{(1,1)}$ . Otherwise the impatient type would claim the patient window (a later departure is now allowed) and pay less. So every patient $(1,M,w_i)$ with $w_i > v^c_{(1,M)}$ is served in period 1.

Step 3: Many patient agents. Profile $\{(1,M,q_1),\dots,(1,M,q_M)\}$ with distinct $q_j \in [q,q+\delta]$ . Each critical value is finite, else the adversary swaps in a huge impatient bid. Perturb so each $q_j$ is strictly above its critical value. Every served bid is served in period 1, so at most one is served: value $\le q+\delta$ , against $V^* \ge Mq$ . Let $M \to \infty$ .

∎

RemarkDispensing with no-late-departure

If the resource can be used early but its benefit withheld until the reported departure (e.g. grid computing: run the job, hold the result), the no-late-departure assumption can be dropped while keeping truthfulness.

Limited supply: an adaptive secretary auction

The problem. There is one item and $N$ agents with types $(a_i, d_i, w_i)$ . We want good revenue and efficiency. There is no early arrival, and departures may be misreported arbitrarily. Against the adversary of the previous section, no constant ratio is possible, so we weaken the adversary.

The secretary problem

DefinitionThe secretary problem

$N$ applicants (known) are interviewed in turn. After each, the interviewer learns its relative rank among those seen so far and must decide irrevocably whether to hire. The goal is to maximize the probability of hiring the best.

Random-ordering hypothesis: the adversary picks the set of qualities, but their assignment to arrival order is uniformly random.

TheoremOptimal stopping rule

Interview the first $t-1$ applicants, then hire the next candidate (best so far), where

\sum_{j=t+1}^N \frac{1}{j-1} \le 1 < \sum_{j=t}^N \frac{1}{j-1}. \tag{16.9}

For $N = 10{,}000$ , $t = 3{,}680$ . As $N \to \infty$ , $t/N \to 1/e$ and the success probability $\to 1/e$ : sample $N/e$ , then take the next best-so- far.

Auction reinterpretation. Bidders are strategic (value and timing) and have both entry and exit times. The adversary picks a set of values and a set of windows. Types are formed by matching the two uniformly at random. By averaging, the upper bounds also hold for i.i.d. values from an unknown distribution.

Definition $c$ -competitive for revenue

$\mathrm{Rev}(p(\theta)) = \sum_i p_i(\theta)$ . The benchmark $R^*(\theta)$ is the offline Vickrey revenue, the second-highest value.

\min_{z\in Z}\mathbb{E}\left[\frac{\mathrm{Rev}(p(\theta_z))} {R^*(\theta_z)}\right] \ge \frac1c, \tag{16.10}

with expectation over the random matching.

The straw man fails

ExampleExample 16.20 — naive learn-then-post isn’t truthful

Rule: observe the first $N/e$ reports, then post the maximum seen and sell to the first later bid above it.

Six agents; $6/e \approx 2$ bids are observed. Types $(1,7,6)$ , $(3,7,2)$ , $(4,8,4)$ , $(6,7,8)$ , and two later arrivals.

Truthful: the learning phase sees agents 1 and 2, so the price is 6. Agent 3 (value 4) passes. Agent 4 wins in period 6 and pays 6.
Agent 1 delays to $(5,7,6)$ : the learning phase now sees agents 2 and 3, so the price is 4. Agent 1 bids in period 5, wins, and pays 4.

WarningWhy it fails

It is truthful for impatient agents, but not monotone in arrival time. Arriving early puts your value into the learning sample and raises your own price. So a patient agent wants to arrive late.

The fix

AlgorithmAuction 3 — adaptive limited-supply auction

Bids $\hat\theta_i$ are made in period $\hat a_i$ .

Learning: in the period $\tau$ when the $(N/e)$ -th bid arrives, let $p \ge q$ be the top two values so far.
Transition: if an agent who bid $p$ is still present at $\tau$ , sell to it (random tie-break) at price $q$ .
Accepting: otherwise sell to the next agent bidding at least $p$ (random tie-break), at price $p$ .

graph LR
  L["Learning: collect first N/e bids"] --> X{"Top bidder still present at transition?"}
  X -->|"yes"| S1["Sell to top bidder at second price q"]
  X -->|"no"| A["Accepting: sell to next bid at least p, at price p"]

IntuitionWhy the transition step matters

An early arrival still sets the price $p$ , but if it is still around at the transition, it gets the item at the second price $q$ . Arriving early no longer hurts you. That restores monotonicity in arrival.

TheoremTheorem 16.21 — Auction 3 is strongly truthful

Auction 3 is strongly truthful in the single-unit, limited-supply environment with no early-arrival misreports.

ProofCase analysis on where the window sits; check monotonic-late

Let tie-breaking be independent of reported departure, and fix $\theta_{-i}$ .

Case (a): window ends before the transition. Never served; nothing to check.

Case (b): window spans the transition, $i$ doesn’t trigger it, and wins with $w_i > q$ . No tie is involved. An earlier arrival, later departure or higher value changes nothing about the price at the transition, so $i$ still wins. Price $q$ .

Case (c): arrives after the transition and wins with $w_i > p$ (perhaps by tie-break with a same-period rival). $i$ still wins with an earlier arrival (even before the transition, where its value sets $p$ ), with a later departure (the tie-break is departure-invariant), or with a higher value. Price $p$ .

Case (d): $i$ triggers the transition and wins with $w_i > q$ . Then $w_i = p$ and there is no tie. $i$ still wins with an earlier arrival (until the next-earliest agent becomes the trigger), with a higher value, and is unaffected by departure. Price $q$ .

Step 5: Payments are critical values ( $q$ , $p$ , $q$ ). The policy is monotonic-late: in (b) the critical value is infinite for departures before the transition and constant after, so the critical departure is the transition. In (c) and (d) the price is departure-independent, so the critical departure is the arrival.

∎

ExampleExample 16.22 — the same six agents under Auction 3

The transition happens at agent 2’s arrival (period 3), with $p=6$ , $q=2$ . Agent 1 is still present, so it wins for 2.

Now suppose agent 1’s true type were $(1,2,6)$ . It has left by period 3, so the item goes to agent 4 in period 6 for 6. Could it gain by claiming $(1,7,6)$ ? It would win, but not until period 3, after its true departure. Monotonic-late bites.

TheoremTheorem 16.23 — competitive ratios

As $N\to\infty$ , Auction 3 is $(e + o(1))$ -competitive for efficiency and $(e^2 + o(1))$ -competitive for revenue.

ProofLower-bound the probability of the “good” event in each branch

Let $\tau = N/e$ .

Efficiency: the ratio is at least $\Pr[\text{sell to the highest value}]$ .

Given a sale at the transition: $\ge (N/e)/N = 1/e - o(1)$ .
Given a sale after it: $1/e - o(1)$ , by the classical secretary analysis.

Revenue: the ratio is at least $\Pr[\text{sell to the highest at the second-highest price}]$ .

At the transition: both top values arrive before $\tau$ , with probability $(1/e)^2 - o(1)$ .
After it: the second-highest arrives before $\tau$ and the highest after, with probability $(1/e)(1-1/e) - o(1)$ .

The key step: the unconditional probability is a weighted average of the branches, so it is at least the smaller one, $(1/e)^2 - o(1)$ .

∎

NoteLower bound, stated without proof

No stopping rule beats success probability $1/e$ asymptotically, and the same $1/e$ bound holds here. This is so even though the mechanism sees values, not ranks, and a non-highest winner still earns partial efficiency. The proof is beyond scope. The sketch in the chapter: some hard distribution makes the second-highest value much smaller than the highest with high probability, so efficiency is driven by the chance of picking the top.

ImportantRandom ordering is essential

Under the fully adversarial model used for expiring items, no constant- competitive mechanism exists for limited supply.

Beyond the basic characterization

Ex-post IC vs DSIC

DefinitionEx-post IC (EPIC)

Truth is a best response given that others are truthful, whatever their types, and hence for all possible futures.

Offline with private values, EPIC and DSIC coincide. They still coincide for closed online mechanisms. If the mechanism gives feedback (prices, or even current bids), a later agent can condition on earlier reports. Monotonicity then gives EPIC but not necessarily DSIC.

ExampleA “crazy” conditional strategy under public bids

Auction 2 with $(1,2,100), (1,2,80), (2,2,60)$ . Agent 3 plays: “bid $(2,2,1000)$ if I see $(1,2,100)$ , else bid $(2,2,60)$ .”

Agent 1 truthful: agent 3 bids 1000, so agent 1 must beat agent 2 in period 1. It pays 80.
Agent 1 bids $(1,2,90)$ : agent 3 bids 60, so agent 1 could win period 2 for anything above 60. It pays 60.

Truth isn’t dominant, but it is still a best response when everyone else is truthful.

Price-schedule auctions

AlgorithmTruthful auctions from agent-independent price schedules

Fix a schedule $q_i^t(L, \theta_{-i}, \omega)$ . Let

p_{(a_i,d_i,L_i)}(\theta_{-i},\omega) = \min_{t\in[a_i,d_i]} q_i^t(L_i,\theta_{-i},\omega),

and let $t^*$ be the first period in the window attaining it. Serve $i$ iff $r_i \ge q_i^t$ for some $t$ in the window, and only at a period $t \ge t^*$ . This is monotonic-late with critical value $p$ .

ExampleExample 16.24 — not every monotonic-late policy is a price schedule

Expiring items with $v^c_{(1,2)} = 20$ and $v^c_{(1,1)} = v^c_{(2,2)} = 30$ . The policy serves $(1,2,25)$ in period 2, but not $(1,1,28)$ or $(2,2,28)$ . A schedule would need $q^1 > 28$ , $q^2 > 28$ and $\min(q^1,q^2) \le 25$ , which is impossible.

The role of limited misreports

In Example 16.24 the period-2 price depends on the report: 30 for window $(2,2)$ but 20 for $(1,2)$ . This violates agent-independent prices, and even weak monotonicity, which is normally necessary for truthfulness.

DefinitionWeak monotonicity (footnote)

If $f(\theta_i,\theta_{-i}) = a$ and $f(\theta'_i,\theta_{-i}) = b$ , then $v_i(b,\theta'_i) - v_i(b,\theta_i) \ge v_i(a,\theta'_i) - v_i(a,\theta_i)$ . In the example, moving from $(1,2,25)$ to $(2,2,28)$ raises the relative value of a period-2 allocation, yet the policy switches away from it.

ImportantWhy it’s still truthful

The agent $(2,2,28)$ can’t report $(1,2,28)$ : that would be an early arrival. For transitive misreport sets (if $\theta'' \in C(\theta')$ and $\theta' \in C(\theta)$ then $\theta'' \in C(\theta)$ , which holds for no-early and no-late), the price for outcome $k$ must be

p_i(k,\theta_i,\theta_{-i},\omega) = \min\{p_i(k,\hat\theta_i, \theta_{-i},\omega) : \hat\theta_i \in C(\theta_i),\ \pi(\hat\theta_i, \theta_{-i},\omega) = k\},

or $\infty$ if no such report exists. Prices may depend on the report as long as they are constant across the agent’s available misreports. With unlimited misreports this collapses back to agent-independent prices.

IntuitionThe blessing and the curse of time

Time justifies limited misreports, which buy flexibility in pricing and in timing allocations. Time also forces decisions in ignorance of the future.

Unknown interesting sets

If $L_i$ is private, make three changes:

the sets in $\mathcal{L}_i$ must be pairwise disjoint;
the policy must be minimal: it never makes a decision in some $L \succ_L L_i$ in the window;
extend the order to $\theta_1 \preceq_\theta \theta_2 \iff (a_1\ge a_2)\wedge(d_1\le d_2) \wedge(r_1\le r_2)\wedge(L_1 \succeq_L L_2) \tag{16.11}$ and define monotonicity with it.

Then monotonic, minimal, deterministic policies with critical payments are truthful, and monotonicity is necessary among minimal deterministic policies. This is left as an exercise.

WarningDisjointness kills substitutes

With fruit $G = \{\text{apple, banana, pear, lime, lemon}\}$ , known sets can express “any of these.” With private sets you must fix a partition, e.g. $\{\{\text{apple, pear}\}, \{\text{banana}\}, \{\text{lime, lemon}\}\}$ . Each agent wants exactly one block. “Apple, or banana, or either” can’t be modeled; this is an open problem.

Stochastic policies

Randomization matters for sampling-based planning and for anonymous tie-breaking. General DSIC for stochastic policies means truth maximizes expected utility (over the policy’s coins) for all others’ reports and all $\omega$ . Let $\pi_i(\theta_i,\theta_{-i},\omega) \in [0,1]$ be the allocation probability.

DefinitionStochastic monotonicity

For all $\theta_i$ , $\theta_{-i}$ , $\omega$ :

\pi_i((a_i,d_i,(r'_i,L_i)),\cdot) \ge \pi_i((a_i,d_i,(r_i,L_i)),\cdot) \quad \forall\, r'_i \ge r_i, \tag{16.12}

\int_0^{r_i} \pi_i((a_i,d_i,(x,L_i)),\cdot)\,dx \ge \int_0^{r_i} \pi_i((a'_i,d'_i,(x,L_i)),\cdot)\,dx \quad \forall\, a'_i\ge a_i,\ d'_i\le d_i. \tag{16.13}

Critical value (an expected payment):

v^c_{(a_i,d_i,(r_i,L_i))}(\theta_{-i},\omega) = \pi_i(\theta,\omega)\,r_i - \int_0^{r_i} \pi_i((a_i,d_i,(x,L_i)),\theta_{-i},\omega)\,dx. \tag{16.14}

IntuitionWhat (16.13) compares

$\int_0^{r}\pi\,dx$ is the expected utility of a truthful agent with reward $r$ (Myerson-style). (16.13) says the weaker window earns at least as much utility as any tighter window at every reward level, so no one wants to claim a tighter window. Pointwise allocation probabilities needn’t be ordered.

TheoremTheorem 16.25 — stochastic characterization

A stochastic policy is implementable by a truthful, IR mechanism that doesn’t pay losers (known interesting set, single-valued, no early arrival, no late departure) iff it satisfies (16.12) and (16.13). The payment is (16.14).

ExampleExample 16.26 — pointwise non-monotone, still truthful

$T = \{1,2\}$ , types $(1,1,w)$ , $(1,2,w)$ , $(2,2,w)$ .

Type	$\pi_i$	expected payment (16.14)
impatient $(1,1,w)$ , $(2,2,w)$	$0$ ( $w\le8$ ); $\frac{w-8}{2}$ ( $8<w\le10$ ); $1$ ( $w>10$ )	$0$ ; $\frac{w^2}{4}-16$ ; $9$
patient $(1,2,w)$	$\frac{w}{20}$ ( $w\le10$ ); $\frac{w-5}{10}$ ( $10<w\le15$ ); $1$ ( $w>15$ )	$\frac{w^2}{40}$ ; $\frac{w^2}{20}-\frac52$ ; $8.75$

At $w=10$ : the impatient type is served surely for 9, and the patient type with probability $0.5$ for expected payment 2.5. The patient type is served less often, but prefers truth: it gets $5 - 2.5 = 2.5$ versus $10 - 9 = 1$ from claiming $(1,1,10)$ .

Check of (16.13) at large $w$ : $\int_0^w \pi(1,2,x)\,dx = w - 8.75 \ge w - 9 = \int_0^w \pi(1,1,x)\,dx$ . The full check is left as an exercise.

RemarkBayesian monotonicity is weaker

With a common-knowledge prior over types and $\omega$ , it suffices that (16.12)–(16.13) hold in expectation. This yields BNIC, not DSIC: off equilibrium, the prior behind the expectation is wrong.

Model-based: the dynamic VCG mechanism

The problem. Beyond single-valued preferences, monotonicity methods run out. With a correct, common-knowledge model of types and events, we can aim for expected-value-maximizing sequential decisions, and make them truthful with a dynamic analogue of VCG.

MDPs

DefinitionMarkov decision process

$(H, K, P, R)$ : states $H$ ; feasible decisions $K(h)$ ; transitions $P(h^{t+1} \mid h^t, k^t)$ summing to 1; reward $R(h^t,k^t)$ . Markov property: feasibility, transitions and rewards depend on the past only through the current state. It holds trivially with $h^t = (\theta^{\le t}; \omega^{\le t}; k^{<t})$ ; in practice a compact summary suffices.

For total value, $R(h^t,k^t) = \sum_{i\in I(h^t)} R_i(h^t,k^t)$ with $v_i(\theta_i,k) = \sum_{t=a_i}^{d_i} R_i(h^t,k^t)$ .

FormulaPolicy value and Bellman optimality

Finite horizon: $V^\pi(h^t) = \mathbb{E}_\pi\{\sum_{\tau=t}^{|T|} R(h^\tau,\pi^\tau(h^\tau)) \}$ . Infinite horizon with a common discount $\gamma\in(0,1)$ : $V^\pi(h^t) = \mathbb{E}_\pi\{\sum_{\tau\ge t}\gamma^{\tau-t} R(h^\tau,\pi^\tau(h^\tau))\}$ .

V^*(h) = \max_{k\in K(h)}\Big[R(h,k) + \sum_{h'\in H^{t+1}} P(h'\mid h, k)\,V^*(h')\Big], \tag{16.19}

\pi^*(h) \in \arg\max_{k\in K(h)}\Big[R(h,k) + \sum_{h'} P(h'\mid h,k) \,V^*(h')\Big]. \tag{16.20}

IntuitionBellman in words

Best value from here = best choice of (reward now + expected best value from wherever that choice sends you).

WarningThe state contains private types

$\pi^*$ is only optimal if the state it sees is the true state. So incentive compatibility is exactly what makes the planner’s view correct.

ExampleExample 16.27 — ice cream as an MDP

State and decisions as in Example 16.3. $P$ encodes the model of new arrivals and the allocation. $R(h^t,k^t) = w_i$ if the cone goes to present agent $i$ , else 0.

The mechanism

AlgorithmAuction 4 — dynamic VCG (finite horizon, no discounting)

Past decisions and reports are public (similar analysis holds without this).

Agent $i$ reports $\hat\theta_i$ in some period $\hat a_i \ge a_i$ .
Implement $\pi^*$ , treating the reported state as true.
At reported departure $t = \hat d_i$ , collect

x_i^t(h^t) = v_i\big(\hat\theta_i, \pi^*(\theta^{\le t},\omega^{\le t}) \big) - \Big[V^*(h^{\hat a_i}) - V^*(h^{\hat a_i}_{-i})\Big], \tag{16.21}

where $h^t_{-i}$ is the counterfactual state with $i$ removed. Zero otherwise.

IntuitionPay your value, get rebated your expected marginal contribution

$V^*(h^{\hat a_i}) - V^*(h^{\hat a_i}_{-i})$ is the expected marginal value $i$ adds to the system, estimated on arrival. $i$ pays its realized value minus this. So truthful $i$ ‘s expected utility equals its expected marginal contribution. This is the Clarke-pivot idea with “welfare” replaced by “optimal expected continuation value.”

Two technical conditions:

Stalling: delaying an agent’s report can’t improve $\pi^*$ ‘s expected value. This holds automatically if the policy could itself delay any decisions pertaining to that agent.
Independence: the arrival process of others doesn’t depend on whether $i$ has arrived.

TheoremTheorem 16.28 — dynamic VCG is BNIC and efficient

With a stalling policy, dynamic VCG is BNIC and implements the expected- value-maximizing policy, with no early-arrival misreports and arbitrary departure misreports.

ProofUtility = total welfare + an agent-independent term

Evaluate $i$ ‘s expected utility from period $a_i$ for a misreport that delays arrival by $c \ge 0$ periods:

\underbrace{\mathbb{E}_{\pi^*}\{v_i(\theta_i,\pi^*(h^{a_i})) \mid\hat\theta_i\}}_{(A)} + \underbrace{\mathbb{E}_{\pi^*}\Big\{ \sum_{t=a_i+c}^{|T|} R_{-i}(h^t,\pi^*(h^t))\Big\}}_{(B)} - \underbrace{\mathbb{E}_{\pi^*}\{V^*(h^{a_i+c}_{-i})\}}_{(C)}.

Step 1: Match terms to the payment.

(A) is $i$ ‘s true value from the outcome its report induces.
(B) is the others’ realized value from its reported arrival onward. It is the expectation of $-v_i(\hat\theta_i,\cdot) + V^*(h^{\hat a_i})$ in the payment.
(C) is the counterfactual value without $i$ , the last payment term.

Step 2: Shift the early periods. Add $\mathbb{E}\{\sum_{t=a_i}^{a_i+c-1} R_{-i}\}$ to (B) and subtract it from (C). The new (C′) covers the others’ value from $a_i$ in a world where $i$ hasn’t reported, and then without $i$ . By independence, (C′) doesn’t depend on $i$ ‘s report, so ignore it.

The key step: (A) + (B′) is $i$ ‘s true value plus everyone else’s value from $a_i$ on, i.e. the true total welfare. $\pi^*$ maximizes exactly this given the true state when others report truthfully. So $i$ maximizes its own utility by reporting truthfully and immediately. Stalling guarantees that delay can’t help.

∎

WarningBNIC, not DSIC

Correctness of $\pi^*$ rests on the center’s model being right. An agent whose beliefs differ from the center’s may believe it gains by misreporting (misrepresenting the state). Incentives also rely on future on-equilibrium play by everyone.

NoteIR and budget (footnotes)

Ex-post IR holds under agent-monotonicity: adding an agent never lowers the MDP value of any state.
Payments are nonnegative in expectation (ex ante budget balance) under no positive externalities: an arrival doesn’t raise others’ expected value.
The mechanism remains BNIC even without the no-early-arrival assumption.

Remarks

RemarkComputation

Exact MDP solutions (dynamic programming, value iteration, policy iteration, LP) don’t scale to real state spaces. Pair VCG with an online sampling-based approximation that plans forward from the current state only.

An $\epsilon$ -approximation gives $\epsilon$ -BNIC: no agent gains more than $\epsilon$ , if others are truthful and $\epsilon$ -accurate value estimates are available.
Sparse sampling builds a lookahead tree. Its cost is independent of the state-space size but exponential in the number of decisions and in the horizon.
Stochastic online combinatorial optimization handles MDPs whose uncertainty is independent of decisions. This is natural for IC auctions: allocations don’t change what types arrive.

RemarkInfinite horizon

With a common discount factor, collect payments every period, aligning $i$ ‘s utility stream with the expected marginal value stream it contributes.

RemarkCoordinated learning

When decisions reveal information about types (types learned online), a VCG variant supports efficient multi-agent bandits. Each agent owns an arm with private reward signals. Gittins’ index policy gives the efficient explore/exploit rule (infinite horizon, discounting), and dynamic-VCG-style payments make truthful reporting of signals incentive compatible.

Open problems

Revenue in model-based settings: an online analogue of Myerson’s optimal auction is only partially solved, even in the simplest settings (see revenue-maximization).
Learning by the center: improve the type model over time while staying IC along the learning path, converging to efficient or optimal mechanisms.
Solution concepts between DSIC and BNIC that avoid common-knowledge priors: set Nash, undominated strategies, minimax regret.
Endogenous information: decisions affect what agents learn about their own types.
Richer domains: substitutes across non-partition sets, budgets, interdependent values, and ultimately online combinatorial auctions and exchanges.

Quick reference

Object	Statement	Note
Expiring items type	$(a_i,d_i,w_i)$ , one unit in window	Jane’s ice cream
Auction 1	greedy, second price this period	not truthful (Ex. 16.1)
Def 16.2	$M=(\pi,x)$ , one report, $\pi^t(h^t)\in K(h^t)$	closed = no feedback
Limited misreports	no early: $a_i\le\hat a_i$ ; no late: $\hat d_i\le d_i$	reports only tighten the window
DSIC / strong truthful / BNIC	truth dominant / for every coin / best reply under a prior
Revelation principle	fails with late-departure misreports (Ex. 16.7)	holds with no-late, or with heartbeats
Single-valued (16.1)	value $r_i$ for any interesting decision in window	known $L_i$
$\preceq_\theta$ (16.2)	later arrival, earlier departure, lower reward	”harder, worth less”
Critical value (16.3)	min reward still served	independent of $r_i$
Lemma 16.12	$v^c$ weakly increases as window tightens	monotone $\pi$
Thm 16.13	monotone + critical payment at departure ⇒ truthful	no early, no late
Lemma 16.14	truthful + IR ⇒ pay exactly $v^c$
Thm 16.15	truthful + IR + losers unpaid ⇒ monotone	fails if losers paid
Monotonic-late	monotone + no service before critical departure	iff with arbitrary departures
Auction 2	greedy + critical payments	Ex. 16.16: both pay 60
Thm 16.17	Auction 2 strongly truthful, 2-competitive	charging, ≤2 charges each
Thm 16.18	no truthful deterministic $(2-\epsilon)$	1.618 algorithm exists, not monotone
Thm 16.19	late departures ⇒ no constant ratio	patient agents served in period 1
Secretary rule (16.9)	sample $\approx N/e$ , take next best-so-far	success $\to 1/e$
Auction 3	learn $N/e$ ; sell to present top at $q$ , else next $\ge p$ at $p$	Ex. 16.20 straw man fails
Thm 16.21	Auction 3 strongly truthful, monotonic-late	no early arrival
Thm 16.23	$e$ -competitive efficiency, $e^2$ revenue	random ordering essential
EPIC vs DSIC	equal for closed mechanisms; feedback breaks DSIC
Price schedules	$p=\min_{t\in\text{window}} q^t$ , serve at $t\ge t^*$	not fully general (Ex. 16.24)
Limited-misreport pricing	price constant over available misreports	transitive $C$
Unknown $L_i$	disjoint sets + minimal policy + extended order (16.11)	no substitutes
Stochastic monotonicity	(16.12) in reward; (16.13) integral over window	Thm 16.25 iff
Critical value (16.14)	$\pi r_i - \int_0^{r_i}\pi\,dx$	expected payment
Bellman (16.19)–(16.20)	$V^* = \max_k[R + \mathbb{E}V^*]$
Dynamic VCG (16.21)	pay value minus $V^(h^{\hat a_i}) - V^(h^{\hat a_i}_{-i})$	on departure
Thm 16.28	dynamic VCG BNIC, efficient	stalling + independence
IR / BB	agent-monotonicity / no positive externalities	footnote

Facts to keep to hand

Every DSIC result is monotonicity + critical value. The online twist is that the order on types includes the window. Tighter window, like lower reward, is “worse.”
Limited misreports do two jobs. They make monotonicity sufficient, since agents can only move down the order in the window dimension. They also permit report-dependent prices that would be illegal offline (Ex. 16.24).
Every attack in the chapter is a timing attack. Delay arrival to enter a cheaper auction (Ex. 16.1, 16.20). Claim a later departure to face a lower price (Thm 16.19). Each fix neutralizes one: critical payments, the transition sale, monotonic-late.
Truthfulness costs a factor. For expiring items: 1.618 algorithmically vs 2 truthfully. With late departures, no constant at all.
The adversary model decides what is possible. Limited supply has no constant ratio against a fully adversarial input, but $e$ / $e^2$ under random ordering.
Each weakening of the solution concept buys generality. Strong truthful → DSIC (randomization in expectation) → EPIC (feedback) → BNIC (a common prior buys general preferences and the MDP-optimal policy).
Dynamic VCG = VCG with “welfare” replaced by “optimal expected continuation value.” The proof is the usual one: utility = total welfare
- an agent-independent term. Stalling handles delay, and independence makes the counterfactual term agent-independent.

References

Nisan, Roughgarden, Tardos, Vazirani, Algorithmic Game Theory — chapter 16 (Parkes)

Related