--------------------------------------------------------------------------------------- CS210 Introduction to Java Programming Assignment FOR MORE CLASSES VISIT
( 3) Use the confluence property of the deferred acceptance algorithm. Problems 1 through 3 above are concerned with modifying an SMI instance I by adding a new man. We now consider a way to modify an SMI instance without adding a new agent. For any SMI instance I, any woman q in I, and any man p in I who is single in da( I) and considers q to be unacceptable, we define extend( I, p, q) as the SMI instance I 0 that is identical to I except the preferences of man p are modified as follows: man p moves woman q from his unacceptable set to the the least-preferred position in his ordered list of acceptable women. The arguments used for solving Problems 1, 2, and 3 are easily adapted to establish Lemma Extend below; the proof is omitted. Lemma Extend. Let I be an SMI instance, let q be a woman in I, let p be a man in I who is single in da( I) and considers q to be unacceptable, and let I 0 denote the SMI instance extend( I, p, q). If q prefers p to threshold( I, q), then p is matched to q in da( I 0); otherwise, p is single in da( I 0) and threshold( I 0, q 0) = threshold( I, q 0) for every woman q 0 i
--------------------------------------------------------------------------------------- CS210 Introduction to Java Programming Assignment FOR MORE CLASSES VISIT