For this assignment, you are required to turn in solutions to any two of Problems 1 through 4, which appear in Section 2 below. Your solutions are due at the beginning of class on Thursday, February 9.

University of Texas at Austin Department of Computer Science Algorithms and Complexity CS 331, Spring 2017 Assignment #2 Greg Plaxton January 31, 2017 For this assignment, you are required to turn in solutions to any two of Problems 1 through 4, which appear in Section 2 below. Your solutions are due at the beginning of class on Thursday, February 9. Please refer to the course syllabus for the ground rules concerning collaboration, and for the slack day policy governing lateness. Any corrections or clarifications related to this assignment will be announced in the lectures and on Piazza. You are responsible for being aware of any such announcements. 1 Exercises The following textbook exercises are recommended to help you to prepare for the tests. We will not be grading your solutions to these exercises, so you do not need to turn anything in. 1. Exercise 3.10, page 110. 2. Exercise 3.12, page 112. 3. Exercise 4.15, page 196. 4. Exercise 4.28, page 203. 2 Programming & Problem Solving In this part of the assignment, we continue our investigation of the SMI problem introduced in Assignment 1. In the first lecture (see also Section 1.1 of the textbook), we described the deferred acceptance algorithm for the SM problem. We showed that given any instance I of the SM problem, the deferred acceptance algorithm produces a stable matching. In Problem 3 of Assignment 1, we showed that there is a natural way to modify the deferred acceptance algorithm so that it produces a stable matching on any given SMI instance. When we discussed the deferred acceptance algorithm for the SM problem, we showed that the stable matching µ it produces is “man-optimal” in the sense that each man likes 1 University of Texas at Austin Department of Computer Science Algorithms and Complexity CS 331, Spring 2017 his partner in µ at least as well as his partner in any other stable matching. The concept of man-optimality is easily adapted to the context of the SMI problem; in this context, we just need to bear in mind that an agent’s partner in a given matching might be “no partner”, i.e., being single is a possible outcome. Using arguments similar to the corresponding arguments for SM, it can be shown that for the SMI problem, the stable matching produced by the deferred acceptance algorithm (i.e., the version that we developed in Problem 3 of Assignment 1) is man-optimal. It follows that even though the deferred acceptance algorithm is nondeterministic — and hence can execute in many different ways on a given SMI instance — the final output is uniquely determined; in the problem hints below, we refer to this as the “confluence property” of the deferred acceptance algorithm. For any instance I of the SMI problem, we define da(I) as the stable matching produced 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 to q in da(I 0 ); otherwise, p is single in da(I 0 ). Hints: (1) Use the confluence property of the deferred acceptance algorithm; (2) Observe that once execution of the deferred acceptance algorithm reaches a state where there is exactly one single man who has not proposed to all of his acceptable women, the rest of the execution is deterministic. Definition: For any SMI instance I and any woman q in I, we define the unique element x identified in Problem 1 as threshold(I, q). Problem 2. Let I be an SMI instance, let q be a woman in I, let p be a man who is not in I, and let I 0 be an SMI instance in add(I, p, q). Prove that no woman q 0 in I prefers threshold(I, q0 ) to threshold(I 0 , q0 ). Hints: (1) Use proof by contradiction, i.e., assume that there is a woman q 0 who prefers threshold(I, q0 ) to threshold(I 0 , q0 ), and derive a contradiction; (2) Use the confluence property of the deferred acceptance algorithm. Problem 3. Let I be an SMI instance, let q be a woman in I, let p be a man who is not in I, and let I 0 be an SMI instance in add(I, p, q). Prove that if p is single in 2 University of Texas at Austin Department of Computer Science Algorithms and Complexity CS 331, Spring 2017 da(I 0 ), then threshold(I 0 , q0 ) = threshold(I, q0 ) for every woman q 0 in I. Hints: (1) Use proof by contradiction, i.e., assume p is single in da(I 0 ) and there is a woman q 0 such that threshold(I 0 , q0 ) 6= threshold(I, q0 ), and derive a contradiction; (2) Use the result of Problem 2; (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 , q0 ) = threshold(I, q0 ) for every woman q 0 in I. For any SMI instance I and man p, let instances(I, p) denote the set of all SMI instances I 0 that are identical to I except for the preferences expressed by man p. Problem 4 below asks you to prove that the deferred acceptance algorithm is “strategyproof for the men” which means that for any SMI instance I, any man p in I, and any SMI instance I 0 in instances(I, p), man p likes the outcome he obtains in da(I) at least as well as the outcome he obtains in da(I 0 ). Informally, this property means that no man can benefit by lying when he provides preference information to the deferred acceptance algorithm. (In Exercise 1.8 of the text, which appeared on Assignment 1 as a recommended exercise, this property is referred to as truthfulness.) Problem 4. Prove that the deferred acceptance algorithm for the SMI problem is strategyproof for the men. Hints: (1) Use the confluence property of the deferred acceptance algorithm; (2) Use Lemma Extend. 3

Looking for a Similar Assignment? Order now and Get 10% Discount! Use Coupon Code "Newclient"