<XML><RECORDS><RECORD><REFERENCE_TYPE>3</REFERENCE_TYPE><REFNUM>9321</REFNUM><AUTHORS><AUTHOR>Biro,P.</AUTHOR><AUTHOR>Irving,R.W.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR></AUTHORS><YEAR>2010</YEAR><TITLE>Popular matchings in the Marriage and Roommates problems</TITLE><PLACE_PUBLISHED>Proceedings of CIAC 2010: the 7th International Conference on Algorithms and Complexity, Lecture Notes in Computer Science</PLACE_PUBLISHED><PUBLISHER>Springer</PUBLISHER><LABEL>Biro:2010:9321</LABEL><KEYWORDS><KEYWORD>popular matchings; stable matchings; Marriage problem; Roommates problem; computational complexity</KEYWORD></KEYWORDS<ABSTRACT>Popular matchings have recently been a subject of study in the context of the so-called <i>House Allocation Problem</i>, where the objective is to match applicants to houses over which the applicants have preferences. A matching M is called <i>popular</i> if there is no other matching M' with the property that more applicants prefer their allocation in M' to their allocation in M. In this paper we study popular matchings in the context of the <i>Roommates Problem</i>, including its special (bipartite) case, the <i>Marriage Problem</i>. We investigate the relationship between popularity and stability, and describe efficient algorithms to test a matching for popularity in these settings. We also show that, when ties are permitted in the preferences, it is NP-hard to determine whether a popular matching exists in both the Roommates and Marriage cases.</ABSTRACT></RECORD></RECORDS></XML>