[Colloq] Monday, April 9 - Chien-Chung Huang

[Rachel Kalweit]

College of Computer and Information Science Colloquium

Presents:
Chien-Chung Huang
Dartmouth University

Who will speak on:
“Cheating Strategies in the Stable Marriage and Stable Roommates Problems”

Monday, April 9, 2007
12:00 pm
366 West Village H
Northeastern University

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.

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.

Host: Ravi Sundaram