by the deferred acceptance algorithm , and we define matched ( I ) as the set of men who are matched ( i . e ., not single ) in da ( I ). For any SMI instance I , any woman q in I , and any man p who is not in I , we define add ( I , p , q ) as the set of all SMI instances that are the same as I except that ( 1 ) p is added to the set of men , ( 2 ) the preferences of p are such that q is acceptable to p and all other women are unacceptable to p , and ( 3 ) the preferences of each woman in I are augmented to incorporate p . To clarify ( 3 ), consider a woman q 0 in I who finds ` of the men in I to be acceptable . There are ` + 2 ways for q 0 to augment her preferences to incorporate p : she can classify p as acceptable , in which case there are ` + 1 different ways she can insert p into her strict ranking of acceptable men , or she she can classify p as unacceptable . In the statement of Problem 1 below , we use the symbol ∅ as follows : If we say that a woman q prefers a man p to ∅ , we mean that q considers p to be acceptable ; conversely , if we say that q prefers ∅to p , it means that q considers p to be unacceptable . Problem 1 . Let I be an SMI instance and let q be a woman in I . Prove that there is a unique element x of matched ( I )+ ∅ such that the following conditions hold for any man p who is not in I and any SMI instance I 0 in add ( I , p , q ): if q prefers p to x in I 0 , then p is matched