Tiered Random Matching Markets: Rank is Proportional to Popularity
summary
Man-proposing deferred acceptance runs in Θ(n log n) proposals and yields average ranks that scale inversely with public scores: expected rank for an agent is Θ((log n)/score) so rank ~ 1/score. Proof uses coupon-collector bounds for total proposals, the deferred-decisions trick to treat acceptances as geometric trials, and concentration lemmas (e.g. no agent makes > log^2 n proposals). Surprisingly, match types are macroscopicly uniform: fraction between tier j men and tier i women ≈ delta_j · epsilon_i.
AI-written summary · about
chapters (11)
- 0:00Start
- 0:20Stable Marriage Problem
- 2:46Model for Tiered Matching Markets
- 3:27Sampling Probability
- 4:01Core Results
- 6:00Distribution of Batch Type
- 12:31Principle of Deferred Decisions
- 17:29Distribution of Match Time
- 18:16Uniform Match Type Distribution
- 19:33Extensions and Future Work
- 19:59Imbalanced Markets