Dartmouth College Computer Science
Technical Report series
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|
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.
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.