Speaker
Description
Stochastic dynamic matching has numerous applications, ranging from supply-chain management to kidney exchange programs. We consider a generic model where items of different classes arrive randomly. Two items can be matched if their classes are compatible. Unmatched items are queued.
We study the stability of such systems and the matching rates between classes. Our main results, which rely on the conservation equation between arrivals and departures, are:
- We give simple relationships between departure and arrival rates, the shape of the compatibility graph, and the existence of a stable matching policy.
- We describe the polytope of non-negative solutions of the conservation in the degenerated and non-degenerated cases. Any stable policy necessarily yields one of these solutions.
- Reciprocally, we show that any part of the polytope can be reached (possibly asymptotically) by using non-greedy policies. The same result does not hold for greedy policies.
This is a joint work with Céline Comte, Sushil Varma, and Ana Bušić.
