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 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:

  1. Sampling: Generate $R$ independent samples of the realized graph based on the probabilities $p_v$ and $p_e$.
  2. Matching: For each sample, compute the maximum weighted matching.
  3. Union: Construct the subgraph $Q$ as the union of all edges found in these matchings.
  4. 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

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 independently with probability pe, 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 G. 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 pv, pe, 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+ε in weighted graphs for some constant ε >0. We further improve our result for unweighted graphs to 2/3 using edge degree constrained sub-graphs (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