On the sub-additivity of stochastic matching

We consider a stochastic matching model with a general compatibility graph, as introduced in Mairesse and Moyal (J Appl Probab 53(4):1064–1077, 2016). We prove that most common matching policies (including fcfm, priorities and random) satisfy a particular sub-additive property, which we exploit to show in many cases, the coupling-from-the-past to the steady state, using a backwards scheme à la Loynes. We then use these results to explicitly construct perfect bi-infinite matchings, and to build a perfect simulation algorithm in the case where the buffer of the system is finite.