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