Many situations in society involve matchings. Workers are matched to jobs, students to schools, conference papers to reviewers, patients to organ donors, etc. Those involved have preferences which are often expressed as rankings of their potential partners. An important goal of a centralized match-maker is to produce a "good" matching that takes into account the preferences of all the participants. Perhaps the most important example of a matchings-with-preferences problem is the stable marriage problem. In some contexts, however, other kinds of matchings are more meaningful.
This research studies computational and structural issues that arise from matchings-with-preferences problems. The first part investigates various ways of choosing a fair matching -- an issue that comes up repeatedly as organizers of centralized matching schemes need to ensure that none of the participants have an advantage. Three criteria for fairness are considered. Let M consist of all valid matchings of an instance. A matching is fair if it is (i) a median element of M whose elements are ordered appropriately, if it is (ii) a winner of an election where participants vote which matching in M they prefer, or if it is (iii) chosen uniformly at random from M. In each case, the objective is to design provably good algorithms for finding or approximating a fair matching. In practice, participants' preferences are often allowed to contain ties and be incomplete. As a result, surprising complexities arise. For example, two stable matchings from the same instance do not necessarily have the same size. The second part of this research seeks to develop efficient algorithms for finding "ideal" stable matchings in these situations, and to analyze existing algorithms to determine the quality of the stable matchings they produce. In addition to impacting the way current centralized matching algorithms are designed, this research aims to make connections between the area of matchings-with-preferences and the fields of distributive lattices, voting theory and random sampling by viewing the problems in a broader context.
