The theory of matching has a long history in economics, mathematics, and graph theory, with applications in many 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. We consider a discrete-time bipartite matching model with random arrivals of units of supply and demand that can wait in queues located at the nodes in the network. A control policy determines which are matched at each time. The focus is on the infi nite-horizon average-cost optimal control problem. A new class of policies is introduced: the h-MaxWeight with threshold. The policy is the solution to a linear program that minimizes the drift of the function h, subject to non-idling constraints. Performance analysis is based on a one-dimensional relaxation of the stochastic control problem, which is found to be a special case of an inventory model, as treated in the classical theory of Clark and Scarf. Consequently, the optimal policy for the relaxation admits a closed-form expression based on a threshold rule. These observations inform the choice of function h, taken to be a perturbation of the cost function, and the choice of threshold. 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.
Joint work with Sean Meyn (University of Florida).
Back to the workshop page