Superiority of Instantaneous Decisions in Thin Dynamic Matching Markets

Johannes B\"aumler, Martin Bullinger, Stefan Kober and Donghao Zhu

Papers from arXiv.org

Abstract: 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.

Date: 2022-06, Revised 2025-11
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://arxiv.org/pdf/2206.10287 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2206.10287

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().