Abstract

The theory of matching has a long history in economics, mathematics, and graph theory, with applications in many other fields. However, most of the research considers the static setting. In recent years, with the increased popularity of online advertising, various online matching models have been proposed that consider random arrivals of one population, while the other is static.
In this talk we consider extensions to fully dynamic bipartite matching models, in which both populations are given by a stochastic process. This line of work combines classical matching theory with queuing and inventory theory. The main departure from traditional queueing networks is that there is no notion of servers. Instead of ``service'', activities correspond to instantaneous matching of a particular unit of supply with a unit of demand. One of the most compelling applications is kidney paired donation by United Network for Organ Sharing.
We will present recent results for the FCFS policy in which each is matched to the earliest compatible unmatched item in the system. Then we will consider an infinite-horizon average-cost optimal control problem. A relaxation of the stochastic control problem will be discussed, which is found to be a special case of an inventory model, as treated in the classical theory of Clark and Scarf. The optimal policy for the relaxation admits a closed-form expression. Based on the policy for this relaxation, we propose a new matching policy. For a parameterized family of models in which the network load approaches capacity, this policy is shown to be approximately optimal, with bounded regret, even though the average cost grows without bound.

Video Recording