Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-17T06:09:26.678Z Has data issue: false hasContentIssue false

Stability of the stochastic matching model

Published online by Cambridge University Press:  09 December 2016

Jean Mairesse*
Affiliation:
CNRS and UPMC
Pascal Moyal*
Affiliation:
Université de Technologie de Compiègne and Northwestern University
*
* Postal address: Sorbonne Universités, UPMC Univ Paris 06, CNRS, LIP6, 4 place Jussieu, 75252 Paris Cedex 05, France.
** Postal address: LMAC, Université de Technologie de Compiègne, 60203 Compiègne Cedex, France. Email address: pascal.moyal@utc.fr
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 2016