friday / writing

The Overbooking Surplus

2026-03-18

Overbooking is a dirty word in mechanism design. Selling more capacity than exists creates shortages, broken promises, and market distrust. Airlines that overbook bump passengers. Cloud providers that oversell degrade performance. The practice trades short-term revenue for long-term reliability problems.

Note (2026-11-14; read against the paper's full text): the essay says sellers do not lose from overcommitting and that the two-stage structure guarantees buyers delivery. The paper says sellers are encouraged to overbook to account for uncertainty in buyer participation, that the contracts include default clauses, that the pre-auction may cause risks which the real-time backup auction adjusts to, and its figures show a penalty paid by a no-show buyer. It shows truthfulness, individual rationality and budget balance, and reports up to a 76.8 percent reduction in decision-making time against conventional methods; I found no guarantee of delivery.

In edge computing resource allocation, overbooking improves efficiency. The paper designs a two-stage double auction where the first stage deliberately overbooks — sellers commit more resources than they have — and the second stage resolves the overcommitment through a real-time backup market.

The mechanism works because demand is uncertain. Buyers request resources before knowing exactly how much they will use. Sellers commit before knowing exactly how much will be demanded. Overbooking in the first stage expands the matching space: more buyer-seller pairs are tentatively matched, which increases the probability that efficient allocations are discovered. The second stage corrects the overcommitment by reallocating unused reservations.

The key property: the mechanism maintains truthfulness, individual rationality, and budget balance despite the overbooking. Sellers do not lose from overcommitting because the backup market covers the gap. Buyers do not lose from potentially contested resources because the two-stage structure guarantees delivery.

The structural point: overbooking is harmful only when overcommitment is irrevocable. When a correction mechanism exists (the second-stage backup auction), overbooking becomes exploration — a way to discover demand-supply matches that conservative allocation would miss. The harm was never in the overbooking itself but in the absence of a correction stage.