Online Stochastic Matching: A Polytope Perspective

C{é}line Comte, Fabien Mathieu, Sushil Mahavir Varma, Ana Bušić

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. When a vertex can only be approximated, we quantify the resulting trade-off between regret and delay: our policies achieve arbitrarily small regret at the cost of increasing delay, and we prove that this trade-off is unavoidable. Lastly, we discuss potential extensions of our results beyond the main assumptions of this paper.
BibTeX
@misc{comte2021online,
  author = {C\{é\}line Comte and Fabien Mathieu and Sushil Mahavir Varma and Ana Bušić},
  title = {{Online Stochastic Matching: A Polytope Perspective}},
  year = {2021},
  eprint = {2112.14457},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.14457},
}

Loading related content...

Figure