Stochastic Matching via Local Sparsification
For decentralized systems with local communication bottlenecks (e.g., ride-hailing, cloud computing), this provides a principled way to achieve near-optimal global matching with strict local budgets.
The paper introduces a two-stage local sparsification framework for online stochastic matching where each request must reduce its compatibility set to k edges before global matching. They propose a local selection strategy that, under sufficient spread, preserves the expected maximum matching size, and empirically show near-optimal performance on NYC ride-hailing data and synthetic benchmarks.
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 {\em 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 ride-hailing 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.