Dynamic Matching Market Design

Abstract

We introduce a simple benchmark model of dynamic matching in networked markets, where agents arrive and depart stochastically and the network of acceptable transactions among agents forms a random graph. We analyze our model from three perspectives: waiting, optimization, and information. The main insight of our analysis is that waiting to thicken the market can be substantially more important than increasing the speed of transactions, and this is quite robust to the presence of waiting costs. From an optimization perspective, naive local algorithms, that choose the right time to match agents but do not exploit global network structure, can perform very close to optimal algorithms. From an information perspective, algorithms that employ even partial information on agents' departure times perform substantially better than those that lack such information. To elicit agents' departure times, we design an incentive-compatible continuous-time dynamic mechanism without transfers.

References in corpus (1)

• Online Stochastic Matching: Beating 1-1/e

Cited by in corpus (8)

• Position-Indexed Formulations for Kidney Exchange
• Prophet Inequality with Correlated Arrival Probabilities, with Application to Two Sided Matchings
• The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm
• Two-sided Facility Location
• On Incentive Compatibility in Dynamic Mechanism Design With Exit Option in a Markovian Environment
• Matching while Learning
• Fair Matching in Dynamic Kidney Exchange
• Bandit based centralized matching in two-sided markets for peer to peer lending