Unilateral substitutability implies substitutable completability in many-to-one matching with contracts

We prove that the unilateral substitutability property introduced in Hatfield and Kojima (2010) implies the substitutable completability property from Hatfield and Kominers (2014). This paper provides a novel linkage between these two sufficient conditions for the existence of a stable matching in many-to-one matching markets with contracts. A substitutable completion of a preference is a substitutable preference created by adding some sets of contracts to the original preference order. We provide an algorithm which when operated on the unilaterally substitutable preferences produces such a substitutable completion. Thus it provides a constructive proof of the connection between the two properties.