Degree and sampling influence online matching performance guarantees
Degree-Parameterized Analysis of Sampling-Based Online Matching
Data Structures and AlgorithmsComputer Science and Game Theory
Summary
This paper looks at how to match items that arrive one by one to a fixed set of options, using some initial samples to set prices. The authors analyze two methods that rely on sampling part of the problem first to improve matching when items come in randomly. They find exact performance limits for these methods based on how many options each item can connect to and how much they sample upfront. Their work improves understanding of how much sampling helps and how stable matches are under different conditions.
What this means in practice
- •For online marketplace operators: Optimize matching of arriving buyers to sellers by tuning sampling strategies based on marketplace connectivity for better value and efficiency.
- •For ad auction platform engineers: Improve bid matching decisions using initial sample data to set dynamic thresholds that account for advertiser demand patterns.
A theory result. No direct application yet.
Authors
Pan Xu
Abstract
We study edge-weighted online bipartite matching under random arrival order, parameterized by the maximum offline degree $d$ and sampling fraction $θ$. We analyze two sampling-based frameworks. For \emph{Deterministic Greedy Sampling}, which computes prices from a fixed-size initial sample and then applies a local threshold rule, we derive an explicit worst-case competitive ratio and prove it tight within this policy family for every fixed $d\ge2$ and $θ\in[0,1]$. The optimal sampling choice interpolates between no sampling for $d=1,2$ and a dense-limit guarantee of approximately $0.2562$, improving on the classical $1/8$ analysis while retaining linear per-arrival time. We also derive worst-case bounds on the variance of the number of matched offline agents, including order-tight behavior as $θ\to1_-$ and an $O(θ)$ bound as $θ\to0_+$ for fixed $m,d$. For \emph{Black-Box Sampling--Matching}, we introduce prefix-dependent reweighting followed by an arbitrary approximate offline matching solver and prove a transfer theorem whose guarantee is the offline approximation ratio times an explicit function of $d$ and $θ$. With exact matching, the framework recovers the classical $1/e$ guarantee in the unbounded-degree limit.