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.
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.