Stochastic Matching via Local Sparsification
Abstract
The classic online stochastic matching problem typically requires immediate and
irrevocable matching decisions. However, in many modern decentralized systems
such as real-time ride-hailing and distributed cloud computing, the primary bottleneck is often local communication bandwidth rather than the timing of the match
itself. We formalize this challenge by introducing a two-stage local sparsification
framework. In this setting, arriving requests must prune their realized compatibility
sets to a strict budget of k edges before a central coordinator optimizes the global
matching. This creates a ”middle ground” between local information constraints
and global optimization utility.
We propose a local selection strategy, parametrized by a fractional solution of the
expected instance. Theoretically, we quantify the approximation ratio as a function
of the solution’s spread. We prove that under sufficient spread, our sparsifier
globally preserves the expected size of the maximum matching. Empirically,
we demonstrate the robustness of our approach using the New York City ridehailing datasets and adversarial synthetic benchmarks. Our results show that near-optimal global matching is achievable even with highly constrained local budgets, significantly outperforming standard online baselines.
irrevocable matching decisions. However, in many modern decentralized systems
such as real-time ride-hailing and distributed cloud computing, the primary bottleneck is often local communication bandwidth rather than the timing of the match
itself. We formalize this challenge by introducing a two-stage local sparsification
framework. In this setting, arriving requests must prune their realized compatibility
sets to a strict budget of k edges before a central coordinator optimizes the global
matching. This creates a ”middle ground” between local information constraints
and global optimization utility.
We propose a local selection strategy, parametrized by a fractional solution of the
expected instance. Theoretically, we quantify the approximation ratio as a function
of the solution’s spread. We prove that under sufficient spread, our sparsifier
globally preserves the expected size of the maximum matching. Empirically,
we demonstrate the robustness of our approach using the New York City ridehailing datasets and adversarial synthetic benchmarks. Our results show that near-optimal global matching is achievable even with highly constrained local budgets, significantly outperforming standard online baselines.
Research Areas
