Stable matchings in metric spaces
Abstract/Contents
- Abstract
- Suppose each of $n$ men and $n$ women is located at a point in a metric space. A woman ranks the men in order of their distance to her from closest to farthest, breaking ties at random. The men rank the women similarly. An interesting problem is to use these ranking lists and find a stable matching in the sense of Gale and Shapley. This problem formulation naturally models preferences in several real world applications; for example, dating sites, room renting/letting, ride hailing and labor markets. Two key questions that arise in this setting are: (a) When is the stable matching unique without resorting to tie breaks? (b) If $X$ is the distance between a randomly chosen stable pair, what is the distribution of $X$ and what is $E(X)$? These questions address conditions under which it is possible to find a unique (stable) partner, and the quality of the stable matching in terms of the rank or the proximity of the partner. We study dating sites and ride hailing as prototypical examples of stable matchings in discrete and continuous metric spaces, respectively. In the dating site model, each man/woman is assigned to a point on the $k$-dimensional hypercube based on their answers to a set of $k$ questions with binary answers ({\it e.g.}\ , like/dislike). We consider two different metrics on the hypercube: Hamming and Weighted Hamming (in which the answers to some questions carry more weight). Under both metrics, there are exponentially many stable matchings when $k = \lfloor\log n\rfloor$. There is a unique stable matching, with high probability, under the Hamming distance when $k = \Omega(n^6)$, and under the Weighted Hamming distance when $k > (2+\epsilon) \log n$ for some $\epsilon> 0$. In the ride hailing model, passengers and cabs are modeled as points on the line and matched based on Euclidean distance (a proxy for pickup time). Assuming the locations of the passengers and cabs are independent Poisson processes of different intensities, we derive bounds on the distribution of $X$ in terms of busy periods at a last-come-first-served preemptive-resume (LCFS-PR) queue. We also study the college admission problem where the goal is to find a stable matching between students and colleges. In our analysis, we consider a utility-based model for the preference lists of colleges and students. We derive sufficient conditions on the utility functions to have a unique stable matching. We also model the interview process in the college admission problem, and show that if conducting interviews are costly, in certain circumstances we may see over-qualification of applicants.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | ©2018 |
| Publication date | 2018; 2018 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Abadi, Hossein Karkeh |
|---|---|
| Degree supervisor | Prabhakar, Balaji, 1967- |
| Thesis advisor | Prabhakar, Balaji, 1967- |
| Thesis advisor | Akbarpour, Mohammad |
| Thesis advisor | Tse, David |
| Degree committee member | Akbarpour, Mohammad |
| Degree committee member | Tse, David |
| Associated with | Stanford University, Department of Electrical Engineering. |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Hossein Karkeh Abadi. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2018. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2018 by Hossein Karkeh Abadi
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...