2022/06/21 by Johannes Bäumler, Bäumler, Johannes, Martin Bullinger +5
Decision Sciences · Engineering · Social Sciences · #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Economics and business #Theoretical Economics (econ.TH) #Transportation Planning and Optimization #Transportation and Mobility Innovations
paper · pdf · doi:10.48550/arxiv.2206.10287
openalex publication_date 2022/06/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study a dynamic matching setting where homogeneous agents arrive at random according to a Poisson process and randomly form edges yielding a sparse market. Agents stay in the market according to a certain sojourn time and wait to be matched with a compatible agent by a matching algorithm. When their maximum sojourn time is reached, they perish unmatched. The primary objective is to maximize the number of matched agents. Our main result is to show that a uniformly guaranteed sojourn time suffices to get almost optimal performance of instantaneous matching. Interestingly, this matching policy essentially keeps as few agents in the market as possible. Hence, in contrast to the common paradigm that market thickness is the crucial property for obtaining strong matching performance, we show that the agents' sojourn behavior can be an equally powerful factor. In addition, instantaneous matching is close to optimal with respect to minimizing waiting time. We develop new techniques for proving our results going beyond commonly adopted methods for Markov processes.