Abstract
Suppose each of N men and N women picks a point in a metric space. A woman ranks the men in increasing order of their distance to her, closest first. Men rank similarly. Based on these ranking lists, the goal is to find a stable matching in the sense of Gale and Shapley. This problem naturally models several applications, we mention two: (i) Dating sites: each man/woman answers a set of questions with, say, binary (e.g., like/dislike) answers. Ranking lists are based on the Hamming distance between the binary vectors of answers, ties are broken at random. (ii) Ride hailing: Passengers and cabs are matched based on Euclidean distance (or, the time to pick up).
We analyze this model in discrete and continuous metric spaces. In the discrete case, our results utilize and contrast with those of Ashlagi et al on the uniqueness of stable matchings. In the continuous case, we consider “unbalanced Poisson matchings in R” and make contact with the work of Holroyd et al.
Joint work with Hossein Karkeh Abadi.