×

Stable matchings in high dimensions via the Poisson-weighted infinite tree. (English. French summary) Zbl 1434.60056

Summary: We consider the stable matching of two independent Poisson processes in \(\mathbb{R}^d\) under an asymmetric color restriction. Blue points can only match to red points, while red points can match to points of either color. It is unknown whether there exists a choice of intensities of the red and blue processes under which all points are matched. We prove that for any fixed intensities, there are unmatched blue points in sufficiently high dimension. Indeed, if the ratio of red to blue intensities is \(\rho\) then the intensity of unmatched blue points converges to \(e^{-\rho }/(1+\rho )\) as \(d\to \infty \). We also establish analogous results for certain multi-color variants. Our proof uses stable matching on the Poisson-weighted infinite tree (PWIT), which can be analyzed via differential equations. The PWIT has been used in many settings as a scaling limit for models involving complete graphs with independent edge weights, but as far as we are aware, this is the first presentation of a rigorous application to high-dimensional Euclidean space. Finally, we analyze the asymmetric matching problem under a hierarchical metric, and show that there are unmatched points for all intensities.

MSC:

60D05 Geometric probability and stochastic geometry
60G55 Point processes (e.g., Poisson, Cox, Hawkes processes)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

References:

[1] L. Addario-Berry, S. Griffiths and R. J. Kang. Invasion percolation on the Poisson-weighted infinite tree. Ann. Appl. Probab. 22 (3) (2012) 931-970. · Zbl 1262.60091 · doi:10.1214/11-AAP761
[2] D. Aldous. Asymptotics in the random assignment problem. Probab. Theory Related Fields 93 (4) (1992) 507-534. · Zbl 0767.60006 · doi:10.1007/BF01192719
[3] D. Aldous and J. M. Steele. The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures 1-72. Encyclopaedia Math. Sci. 110. Springer, Berlin, 2004. · Zbl 1037.60008
[4] G. Amir, O. Angel and A. E. Holroyd. Multicolor Poisson matching, 2016. Available at arXiv:1605.06485.
[5] C. Bordenave, P. Caputo and D. Chafaï. Spectrum of large random reversible Markov chains: Heavy-tailed weights on the complete graph. Ann. Probab. 39 (4) (2011) 1544-1590. · Zbl 1245.60008 · doi:10.1214/10-AOP587
[6] C. Bordenave, P. Caputo and D. Chafaï. Spectrum of non-Hermitian heavy tailed random matrices. Comm. Math. Phys. 307 (2) (2011) 513-560. · Zbl 1235.60008 · doi:10.1007/s00220-011-1331-9
[7] C. Bordenave and D. Chafaï. Around the circular law. Probab. Surv. 9 (2012) 1-89. · Zbl 1243.15022
[8] D. J. Daley and G. Last. Descending chains, the lilypond model, and mutual-nearest-neighbour matching. Adv. in Appl. Probab. 37 (3) (2005) 604-628. · Zbl 1078.60038 · doi:10.1239/aap/1127483738
[9] M. Deijfen, A. E. Holroyd and J. B. Martin. Friendly frogs, stable marriage, and the magic of invariance. Amer. Math. Monthly 124 (5) (2017) 387-402. · Zbl 1394.05077 · doi:10.4169/amer.math.monthly.124.5.387
[10] D. Gale and L. S. Shapley. College admissions and the stability of marriage. Amer. Math. Monthly 69 (1) (1962) 9-15. · Zbl 0109.24403 · doi:10.1080/00029890.1962.11989827
[11] A. E. Holroyd, R. Pemantle, Y. Peres and O. Schramm. Poisson matching. Ann. Inst. Henri Poincaré Probab. Stat. 45 (1) (2009) 266-287. · Zbl 1175.60012 · doi:10.1214/08-AIHP170
[12] O. Kallenberg. Foundations of Modern Probability, 2nd edition. Probability and Its Applications (New York). Springer-Verlag, New York, 2002. · Zbl 0996.60001
[13] J. Salez and D. Shah. Belief propagation: An asymptotically optimal algorithm for the random assignment problem. Math. Oper. Res. 34 (2) (2009) 468-480. · Zbl 1230.68183 · doi:10.1287/moor.1090.0380
[14] J. M. Steele. Minimal spanning trees for graphs with random edge lengths. In Mathematics and Computer Science, II (Versailles, 2002), Trends Math 223-245. Birkhäuser, Basel, 2002. · Zbl 1032.60007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.