High Satisfaction in Thin Dynamic Matching Markets

Dynamic matching markets are an ubiquitous object of study with applications in health, labor, or dating. There exists a rich literature on the formal modeling of such markets. Typically, these models consist of an arrival procedure, governing when and which agents enter the market, and a sojourn period of agents during which they may leave the market matched with another present agent, or after which they leave the market unmatched. One important focus lies on the design of mechanisms for the matching process aiming at maximizing the quality of the produced matchings or at minimizing waiting costs. We study a dynamic matching procedure where homogeneous agents arrive at random according to a Poisson process and form edges at random yielding a sparse market. Agents leave according to a certain departure distribution and may leave early by forming a pair with a compatible agent. The objective is to maximize the number of matched agents. Our main result is to show that a mild guarantee on the maximum sojourn time of agents suffices to get almost optimal performance of instantaneous matching, despite operating in a thin market. This has the additional advantages of avoiding the risk of market congestion and guaranteeing short waiting times. We develop new techniques for proving our results going beyond commonly adopted methods for Markov processes.