[Colloq] Reminder: Today, Monday, April 9 - Chien-Chung Huang

[Rachel Kalweit]

College of Computer and Information Science Colloquium

Presents:
Chien-Chung Huang
Dartmouth College

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


_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq