Stabilizing policies for probabilistic matching systems

In this work, we introduce a novel queueing model with two classes of users, where users wait in the system to match with a candidate from the other class, instead of accessing a resource. This new model is useful for analyzing the traffic in web portals that match people who provide a service with people who demand the service, for example, employment portals, matrimonial and dating sites, and rental portals. We provide a Markov chain model for these systems and derive the probability distribution of the number of matches up to some finite time given the number of arrivals. We prove that if no control mechanism is employed these systems are unstable for any set of parameters, and suggest four different classes of control policies to assure stability. Contrary to the intuition that the rejection rate should decrease as the users get more likely to match, we show that for certain control policies the rejection rate is insensitive to the matching probability. Even more surprisingly, we show that for reasonable policies the rejection rate may be an increasing function of the matching probability. We also prove insensitivity results related to the average queue lengths and waiting times.