Stochastic Matching via Local Sparsification

Technical Summary: Stochastic Matching via Local Sparsification

Problem Definition
The paper addresses the classic online stochastic matching problem, traditionally characterized by the requirement for immediate and irrevocable decisions. However, the authors argue that in modern decentralized systems (e.g., ride-hailing, distributed cloud computing), the primary bottleneck is often local communication bandwidth and memory limits rather than the timing of the match itself.

To formalize this, the authors introduce a two-stage local sparsification framework:

1. Local Pruning: Upon arrival, each request $u_i$ observes its compatible resources but must immediately prune its compatibility set to a strict budget of $k$ edges. This decision relies solely on the prior distribution of request types and the realized compatibility set, without coordination with other requests.
2. Global Matching: A central coordinator receives the resulting sparse subgraph (containing only the selected $k$ edges per request) and computes a maximum bipartite matching.

The objective is to design a local selection rule that maximizes the preservation ratio $\alpha = \mathbb{E}[|M(G_S)|] / \mathbb{E}[|M(G)|]$, where $G_S$ is the sparsified graph and $G$ is the full realized graph.

Methodology
The proposed approach leverages offline statistical knowledge to guide local edge selection, moving away from the strict "immediate decision" paradigm of traditional online algorithms.

1. Expected Instance Linear Program (LP): The framework first solves an LP that maximizes the expected matching size over the known distribution of request types. This yields a fractional solution $x^*$ representing the optimal flow of expected demand.
2. Variance-Optimal (VarOpt) Sampling: To convert the fractional solution into a discrete set of $k$ edges for each arriving request, the authors employ VarOpt sampling. Unlike independent Bernoulli sampling, VarOpt is a dependent sampling scheme that ensures the sum of the inverse-probability weights of the selected edges exactly equals the sum of the original fractional weights. This property preserves the expected load on resources while strictly adhering to the hard capacity constraint $k$.
3. Heavy-Light Decomposition: The theoretical analysis partitions the fractional solution edges into:
   • Light Edges ($E_L$): Edges with fractional values $x_{ij} \le 1/k$.
   • Heavy Edges ($E_H$): Edges with fractional values $x_{ij} > 1/k$.
     The core insight is that the stochastic collision penalty (which typically limits online algorithms to a $1-1/e$ competitive ratio) is confined exclusively to the heavy edges. Light edges are preserved by the sparsifier essentially without loss.

Key Contributions

• Theoretical Approximation Guarantee: The authors prove that if the fractional solution is "well-spread" (i.e., the heavy component constitutes a small fraction of the total objective), a local budget of $k = \epsilon^{-2}$ guarantees an expected matching size within a $1-\epsilon$ factor of the maximum matching in the realized graph. This effectively bypasses the theoretical limits of strict online matching when the solution geometry is favorable.
• Spread Solutions via Equivalence Classes: The paper demonstrates that in systems with interchangeable resources (e.g., many similar vehicles in a ride-hailing network), one can construct optimal fractional solutions where weights are naturally spread across equivalent resources, minimizing the heavy component.
• Monte Carlo Heuristic: A practical method is proposed to construct these high-spread fractional solutions. By repeatedly sampling realizations of the stochastic instance, computing offline optimal matchings with random tie-breaking, and averaging the edge incidences, the algorithm generates weights that guide the local VarOpt sparsifier.
• Bypassing the 0.901 Barrier: The authors show that by returning a subgraph of size $k > 1$, their algorithm fundamentally bypasses the theoretical efficiency barrier of $\approx 0.901$ established for traditional online stochastic matching algorithms (which must commit to a single edge immediately).

Experimental Results
The framework was validated using two distinct environments:

1. Real-World Ride-Hailing (NYC Taxi Data): Using a simulation based on NYC Yellow Taxi trip data, the proposed VarOpt Local Sparsifier (with $k=5$ and $k=10$) significantly outperformed standard online baselines (KVV Ranking, MGS) and naive random subgraph selection. The performance closely tracked the full-information offline optimal matching, demonstrating that near-optimal global matching is achievable with highly constrained local budgets.
2. Synthetic Adversarial Benchmarks: The algorithm was tested against structured hard examples known to challenge online algorithms (e.g., Partitioned Block Graphs, TSM Tightness Graphs, and the Bahmani-Kapralov Upper-Bound Graph). In these tests, the VarOpt sparsifier consistently achieved high approximation ratios (often exceeding 95-99%), significantly outperforming the theoretical limits of strict online commitment.

Significance and Claims
The paper claims to introduce a "middle ground" between local information constraints and global optimization utility. By formalizing the problem as a local sparsification task, the authors demonstrate that the strict requirement for immediate, irrevocable decisions is not necessary to achieve high efficiency in stochastic settings, provided that local decisions are guided by a well-spread global plan.

The work highlights that the "stochastic collision penalty" is not an inherent limitation of the matching problem itself but rather a consequence of concentrated fractional solutions and immediate commitment. By utilizing dependent sampling (VarOpt) and constructing spread solutions, the framework allows decentralized systems to recover near-optimal global matchings despite severe local communication bottlenecks. The authors note that while their analysis relies on the "well-spread" assumption, the algorithm remains robust even when this assumption is partially violated, as evidenced by performance on adversarial synthetic benchmarks.