When an Algorithm Cannot Help You Find a Wife: Modeling Two-Sided Matching Markets Using Stochastic Matching
Wouter P.J. Kroese

Abstract:
In Stable Marriage Problems two groups of agents have preferences over being paired with one another. The Deferred Acceptance Algorithm is a great and elegant tool for finding stable matchings for these Stable Marriage Problems, where no blocking pair, consisting of two agents that would rather be matched with one another exists. In many real-world two-sided matching markets, like people in search of a romantic partner, it is however not possible to execute a procedure like the Deferred Acceptance Algorithm. We constructed a stochastic matching model in which all agents randomly meet another agent from the other side of the market in consecutive daterounds, with whom they pair up if they form a blocking pair. We first show that our model will converge towards stable matchings. In our model agents have randomly assigned preferences over all agents of the other side of the market. We show that our model obtains stable matchings, which on average yield both higher and more egalitarian payoffs than in the Deferred Acceptance Algorithm or in a randomly selected stable matching. Furthermore we extend our model such that it can be used for simulating and improving real-world two-sided markets.