Reproduce “Dynamic Bipartite Matching Market with Arrivals and Departures” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Naonori Kakimura, Donghao Zhu
This research analyzes local matching mechanisms in dynamic bipartite markets with stochastic arrivals and departures, quantifying the performance of "Greedy" and "Patient" strategies. It reveals that the significant benefits of waiting to thicken the market, observed in two-sided markets, largely disappear in one-sided market configurations.
Key insights
- The "value of waiting" to thicken the market is highly contingent; its substantial benefit (exponentially reduced loss) is realized primarily in two-sided markets where both types of agents actively seek partners.
- In one-sided markets, where agents on one side are passive, delaying matching decisions by the active side does not provide a performance advantage over immediate matching, showing similar loss orders for both strategies.
- Market density (λ*p) and the balance between agent arrival rates (d_a vs. d_b) are critical parameters determining the unavoidable loss and the efficacy of different timing strategies.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.