Strategyproof Matching of Roommates and Rooms

We initiate the study of matching roommates and rooms wherein the preferences of agents over other agents and rooms are complementary and represented by Leontief utilities. In this setting, 2n agents must be paired up and assigned to n rooms. Each agent has cardinal valuations over the rooms as well as compatibility values over all other agents. Under Leontief preferences, an agent's utility for a matching is the minimum of the two values. We focus on the tradeoff between maximizing utilitarian social welfare and strategyproofness. Our main result shows that-in a stark contrast to the additive case-under binary Leontief utilities, there exist strategyproof mechanisms that maximize the social welfare. We further devise a strategyproof mechanism that implements such a welfare maximizing algorithm and is parameterized by the number of agents. Along the way, we highlight several possibility and impossibility results, and give upper bounds and lower bounds for welfare with or without strategyproofness. Leontief Additive General Binary General Binary SW APX-h † (Thm. 3.6) APX-h † (Thm. 3.6) NP-h * NP-h * SP Upper Bound ✗ (Thm. 4.1) 1 (Thm. 4.6) ✗ (Thm. 4.1) 2 /3 (Thm. 4.2) SP (Polytime) ✗ (Thm. 4.1) 1 /3 (Thm. 4.9) ✗ (Thm. 4.1) 1 /7 (Thm. 4.8) Table 1: Summary of the tradeoff between social welfare (SW) and strategyproofness (SP). Here ✗ denotes that no strategyproof mechanism can give any non-zero approximation of SW. APX-h and NP-h denote APX and NP-hardness, resp. * denotes a result by [20] and † indicates bounds that hold even for binary and symmetric valuations. From the theoretical perspective, binary valuations pose many technical challenges in achieving axiomatic results when dealing with strategyproofness (e.g. stable matchings [51] ) and in developing computationally tractable algorithms (e.g. fair division [38] ). Table 1 summarizes our main results under Leontief utilities with general or binary valuations. Social Welfare. We investigate various approaches for finding maximal matchings in the roommate matching problems, and analyze their welfare bounds. We develop a greedy algorithm for finding a maximal matching and show that its satisfies 1 ⁄3-SW, resembling the same bound for maximal 3-dimensional matching. We then show that under Leontief utilities, finding a social welfare (SW) maximizing matching is APX-hard even when the valuations are binary and symmetric (Theorem 3.6). 3 We then show that there exists an 0.559-approximation algorithm for any type of utility function (Proposition 3.8). Strategyproof Mechanisms. When requiring strategyproofness, we show that no strategyproof mechanism can satisfy any approximation of social welfare, with arbitrary valuations over rooms or roommates. This negative result holds for both Leontief and additive utilities (Theorem 4.1), and raises the question of whether it is possible to escape the impossibility by restricting the valuation domain. For additive utilities with binary valuations, we prove an upper bound on the social welfare of any strategyproof mechanism. In particular, in Theorem 4.2 and Corollary 4.3, we show that no strategyproof mechanism can satisfy α-SW for any α > 2/3 for binary but not symmetric preferences or α > 3/4 for binary and symmetric preferences (Theorem 4.2). Our main result shows that-in stark contrast with its additive counterpart-under Leontief utilities with binary valuations, there exists a strategyproof mechanism that maximizes social welfare (Theorem 4.4). We develop a novel mechanism that repeatedly reduces the welfare set by 'shrinking' the potential strategy space. We show that this mechanism runs in time O * (n 2n ). 4 Computation and Algorithms. Our welfare maximizing strategyproof mechanism runs in exponential time; given our intractability result in Theorem 3.6, no polynomial-time mechanism can be expected, unless P=NP. Nonetheless, we develop a Fixed Parameter Tractable (FPT) algorithm that implements our strategyproof mechanism while maximizing the social welfare. This algorithm is parameterized by the number of agents which runs in time O * (c n ) where c > 0 is a constant. 5