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