Stability of the stochastic matching model

E-ISSN： 1475-6072|53|4|1064-1077

ISSN： 0021-9002

Source： Journal of Applied Probability, Vol.53, Iss.4, 2016-12, pp. : 1064-1077

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

We introduce and study a new model that we call the matching model. Items arrive one by one in a buffer and depart from it as soon as possible but by pairs. The items of a departing pair are said to be matched. There is a finite set of classes 𝒱 for the items, and the allowed matchings depend on the classes, according to a matching graph on 𝒱. Upon arrival, an item may find several possible matches in the buffer. This indeterminacy is resolved by a matching policy. When the sequence of classes of the arriving items is independent and identically distributed, the sequence of buffer-content is a Markov chain, whose stability is investigated. In particular, we prove that the model may be stable if and only if the matching graph is nonbipartite.