Testing substitutability of weak preferences

详细信息    查看全文

• 作者：Haris Aziz^a ; ^{haris.aziz@nicta.com.au} ; Markus Brill^b ; ^{brill@in.tum.de} ; Paul Harrenstein^c ; ^{paul.harrenstein@cs.ox.uk}
• 刊名：Mathematical Social Sciences
• 出版年：2013
• 出版时间：July, 2013
• 年：2013
• 卷：66
• 期：1
• 页码：91-94
• 全文大小：214 K

文摘

In various models of matching markets, substitutable preferences constitute the largest domain for which stable matchings are guaranteed to exist. Recently, 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.