Generalized Stochastic Matching

Alireza Farhadi, Jacob Gilbert, MohammadTaghi Hajiaghayi

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

Abstract

In this paper, we generalize the recently studied Stochastic Matching problem to more accurately model a significant medical process, kidney exchange, and several other applications. Up until now the Stochastic Matching problem that has been studied was as follows: given a graph G = (V, E), each edge is included in the realized sub-graph of G mutually independently with probability p_e, and the goal is to find a degree-bounded sub-graph Q of G that has an expected maximum matching that approximates the expected maximum matching of the realized sub-graph. This model does not account for possibilities of vertex dropouts, which can be found in several applications, e.g. in kidney exchange when donors or patients opt out of the exchange process as well as in online freelancing and online dating when online profiles are found to be faked. Thus, we will study a more generalized model of Stochastic Matching in which vertices and edges are both realized independently with some probabilities p_v, p_e, respectively, which more accurately fits important applications than the previously studied model. We will discuss the first algorithms and analysis for this generalization of the Stochastic Matching model and prove that they achieve good approximation ratios. In particular, we show that the approximation factor of a natural algorithm for this problem is at least $0.6568$ in unweighted graphs, and $1/2 + \epsilon$ in weighted graphs for some constant $\epsilon > 0$. We further improve our result for unweighted graphs to $2/3$ using edge degree constrained subgraphs (EDCS).
BibTeX
@inproceedings{farhadi2022generalized,
  author = {Alireza Farhadi and Jacob Gilbert and MohammadTaghi Hajiaghayi},
  title = {{Generalized Stochastic Matching}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=qjeFUkzoqVk},
}
Figure