A mechanism uses the deferred acceptance algorithm with women proposing to match the set of men = {1, 2, ... , } with the set of women = {1, 2, ... , }. Men have strict preferences over women, and women have strict preferences over men. Their true preferences are denoted by . The resulting matching is the woman-optimal matching .

Man 1 finds that he would prefer the outcome generated by the deferred acceptance algorithm with women proposing, using preferences . In man 1 misrepresents his preferences in his optimal way (ie. he is matched in with his most preferred woman achievable through misrepresentation). For all other men, and for all women, their preferences in are identical to their true preferences .

a) Prove that the matching is stable with respect to the true preferences . (You may assume the result that the matching is stable with respect to the preferences used to derive it.)