Neighborhood preferences in random matching problems

We consider a class of random matching problems where the distance between two points has a probability law which, for a small distance l, goes like l^r. In the framework of the cavity method, in the limit of an infinite number of points, we derive equations for p_k. the probability for some given point to be matched to its kth nearest neighbor in the optimal configuration. These equations are solved in two limiting cases: r = O - where we recover p_k = 1/2^k, as numerically conjectured by Houdayer et al. and recently rigorously proved by Aldous - and r → +∞. For 0 < r < +∞, we are not able to solve the equations analytically, but we compute the leading behavior of p_k for large k.