Stability of the bipartite matching model (Q2837751)

The bipartite matching model is specified by: (i) the finite set \(C\) of customer classes and the finite set \(S\) of server classes; (ii) the probability law \(\mu \) on \(C \times S\) for the arrivals in pairs; (iii) the bipartite graph \((C,S,E \subset C \times S)\) giving the possible matching between customers and servers (the possible departures in pairs); (iv) the matching policy to decide how to match when several choices are possible. The service durations are null. The paper deals with so-called admissible policies which depend only on the current state of the system. Customers/servers that cannot be matched are stored in a buffer. Under these assumptions, the buffer content evolves as a discrete-time Markov chain. The paper considers the stability issue for various admissible matching policies: match the longest, match the shortest, match the oldest, random (match uniformly), and priority.