Abstract
In this paper, we generalize the recently studied Stochastic Matching problem to more accurately model significant medical and economic processes, such as kidney exchanges, online freelancing, and online dating. Previous models of Stochastic Matching assumed that while edges in a graph $G = (V, E)$ are realized independently with probability $p_e$, the vertices are always present. This does not account for vertex dropouts, which occur when donors opt out of exchanges or online profiles are found to be fraudulent. We introduce a generalized model where both vertices and edges are realized independently with probabilities $p_v$ and $p_e$, respectively. We present the first algorithms and analysis for this generalization, proving that they achieve significant approximation ratios. Specifically, we show that a natural sampling algorithm achieves at least a $0.6568$ approximation in unweighted graphs and $1/2 + \epsilon$ in weighted graphs. Furthermore, we improve the unweighted result to $2/3$ using Edge Degree Constrained Subgraphs (EDCS).
Introduction
Matching problems are fundamental to resource allocation, ranging from pairing kidney donors with patients to connecting freelancers with employers. In many real-world scenarios, the compatibility of a pair is not known with certainty until a "query" or test is performed. Stochastic matching provides a framework for this: given a graph representing potential matches, we seek a sparse subgraph $Q$ 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$.
Historically, research has focused on edge-based uncertainty. However, this paper identifies a critical limitation: the assumption that vertices are always available. In a kidney exchange, a patient or donor might become unavailable for health reasons; in online dating, a profile might be deleted. This paper addresses the Generalized Stochastic Matching problem, where both vertices and edges can fail, creating a complex dependency structure that previous models could not handle.
The Generalized Model
In the generalized model, each vertex $v \in V$ is realized independently with probability $p_v$, and each edge $e \in E$ is realized independently with probability $p_e$. Crucially, an edge $e = (u, v)$ can only exist in the realized graph if both of its endpoints, $u$ and $v$, are also realized.
This introduces a significant mathematical challenge: the loss of edge independence. In traditional models, the existence of one edge provides no information about another. In the generalized model, if an edge $(u, v)$ is known to exist, it implies that both $u$ and $v$ have been realized, which increases the conditional probability that other edges connected to $u$ or $v$ might also exist. This dependency necessitates new algorithmic approaches to ensure that the chosen subgraph $Q$ remains sparse while maintaining a high approximation ratio.
Algorithmic Strategies
The authors propose two primary methods to construct the sparse subgraph $Q$:
1. Sampling-based Matching
This approach involves repeatedly sampling realizations of the original graph $G$ and aggregating their maximum weighted matchings into the subgraph $Q$. The analysis utilizes fractional matching theory to partition edges into "crucial" and "non-crucial" sets. By focusing on edges that are likely to participate in a maximum matching across different realizations, the algorithm ensures that $Q$ captures the most valuable potential connections without exceeding degree bounds.
2. Edge Degree Constrained Subgraphs (EDCS)
For unweighted graphs, the authors employ EDCS, a graph sparsification technique. An EDCS is a subgraph where the sum of the degrees of any two connected vertices is maintained within a specific range. This structure is particularly robust; it is known to preserve large matchings even when the graph is significantly sparsified. The authors demonstrate that EDCS can be adapted to the generalized stochastic setting to provide a stronger approximation than simple sampling.
Key Results
The paper establishes the first rigorous bounds for the Generalized Stochastic Matching problem. Despite the added complexity of vertex-edge dependencies, the authors prove that it is possible to achieve high-quality matchings using subgraphs where each vertex has a constant degree (independent of the total number of vertices $n$).
| Graph Type | Algorithm | Approximation Ratio |
|---|---|---|
| Unweighted | Sampling-based | 0.6568 |
| Weighted | Sampling-based | 0.501 ($1/2 + \epsilon$) |
| Unweighted | EDCS-based | 0.666 (2/3) |
Notably, the $0.501$ result for weighted graphs is the first to break the "0.5 barrier" in the generalized model, a common threshold in matching theory that is difficult to surpass without sophisticated analysis.
Conclusion and Future Work
This work bridges the gap between theoretical stochastic matching and the practical realities of vertex dropouts in medical and economic networks. By providing the first algorithmic bounds for the generalized model, the authors lay the groundwork for more resilient matching systems.
Future research directions include closing the gap between the current results and the $(1 - \epsilon)$ near-optimal approximations available for simpler models. Additionally, there is significant interest in improving the weighted graph bound and exploring more complex dropout scenarios, such as those found in dynamic social networks or supply chain logistics.
Summary updated