  We consider the bipartite matching model of customers and servers introduced
by Caldentey, Kaplan, and Weiss (Adv. Appl. Probab., 2009). Customers and
servers play symmetrical roles. There is a finite set C resp. S, of customer,
resp. server, classes. Time is discrete and at each time step, one customer and
one server arrive in the system according to a joint probability measure on
CxS, independently of the past. Also, at each time step, pairs of matched
customer and server, if they exist, depart from the system. Authorized
matchings are given by a fixed bipartite graph. A matching policy is chosen,
which decides how to match when there are several possibilities.
Customers/servers that cannot be matched are stored in a buffer. The evolution
of the model can be described by a discrete time Markov chain. We study its
stability under various admissible matching policies including: ML (Match the
Longest), MS (Match the Shortest), FIFO (match the oldest), priorities. There
exist natural necessary conditions for stability (independent of the matching
policy) defining the maximal possible stability region. For some bipartite
graphs, we prove that the stability region is indeed maximal for any admissible
matching policy. For the ML policy, we prove that the stability region is
maximal for any bipartite graph. For the MS and priority policies, we exhibit a
bipartite graph with a non-maximal stability region.
