Constructing Stable Matchings Using Preference Elicitation Through Prices and Budgets

Abstract

Eliciting complete preference information is difficult in many two-sided matching markets. First, there may be a very large number of options to rank. In addition, preference elicitation may require interviews that are time and effort costly, and furthermore, costs for elicitation may be unbalanced on the two sides. For example, schools may have easy criteria by which to rank students, but students may need to expend considerable time and energy to rank schools. The problem addressed in this thesis is to achieve a stable matching while minimizing the amount of information required from agents. I focus on the one-to-one two-sided matching problem, or the stable marriage problem, and introduce a new mechanism for achieving a stable matching using virtual prices and virtual budgets. I experimentally analyze the degree of information elicited and the time to convergence, comparing the performance of this new mechanism with two existing stable marriage matching algorithms, Deferred Acceptance and Minimax Regret. The new mechanism requires less information from one side of the market than these other algorithms, which may make it well suited to several real-life market places.