Speaker
Description
We consider the following online stochastic matching problem: items from different classes arrive according to independent Poisson processes; matching compatibilities between items are described by a simple graph over the classes, so that two items can be matched if and only if their classes are neighbors in the graph; this graph is assumed to be connected and non-bipartite; lastly, each incoming item is matched immediately with the oldest compatible unmatched item, if any. The evolution of the sequence of unmatched item classes, ordered by arrival times, defines an irreducible Markov chain. Previous work has derived (i) a necessary and sufficient condition for this Markov chain to be positive recurrent, which we assume is satisfied, and (ii) a closed-form expression for its stationary distribution. In this presentation, we first provide more direct method to derive the stationary distribution, based on quasi-reversibility, a notion introduced by Kelly (1979). We then derive new closed-form expressions for several performance metrics, such as the waiting probability and the mean waiting time, which can be efficiently implemented using dynamic programming. Both these formulas and the numerical results that they allow us to derive are used to better understand the impact of parameters on performance. In particular, we characterize performance in a so-called heavy-traffic regime, in which the number of items of a subset of the classes goes to infinity while items of other classes become scarce.
