When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings

Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, Atri Rudra

Introduction

In many real-world matching scenarios—ranging from kidney donor exchanges to online dating and digital advertising—decisions must be made under significant uncertainty. When a potential match is identified, its success is not guaranteed; it must be "probed." If the probe succeeds, the parties are matched and removed from the system—a constraint known as irrevocability. Furthermore, participants often have limited patience, represented by a timeout parameter $t_i$, which restricts the number of failed probes they will tolerate before leaving the system.

This paper addresses the weighted stochastic matching problem, where the goal is to maximize the total weight (value) of successful matches. While previous work focused on the unweighted case, the weighted variant presents unique challenges that traditional greedy heuristics fail to solve effectively.

The Problem: Uncertainty and Commitment

The stochastic matching model involves a graph $G=(V, E)$ where each edge $e$ has a weight $w_e$ and a probability of success $p_e$. The constraints are:

  1. Irrevocability: A successful probe results in a permanent match. You cannot "un-match" a pair if a better partner appears later.
  2. Timeouts: Each vertex $v$ has a patience parameter $t_v$. After $t_v$ unsuccessful probes involving $v$, the vertex is removed from the market.

The objective is to find a probing strategy that maximizes the expected total weight. The challenge lies in the "commitment cost": a greedy choice might match a high-value vertex to a low-weight edge simply because it has a high probability of success, preventing a more valuable match from occurring later.

Methodology: The LP Relaxation Framework

The authors move beyond simple greedy approaches by utilizing Linear Programming (LP) relaxation. They formulate an LP where variables represent the probability that an edge is probed. A key theoretical contribution is proving that the optimal value of this LP serves as an upper bound on the performance of any strategy, including fully adaptive ones that make decisions based on all previous probe outcomes.

Rounding Strategies

To convert the fractional LP solution into a concrete probing sequence, the authors propose several rounding techniques:

  1. Random Permutation: Edges are processed in a uniformly random order. An edge is probed only if it is "safe" (neither endpoint is matched or timed out), with a probability scaled by the LP solution.
  2. Dependent Rounding (GKSP): For bipartite graphs, the authors employ Gandhi-Khuller-Parthasarathy-Srinivasan (GKSP) rounding. This technique ensures that the marginal probabilities of probing edges match the LP values while minimizing conflicts between edges sharing a vertex.
  3. Random Partitioning: To extend bipartite results to general graphs, the algorithm randomly partitions vertices into two sets, effectively treating the general graph as a bipartite one. This introduces a small loss in the approximation factor but allows for a unified algorithmic approach.

Key Results and Approximation Bounds

The paper provides the first constant-factor approximation algorithms for several variations of the problem, comparing them against a theoretical optimal adaptive strategy:

  • Bipartite Graphs: A 3-approximation algorithm.
  • General Graphs: A 4-approximation algorithm.
  • Unweighted Matching: An improved bound of 3.46 (down from the previous best of 4).
  • Online Stochastic Matching: A 7.92-approximation for a new model involving online buyers with timeouts.
  • Generalization: The logic extends to stochastic $k$-set packing, achieving a $2k$-approximation.

Insights: The Power of Non-Adaptivity

Perhaps the most significant insight is the efficacy of non-adaptive strategies. The authors demonstrate that a fixed probing order, determined before any probes are made, can perform within a small constant factor of the best possible adaptive strategy. This has profound implications for practical implementation, as non-adaptive algorithms are significantly easier to execute in complex environments.

Furthermore, the "LP as a cure" metaphor highlights why global optimization outperforms local greedy choices. In weighted scenarios, greedy algorithms are often "short-sighted," wasting valuable vertices on high-probability but low-weight matches. The LP framework accounts for the global structure, ensuring that high-weight opportunities are preserved.

Conclusion

By bridging the gap between greedy heuristics and complex adaptive strategies, this work establishes a robust theoretical foundation for stochastic matching. The use of LP relaxation and sophisticated rounding techniques not only provides strong approximation guarantees but also simplifies the operational requirements for matching markets under uncertainty. While the bounds are theoretical, they suggest that simple, LP-based strategies can perform remarkably well in practice.

Summary updated

BibTeX
@article{bansal2012when,
  author = {Nikhil Bansal and Anupam Gupta and Jian Li and Julián Mestre and Viswanath Nagarajan and Atri Rudra},
  title = {{When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings}},
  journal = {Algorithmica2012},
  year = {2012},
  doi = {10.1007/s00453-011-9511-8},
}
Figure