Stable Marriages in Metric Spaces
Talkat Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016) · 2016-09-19..09-23
summary
One-dimensional Hamming preferences produce many ties: K=1 ties persist and even K ≈ log n leaves exponentially many stable matchings; recovering uniqueness under plain Hamming requires astronomically large K, while a weighted-coordinate metric yields a strict global ordering already at 4 log n questions and guarantees each person gets their top choice with ≥50% probability. Continuous matching on R maps to growing-ray and LCFS queue analyses, giving mean-distance bounds on the order of 1/(mu−lambda) and a one-sided top-choice probability exactly mu/(mu+lambda), with two-sided matching strictly better.
AI-written summary · about
chapters (12)
- 0:00Start
- 1:03Motivation
- 2:04The Model
- 8:24Background: Stable Matchings
- 8:52Background: Random Ranking Lists
- 16:13Results, Hamming Distance
- 16:26Results, Discrete Uniform Metric
- 18:231-Dimensional Point Process Stable Matching
- 19:35Matching Distance
- 20:24Unbalanced Case: Key Observation
- 22:472-sided Stable Matching: Bounds
- 27:47Conclusions