Cheating Strategies in the Stable Matching Problems

present their preferences and the goal is to find a matching
in which no two persons have incentive to divorce or to desert their
roommates.
Efficient algorithms have been designed to find the stable matchings.
However, 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 a stable matching?

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 wives 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.