A stochastic matching between graph theory and linear algebra

Stochastic dynamic matching has numerous applications, ranging from supply-chain management to kidney exchange programs. In a matching problem, different classes arrive according to independent Poisson processes. Unmatched items are stored in a queue, and two items can be matched if their classes are neighbors in a (simple) compatibility graph. We analyze the efficiency of matching policies in terms of system stability and of matching rates between different classes. Our results, which rely on the observation of the conservation equation between departures and arrivals, are threefold. We first relate the way the conservation equation maps arrival and departure vectors, the structure of the compatibility graph, and the existence of a stable policy. 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 at least reach any point of the interior of this polytope, and can also reach its boundary if a specific condition on its vertices is checked.

 

This is a joint work with Céline Comte and Ana Bušic.