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