There is a famous stable marriage problem.
It's well known that the standard algorithm for stable marriage problem proposed by Shapley and Gale is man-optimal, men get a best according to their preferences among all stable matchings.
truthful game? Men don't have the incentive to change their preferences because by default they get the "best" woman, however women can achieve a better man but deliberately changing their preferences list (not the true preferences, but just the list) in this case a game is not more truthful, and there is a proven result that there is no any truthful mechanism for the stable matching problem?
Problem.The problem is to show that there is always a pure Nash equilibrium in the game of stable marriage problem when players can present altered preference list (when the players can lie).
Ideas.The intuition is optimal matching exists, and only women should care about altering preference list in the run of Gale-Shapley algorithms. However, women don't know the best possible preference list. Therefore it might take few iteration of the Gale-Shapley algorithm to them to figure out what is the best preference list.
How to show it mathematically rigorous is still a problem. Would appreciate any help.