Online Stochastic Matching: A Polytope Perspective

Céline Comte, Fabien Mathieu, Ana Bušić, Bušić, Ana

Abstract: Stochastic dynamic matching problems have recently gained attention in the stochastic-modeling community due to their diverse applications, such as supply-chain management and kidney exchange programs. In this paper, we study a matching problem where items of different classes arrive according to independent Poisson processes. Unmatched items are stored in a queue, and compatibility between items is represented by a simple graph, where items can be matched if their classes are connected. We analyze matching policies in terms of stability, delay, and long-term matching rate optimization. Our approach relies on the conservation equation, which ensures a balance between arrivals and departures in any stable system. Our main contributions are as follows. We establish a link between the existence of stable policies, the dimensionality of the solution set of the conservation equation, and the compatibility graph's structure. We describe the convex polytope formed by non-negative solutions to the conservation equation, and we design policies that can achieve or closely approximate the vertices of this polytope. Lastly, we discuss potential extensions of our results beyond the main assumptions of this paper.

1. Introduction

Stochastic dynamic matching problems are central to modern platforms like ride-sharing, supply-chain management, and medical exchange programs. In these environments, items (e.g., donors and patients) arrive randomly over time and must be matched based on compatibility. If an immediate match is unavailable, items are queued. The core challenge lies in balancing two competing objectives: maintaining system stability (preventing infinite queues) and maximizing long-term rewards from matches.

2. Problem Formulation and the Conservation Equation

The system is modeled as a compatibility graph $G = (V, E)$, where nodes represent item classes and edges represent possible matches. Items of class $i$ arrive at rate $\lambda_i$. When items of classes $i$ and $j$ are matched, they are removed from their respective queues.

The Diamond Graph model illustrating arrival rates (λ) and matching rates (μ) between nodes.

The fundamental relationship governing a stable system is the Conservation Equation: $$A\mu = \lambda$$ where $\lambda$ is the vector of arrival rates, $\mu$ is the vector of matching rates across edges, and $A$ is the incidence matrix of the graph. The set of all non-negative matching rates $\mu$ satisfying this equation forms a convex polytope. This geometric perspective allows us to analyze the limits of what any matching policy can achieve.

3. Theoretical Framework: Graph Structure and Stability

The paper establishes a deep link between the algebraic properties of the conservation equation and the topological structure of the compatibility graph.

  • The Odd Cycle Requirement: A critical finding is that a graph is only stabilizable if every connected component contains at least one odd cycle. In bipartite graphs, any imbalance in arrival rates between the two partitions leads to unavoidable queue growth.
  • Policy Irrelevance in Bijective Graphs: For certain "bijective" graphs, the matching rates $\mu$ are uniquely determined by $\lambda$. In such cases, any policy that maintains stability will result in the same long-term matching rates.
  • Suboptimality of Greedy Policies: Traditional "greedy" policies, which match items as soon as possible, are shown to be suboptimal. They tend to stay in the interior of the polytope, whereas maximizing rewards typically requires operating at the vertices (corners) of the polytope.

4. Proposed Matching Policies

To optimize rewards while maintaining stability, the authors propose and analyze several policies:

  • $\epsilon$-filtering: This policy prioritizes reward-maximizing edges but occasionally uses "suboptimal" edges to ensure queues remain bounded. It achieves a regret of $O(\epsilon)$ with a bounded delay of $O(1/\epsilon)$.
  • $k$-filtering: A threshold-based approach that behaves greedily for optimal matches but switches to a stability-focused mode if any queue length exceeds a threshold $k$.

5. Experimental Evaluation

The theoretical results were validated using a modular simulation engine across various graph topologies:

  • Diamond Graph: As shown in Figure 1, this four-node structure served as a primary test case for comparing policy performance.
  • Large-Scale Random Graphs: Tests on Erdős-Rényi graphs (up to 100 nodes and 1,000 edges) demonstrated the scalability of the linear programming approach for stability verification and rate optimization.
  • Performance: The $k$-filtering and adapted Primal-Dual policies significantly outperformed standard greedy approaches, achieving near-optimal rewards with manageable delays even in adversarial scenarios.

6. Conclusion and Future Work

This research provides a unified "polytope perspective" on stochastic matching, bridging graph theory and linear optimization. By identifying the structural requirements for stability and the limitations of greedy policies, the authors offer a roadmap for designing more efficient matching systems. Future research directions include extending the framework to non-linear reward functions and exploring the complexities of hypergraph-based multi-way matching.

Summary updated

Abstract

Stochastic dynamic matching problems have recently gained attention in the\nstochastic-modeling community due to their diverse applications, such as\nsupply-chain management and kidney exchange programs. In this paper, we study a\nmatching problem where items of different classes arrive according to\nindependent Poisson processes. Unmatched items are stored in a queue, and\ncompatibility between items is represented by a simple graph, where items can\nbe matched if their classes are connected.We analyze matching policies in terms\nof stability, delay, and long-term matching rate optimization. Our approach\nrelies on the conservation equation, which ensures a balance between arrivals\nand departures in any stable system. Our main contributions are as follows.We\nestablish a link between the existence of stable policies, the dimensionality\nof the solution set of the conservation equation, and the compatibility graph's\nstructure.We describe the convex polytope formed by non-negative solutions to\nthe conservation equation, and we design policies that can achieve or closely\napproximate the vertices of this polytope.Lastly, we discuss potential\nextensions of our results beyond the main assumptions of this paper.\n
BibTeX
@misc{comte2021online,
  author = {Céline Comte and Fabien Mathieu and Ana Bušić and Bušić, Ana},
  title = {{Online Stochastic Matching: A Polytope Perspective}},
  year = {2021},
  eprint = {2112.14457},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.14457},
}
Figure