Bounded local menus enable near-optimal matching under independent arrivals
Locally Sparsified, Globally Near-Optimal: Matching under Independent Vertex Arrivals
Data Structures and Algorithms
Summary
Sometimes, systems match tasks to resources by limiting each task to a few possible options before making global decisions. This paper shows that even if each task keeps only a small, fixed number of options selected independently, it is still possible to match almost as well as if all options were available. The authors provide simple methods to choose these small menus using any reference matching plan, ensuring near-best overall matching without complicated global coordination. Their approach works even when the way matches spread across options is unrestricted.
What this means in practice
- •For network schedulers: Improve scheduling by limiting each request’s options to a small menu without losing near-optimal resource assignments.
- •For online ad operators: Reduce complexity in ad placement systems by preselecting few candidate ads per user while maintaining near-optimal matching of ads to users.
Authors
Sara Ahmadian, Edith Cohen, Mohammad Roghani
Abstract
Resource allocation systems often restrict each request to a short list of options before coordinating assignments globally. We study this separation in stochastic bipartite matching under independent vertex arrivals. Each request draws a state from its own known distribution, determining its compatible resources, and independently retains a menu of at most $k$ edges. A maximum matching is then computed on the retained graph. We show that bounded local menus universally suffice for near-optimal matching. For every $\varepsilon>0$, there is a menu size $k_\varepsilon$ depending only on $\varepsilon$ that preserves at least a $(1-\varepsilon)$ fraction of the expected maximum-matching size of the full realized graph. Earlier guarantees required additional assumptions on how matching mass is distributed across edges; our result resolves the unrestricted case. Moreover, the menus are simple to generate from any benchmark matching rule, either by weighted sampling according to the benchmark's edge marginals, or by applying the benchmark to sampled realizations and retaining the resulting partners. Our proof constructs a near-optimal certificate inside the sparsifier by combining a \emph{locally computable} surrogate for the large-marginal edges with a fractional completion from sampled light edges. The surrogate nearly preserves the benchmark's value and endpoint loads while controlling dependencies, which makes the statistical light-edge completion possible.