  The stable marriage problem is a well-known problem of matching men to women
so that no man and woman who are not married to each other both prefer each
other. Such a problem has a wide variety of practical applications ranging from
matching resident doctors to hospitals to matching students to schools. A
well-known algorithm to solve this problem is the Gale-Shapley algorithm, which
runs in polynomial time.
  It has been proven that stable marriage procedures can always be manipulated.
Whilst the Gale-Shapley algorithm is computationally easy to manipulate, we
prove that there exist stable marriage procedures which are NP-hard to
manipulate. We also consider the relationship between voting theory and stable
marriage procedures, showing that voting rules which are NP-hard to manipulate
can be used to define stable marriage procedures which are themselves NP-hard
to manipulate. Finally, we consider the issue that stable marriage procedures
like Gale-Shapley favour one gender over the other, and we show how to use
voting rules to make any stable marriage procedure gender neutral.

Artificial Intelligence;Computer Science and Game Theory