Events - Colloquia & Seminars

CCIS Colloquium Spring 2007

Cheating Strategies in the Stable Marriage and Stable Roommates Problems

Speaker: Chien-Chung Hwang

Affiliation: Dartmoth University

Date: Monday, April 9, 2007

Talk: 12:00 p.m. - 1:00 p.m., 366 WVH

Abstract

The stable marriage and the stable roommates problem, since their inception by Gale and Shapley, have been a source of interest for mathematicians, computer scientists, economists and operation researchers. The strategic aspect of these two problems has been intriguing researchers: whether a (group of) person(s) can cheat so that they can get better wives/husbands/roommates?

In this talk, we will report both positive and negative results. Especially we will focus on the following question: how can a group of men cheat so that they can get higher-ranking partners in their preference? A classical theorem by Dubins and Freedman states that it is impossible that a group of cheating men all get better partners after they falsify their preference lists. This impossibility result seems to preclude any chance of men cheating to benefit. But is it really so? Can we devise some randomized mechanisms to get around this impossibility theorem? Can a coalition of cheating men try to lobby some women to help them? We shall investigate these issues extensively in this talk.

Brief Biography

Chien-Chung Huang got his B.S and M.S. degrees at National Taiwan University. After finishing his military service, he went to Dartmouth College to pursue a Ph.D. degree in computer science. He is now doing his third year under the direction of Dr. Peter Winkler. His primary research interest is on the stable marriage problem, along with all its related combinatorial problems. Besides these, he is also interested in distributed algorithms.