A product form and a sub-additive theorem for the general stochastic matching model

Pascal Moyal (1) , Ana Bušić (2, 3) , Jean Mairesse (4)

1 IRD [France-Nord] - Institut de Recherche pour le Développement
2 DYOGENE - Dynamics of Geometric Networks
3 LINCS - Laboratory of Information, Network and Communication Sciences
4 APR - Algorithmes, Programmes et Résolution

We consider a stochastic matching model with a general matching graph, as introduced in \cite{MaiMoy16}. We show that the natural necessary condition of stability of the system exhibited therein is also sufficient whenever the matching policy is First Come, First Matched (FCFM). For doing so, we exhibit a stationary distribution under a remarkable product form, by using an original dynamic reversibility inspired by that of \cite{ABMW17} for the bipartite matching model. Second, we observe that most common matching policies (including FCFM, priorities and random) satisfy a remarkable sub-additive property, which we exploit to derive in many cases, a coupling result to the steady state, using a constructive backwards scheme {\em \`a la} Loynes. We then use these results to explicitly construct perfect bi-infinite matchings.

Domaines: Probabilités [math.PR]

Pascal Moyal, Ana Bušić, Jean Mairesse. A product form and a sub-additive theorem for the general stochastic matching model. 2017. ⟨hal-01672482⟩