Manipulating Gale-Shapley Algorithm:
Preserving Stability and Remaining Inconspicuous
Abstract
We study the problem of manipulation of the
men-proposing Gale-Shapley algorithm by a single
woman via permutation of her true preference list.
Our contribution is threefold: First, we show that
the matching induced by an optimal manipulation is
stable with respect to the true preferences. Second,
we identify a class of optimal manipulations called
inconspicuous manipulations which, in addition to
preserving stability, are also nearly identical to the
true preference list of the manipulator (making the
manipulation hard to be detected). Third, for optimal inconspicuous manipulations, we strengthen
the stability result by showing that the entire stable lattice of the manipulated instance is contained
inside the original lattice