On the sub-additivity of stochastic matching (Q6623437)

The authors consider a stochastic matching model with a general compatibility graph and prove that most common matching policies (including ``first come, first matched'', priorities and random) satisfy a particular sub-additive property. This property is exploited to show the coupling-from-the-past to the steady state, using a backwards scheme.\N\NThe results are used 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.