  Gale and Sotomayor (1985) have shown that in the Gale-Shapley matching
algorithm (1962), the proposed-to side W (referred to as women there) can
strategically force the W-optimal stable matching as the M-optimal one by
truncating their preference lists, each woman possibly blacklisting all but one
man. As Gusfield and Irving have already noted in 1989, no results are known
regarding achieving this feat by means other than such preference-list
truncation, i.e. by also permuting preference lists.
  We answer Gusfield and Irving's open question by providing tight upper bounds
on the amount of blacklists and their combined size, that are required by the
women to force a given matching as the M-optimal stable matching, or, more
generally, as the unique stable matching. Our results show that the coalition
of all women can strategically force any matching as the unique stable
matching, using preference lists in which at most half of the women have
nonempty blacklists, and in which the average blacklist size is less than 1.
This allows the women to manipulate the market in a manner that is far more
inconspicuous, in a sense, than previously realized. When there are less women
than men, we show that in the absence of blacklists for men, the women can
force any matching as the unique stable matching without blacklisting anyone,
while when there are more women than men, each to-be-unmatched woman may have
to blacklist as many as all men. Together, these results shed light on the
question of how much, if at all, do given preferences for one side a priori
impose limitations on the set of stable matchings under various conditions. All
of the results in this paper are constructive, providing efficient algorithms
for calculating the desired strategies.
