| Matching markets are ubiquitous, including college admissions, school choice, reviewer paper matching, and various labour market matchings. Many of these matching markets run centralized matching schemes, using algorithms to determine the resulting match. An important property for the matches provided by the clearing house is stability. The notion of stability, where no one in the market has both the incentive and the ability to change their partner, has been empirically shown to be a very valuable property in real-world markets.;However, the mechanisms used in practice make assumptions that do not hold in practice. In this thesis, we investigate problems in this gap between theory and practice. We focus on assumptions regarding participants' preferences: the standard algorithms for this problem assume participants are able and willing to provide a full preference list, sometimes over tens of thousands of alternatives. The standard algorithms also assume participants' preferences can be expressed by a simple ordered list over individual alternatives: a false assumption when a pair of participants, a couple, are looking for a job in the same city.;We use a variety of techniques to address these issues, ranging from heuristic preference elicitation schemes, to equilibria analysis of participants' behaviour in the market as-is, to using SAT solvers to develop new matching mechanisms with couples. Our SAT encoding exhibits improved performance, and allows for more guarantees regarding participants' strategic behavior under certain circumstances. We find, under some settings, a common interviewing strategy is not an equilibrium. This provides further evidence for the need of elicitation schemes; ours find stable matches with much less information than traditional methods. |
