John Chiarelli, Rutgers University

Abstract

The stable marriage problem is a classic one in the library of discrete math. The best-known results on the problem stem from the work of David Gale and Lloyd Shapley, who in their 1962 paper not only showed that a stable matching exists for every possible instance of the problem, but also gave an algorithm for finding such a matching. However, in applications of finding stable matchings between agents, these agents may choose to be dishonest about their preferences. In this talk, I will discuss the circumstances under which agents in the Gale-Shapley algorithm can improve their outcome by lying about their order of preference