Dartmouth logo Dartmouth College Computer Science
Technical Report series
CS home
TR home
TR search TR listserv
By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
By number: 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

How hard is it to cheat in the Gale-Shapley Stable Matching Algorithm
Chien-Chung Huang
Dartmouth TR2005-565

Abstract: 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.


PDF PDF (120KB)

Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
   Chien-Chung Huang, "How hard is it to cheat in the Gale-Shapley Stable Matching Algorithm." Dartmouth Computer Science Technical Report TR2005-565, December 2005.


Notify me about new tech reports.

Search the technical reports.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu


Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.