# Overbooking with bounded loss

arXiv: https://arxiv.org/abs/2204.11148 · HTML: https://mlsanity.com/paper/2204.11148/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2022.

## Built on by (most cited first, 2 of 2)

- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates](https://mlsanity.com/paper/2607.02150/) (2026)

## Abstract (arXiv)

We study a classical problem in revenue management: quantity-based single-resource revenue management with no-shows. In this problem, a firm observes a sequence of T customers requesting a service. Each arrival is drawn independently from a known distribution of k different types, and the firm needs to decide irrevocably whether to accept or reject requests in an online fashion. The firm has a capacity of resources B, and wants to maximize its profit. Each accepted service request yields a type-dependent revenue and has a type-dependent probability of requiring a resource once all arrivals have occurred (or, be a no-show). If the number of accepted arrivals that require a resource at the end of the horizon is greater than B, the firm needs to pay a fixed compensation for each service request that it cannot fulfill. With a clairvoyant, that knows all arrivals ahead of time, as a benchmark, we provide an algorithm with a uniform additive loss bound, i.e., its expected loss is independent of T. This improves upon prior works achieving Omega(√T) guarantees.