  We consider the stability of matchings when individuals strategically submit
preference information to a publicly known algorithm. Most pure Nash equilibria
of the ensuing game yield a matching that is unstable with respect to the
individuals' sincere preferences. We introduce a well-supported minimal
dishonesty constraint, and obtain conditions under which every pure Nash
equilibrium yields a matching that is stable with respect to the sincere
preferences. The conditions on the matching algorithm are to be either
fully-randomized, or monotonic and independent of non-spouses (INS), an
IIA-like property. These conditions are significant because they support the
use of algorithms other than the Gale-Shapley (man-optimal) algorithm for
kidney exchange and other applications. We prove that the Gale-Shapley
algorithm always yields the woman-optimal matching when individuals are
minimally dishonest. However, we give a negative answer to one of Gusfield and
Irving's open questions: there is no monotonic INS or fully-randomized stable
matching algorithm that is certain to yield the egalitarian-optimal matching
when individuals are strategic and minimally dishonest. Finally, we show that
these results extend to the student placement problem, where women are
polyandrous but must be honest but do not extend to the admissions problem,
where women are both polyandrous and strategic.
