Individually Rational Mechanisms for Convex Roommate Problems on Linear Orders

Abstract

Convex preferences open up roommates mechanisms to desirable properties, such as stability. For roommate problems, convex preferences are equivalent to single-peaked preferences. Assumption of individual rationality converts roommate problems from one-sided to two-sided problems. However, stability and strategyproofness are incompatible incentives for roommate problems under assumption of individual rationality and convexity. We explore the limitations that individual rationality bring to convex roommate problems before developing an individually rational, efficient, and strategyproof mechanism for convex roommate problems.