Abstract
In this paper, we generalize the recently studied stochastic matching problem to more accurately model significant medical and social processes, such as kidney exchange, online freelancing, and online dating. Previous models of stochastic matching assumed that edges in a graph $G = (V, E)$ are realized independently with probability $p_e$. However, these models fail to account for vertex dropouts—where a patient, donor, or user opts out entirely—which introduces complex dependencies between edges. We propose a generalized model where both vertices and edges are realized independently with probabilities $p_v$ and $p_e$, respectively. We provide the first algorithms and theoretical analysis for this generalization, proving approximation ratios of 0.6568 for unweighted graphs and $1/2 + \epsilon$ for weighted graphs. Furthermore, we improve the unweighted bound to $2/3$ using Edge Degree Constrained Subgraphs (EDCS).
Introduction
Matching problems are fundamental to computer science, with applications ranging from resource allocation to market design. In many real-world scenarios, the underlying graph is not known with certainty. The stochastic matching problem addresses this by assuming a "master graph" where edges exist only with a certain probability. The goal is to select a sparse subgraph $Q$ (with bounded degree) such that the expected maximum matching in the realized version of $Q$ is a good approximation of the expected maximum matching in the realized version of the full graph $G$.
While previous research has focused on edge-level uncertainty, this paper identifies a critical gap: vertex-level uncertainty. In kidney exchanges, a patient or donor may become unavailable due to health changes, effectively removing them and all their incident edges from the graph. Similarly, in online labor markets, a profile may be found to be fraudulent. This paper introduces a generalized model that accounts for both vertex ($p_v$) and edge ($p_e$) realization probabilities, creating a more robust framework for these volatile environments.
The Generalized Stochastic Matching Model
In the traditional model, edges are independent. In our generalized model, a vertex $v$ is realized with probability $p_v$, and an edge $e=(u,v)$ is realized with probability $p_e$. An edge $e$ exists in the final graph only if both its endpoints $u$ and $v$ are realized and the edge itself is realized.
This dependency structure significantly complicates the analysis. If a vertex $v$ fails to realize, all edges incident to $v$ are lost simultaneously. This correlation means that the standard techniques used to prove approximation ratios for edge-independent models no longer apply directly. The challenge lies in selecting a subgraph $Q$ that remains resilient to these correlated failures.
Algorithmic Framework
Algorithm 1: Sampling and Union
The primary approach involves a sampling-based algorithm. The process follows four main steps:
- Sampling: Generate $R$ independent samples of the realized graph based on the probabilities $p_v$ and $p_e$.
- Matching: For each sample, compute the maximum weighted matching.
- Union: Construct the subgraph $Q$ as the union of all edges found in these matchings.
- Querying: In the actual realized graph, query the edges in $Q$ to find the final matching.
To ensure $Q$ remains sparse while maintaining high quality, the authors utilize a "scaling-factor" procedure. They categorize edges into crucial (highly likely to be in an optimal matching) and non-crucial (low probability). By managing a "vertex budget"—the number of times a vertex can be included in $Q$—the algorithm prioritizes edges that contribute most to the expected matching size.
Edge Degree Constrained Subgraphs (EDCS)
For unweighted graphs, the authors employ EDCS. An EDCS is a subgraph where the sum of the degrees of the endpoints of any edge is constrained within a specific range. This structure is known to maintain a large matching relative to the original graph while keeping the maximum degree of the subgraph small. By adapting EDCS to the stochastic setting, the authors achieve a tighter approximation bound.
Theoretical Results
This research provides the first known lower bounds for the approximation ratio in the generalized stochastic matching model:
- Unweighted Graphs: The sampling-based approach achieves an approximation ratio of 0.6568.
- Weighted Graphs: The algorithm achieves a ratio of 0.501, successfully breaking the "half-approximation" barrier ($0.5$) that typically limits greedy or simple sampling approaches.
- Improved Unweighted Bound: By utilizing the EDCS technique, the approximation ratio for unweighted graphs is improved to 2/3 (~0.666).
These results demonstrate that even with the added complexity of vertex dropouts, it is possible to pre-select a small set of potential matches that capture a significant portion of the optimal expected matching.
Discussion and Future Work
While this paper significantly advances the state of stochastic matching, a gap remains between these results and the $(1-\epsilon)$ approximations possible in edge-only models. The dependency introduced by vertex realization remains a formidable theoretical hurdle.
Future research may focus on narrowing this gap or exploring the weighted case further, as the $0.501$ result, while theoretically significant for breaking the $0.5$ barrier, leaves room for improvement. Additionally, applying these generalized models to specific real-world constraints—such as the short cycle requirements in kidney exchange—presents a vital path for practical implementation.
Summary updated