%T Cheating to Get Better Roommates in a Random Stable Matching
%A Chien-Chung Huang
%R Technical Report TR2006-582
%I Dartmouth College, Computer Science
%C Hanover, NH
%D December, 2006
%U http://www.cs.dartmouth.edu/reports/TR2006-582.pdf
%X
This paper addresses strategies for the stable
roommates problem, assuming that a stable matching is chosen at
random. We investigate how a cheating man should permute his
preference list so that he has a higher-ranking roommate
probabilistically.
In the first part of the paper, we identify a necessary condition
for creating a new stable roommate for the cheating man. This
condition precludes any possibility of his getting a new
roommate ranking higher than all his stable roommates when everyone
is truthful. Generalizing
to the case that multiple men collude, we derive another
impossibility result: given any stable matching in which
a subset of men get their best possible roommates, they
cannot cheat to create a new stable matching in which they all get strictly
better roommates than in the given matching.
Our impossibility result, considered in the context of the stable marriage
problem, easily re-establishes the celebrated Dubins-Freedman Theorem.
The more generalized Demange-Gale-Sotomayor Theorem states that
a coalition of men and women cannot cheat to create a stable
matching in which everyone of them gets a strictly better partner
than in the Gale-Shapley algorithm (with men proposing).
We give a sharper result: a coalition of men and women
cannot cheat together so that, in a newly-created stable matching,
every man in the coalition gets a strictly better partner than
in the Gale-Shapley algorithm while none of the women
in the coalition is worse off.
In the second part of the paper, we present two cheating strategies
that guarantee that the cheating man's new probability
distribution over stable roommates majorizes the original one. These
two strategies do not require the knowledge of
the probability distribution of the
cheating man. This is important because the problem of counting stable
matchings is \#P-complete. Our strategies only require knowing the
set of stable roommates that the cheating man has and
can be formulated in polynomial time. Our second cheating strategy
has an interesting corollary in the context of
stable marriage with the Gale-Shapley algorithm.
Any woman-optimal strategy will ensure that every woman,
cheating or otherwise, ends up with a partner at least as good as when everyone is truthful.