Men cheating in the Gale-Shapley stable matching algorithm

We study strategy issues surrounding the stable marriage problem. Under the Gale-Shapley algorithm (with men proposing), a classical theorem says that it is impossible for every liar to get a better partner. We try to challenge this theorem. First, observing a loophole in the statement of the theorem, we devise a coalition strategy in which a non-empty subset of the liars gets a better partner and no man is worse off than before. This strategy is restricted in that not everyone has the incentive to cheat. We attack the classical theorem further by means of randomization. However, this theorem shows surprising robustness: it is impossible that every liar has the chance to improve while no one gets hurt. Hence, this impossibility result indicates that it is always hard to induce some people to falsify their lists. Finally, to overcome the problem of lacking motivation, we exhibit another randomized lying strategy in which every liar can expect to get a better partner, though with a chance of getting a worse one.