Abstract: The FCFS stochastic matching model, where each server in an infinite sequence is matched to the first customer from a second infinite sequence that is eligible to receive service from the server in question, developed from queueing problems addressed by Kaplan (1984) in the context of public housing assignments. The main goal of this model is to determine the matching rates between eligible customer and server types, that is, what fraction of all matches occur between type-i customers and type-j servers. This model was solved in a beautiful paper by Adan and Weiss (2012), but the resulting equation for the matching rates is quite complicated, involving the sum of terms over all permutations of the server types (Adan and Weiss suggest that their calculation might be of complexity #P). Here we develop physical flow approximations for the matching rates that in some cases reduce to exact results, and via simulation are shown to be highly accurate. As our approximations only require the solution of a system of linear equations along with the identification of a small number of terms, they provide a tractable alternative to the exact solution.
Note: this is joint work with Mohammad Fazel Zarandi, Yale School of Management