Georgia Institute of Technology College of Sciences

We study stable marriage where individuals strategically submit private preference information to a publicly known stable marriage algorithm. We prove that no stable marriage algorithm ensures actual stability at every Nash equilibrium when individuals are strategic. More specifically, we show that any rational marriage, stable or otherwise, can be obtained at a Nash equilibrium. Thus the set of Nash equilibria provides no predictive value nor guidance for mechanism design. We propose the following new minimal dishonesty equilibrium refinement, supported by experimental economics results: an individual will not strategically submit preference list L if there exists a more honest L' that yields as preferred an outcome. Then for all marriage algorithms satisfying monotonicity and IIA, every minimally dishonest equilibrium yields a sincerely stable marriage. This result supports the use of algorithms less biased than the (Gale-Shapley) man-optimal, which we prove yields the woman-optimal marriage in every minimally dishonest equilibrium. However, bias cannot be totally eliminated, in the sense that no monotonic IIA stable marriage algorithm is certain to yield the egalitarian-optimal marriage in a minimally dishonest equilibrium – thus answering a 28-year old open question of Gusfield and Irving's in the negative. Finally, we show that these results extend to student placement problems, where women are polygamous and honest, but not to admissions problems, where women are both polygamous and strategic. Based on joint work with Craig Tovey at Georgia Tech.