Testing substitutability of weak preferences

In various models of matching markets, substitutable preferences constitute the largest domain for which stable matchings are guaranteed to exist. Recently, Hatfield et al. (2012) have proposed an efficient algorithm to test substitutability of strict preferences. In this note we show how the algorithm by Hatfield et al. can be adapted in such a way that it can test substitutability of weak preferences as well. When restricted to the domain of strict preferences, our algorithm is faster than Hatfield et al.’s original algorithm by a linear factor.

► We study a property of preferences called substitutability. ► We extend a recently proposed algorithm to test substitutability of weak preferences. ► On the domain of strict preferences, our algorithm is faster by a linear factor.