Abstract
The stochastic dynamic matching problem has recently drawn attention in the stochastic-modeling community due to its numerous applications, ranging from supply-chain management to kidney exchange programs. In this paper, we consider a matching problem in which items of different classes arrive according to independent Poisson processes. Unmatched items are stored in a queue, and compatibility constraints are described by a simple graph on the classes, so that two items can be matched if their classes are neighbors in the graph. We analyze the efficiency of matching policies, not only in terms of system stability, but also in terms of matching rates between different classes. Our results rely on the observation that, under any stable policy, the matching rates satisfy a conservation equation that equates the arrival and departure rates of each item class. Our main contributions are threefold. We first introduce a mapping between the dimension of the solution set of this conservation equation, the structure of the compatibility graph, and the existence of a stable policy. In particular, this allows us to derive a necessary and sufficient stability condition that is verifiable in polynomial time. Secondly, we describe the convex polytope of non-negative solutions of the conservation equation. When this polytope is reduced to a single point, we give a closed-form expression of the solution; in general, we characterize the vertices of this polytope using again the graph structure. Lastly, we show that greedy policies cannot, in general, achieve every point in the polytope. In contrast, non-greedy policies can reach any point of the interior of this polytope, and we give a condition for these policies to also reach the boundary of the polytope.
Introduction
Stochastic dynamic matching is a critical framework for modeling systems such as kidney exchange programs, supply-chain management, and online marketplaces like Uber or Airbnb. In these systems, items (or people) arrive randomly and wait in queues to be matched with compatible partners. The primary challenge is balancing two often-conflicting goals: maintaining system stability (ensuring queues do not grow indefinitely) and maximizing rewards (optimizing the quality of matches).
Traditionally, queueing theorists focused on stability while optimization experts focused on rewards. This paper provides a unified "polytope perspective," using linear algebra to define exactly what matching rates are possible and how to achieve them without compromising system stability.
Theoretical Framework: The Polytope Perspective
The authors base their approach on a fundamental conservation equation: $A\mu = \lambda$. Here, $\lambda$ represents the vector of arrival rates for different item classes, $\mu$ is the vector of matching rates across specific edges in the compatibility graph, and $A$ is the incidence matrix of the graph. In any stable system, the rate of items entering must equal the rate of items being matched.
By analyzing the linear map $\mu \to A\mu$, the authors classify graphs as surjective, injective, or bijective. They characterize the set of all non-negative matching rates as a convex polytope. Key insights from this geometric approach include:
- The Geometry of Stability: A compatibility graph is only "stabilizable" if it is surjective. In graph-theoretic terms, every connected component must contain at least one odd cycle; bipartite graphs are inherently unstable as they behave like biased random walks that eventually drift to infinity.
- The Vertex-Injective Link: The vertices (corners) of the matching polytope correspond to subgraphs that are injective. Optimizing rewards effectively requires "pruning" the compatibility graph down to an injective subgraph.
- The Fundamental Trade-off: If the optimal vertex is "bijective," maximum rewards and low delay can coexist. However, if the vertex is "injective-only," a trade-off emerges: to get $O(\epsilon)$ close to the perfect reward, the average delay must grow by $O(1/\epsilon)$.
Policy Design and Results
While greedy policies (matching items as soon as possible) are effective for stability, they are often trapped in the interior of the polytope and cannot reach the reward-optimal boundaries. To address this, the authors introduce two new policy classes:
- $\epsilon$-filtering: A probabilistic policy that prioritizes a reward-optimal subgraph but occasionally allows suboptimal matches to prevent queue buildup.
- $k$-filtering: A state-dependent policy that only allows reward-optimal matches unless a queue exceeds a threshold $k$, at which point it prioritizes stability.
Using a custom Python simulation engine, the authors evaluated these policies on various structures, including toy graphs (Triangle, Diamond, "Kayak Paddle") and large-scale synthetic Erdös-Rényi graphs with 100 nodes. The results demonstrated that these reward-aware policies significantly outperform standard stability-focused policies like "Match-the-Longest" when rewards are adversarial.
Conclusion and Future Work
The framework successfully identifies optimal vertices and maintains stability in complex graphs where manual analysis is impossible. Future work remains to prove the conjectured convergence of $k$-filtering, develop practical policies for non-linear rewards, and extend the polytope perspective to hypergraphs where matches involve more than two items.
Summary updated