Dynamic Matching Models
summary
First come first matched on a general compatibility graph has maximal stability whenever the graph is non‑bipartite and the stationary law factorizes into a product form stationary distribution; the proof constructs enlarged word‑based chains with a ghost process / reversibility proof to get tractability. Priority and shortest‑job policies fail in general, while randomized and asymptotically optimal mixed policy variants (max‑weight plus thresholds) reach maximal stability and, in heavy traffic, achieve bounded regret.
AI-written summary · about
chapters (8)
- 0:00Introduction to matching
- 2:55Motivation and modeling
- 6:18Performance evaluation
- 10:12Stability conditions
- 15:25Proof methodologies
- 19:05Bipartite and open variants
- 22:43Alternative policy analysis
- 26:01Optimization and outlook
related talks
50mDiversity in Matching Markets
44mComputational Complexity of Matching in Ride Sharing
44mClearing Matching Markets Efficiently: Informative signals and Match Recommendations
44mOnline Advertisements and Online Algorithms
46mJob Matching under Constraints
52mOptimal Growth in Two-Sided Markets
36mThe Intractability of Hylland-Zeckhauser and its Aftermath
01h 01mScarf's Lemma and Applications I