2021/07/09 by Michael McKay, McKay, Michael, David F. Manlove +1 · 1 citation
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Economic theories and models #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2107.04368
openalex publication_date 2021/07/09 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
The Stable Roommates problem involves matching a set of agents into pairs\nbased on the agents' strict ordinal preference lists. The matching must be\nstable, meaning that no two agents strictly prefer each other to their assigned\npartners. A number of three-dimensional variants exist, in which agents are\ninstead matched into triples. Both the original problem and these variants can\nalso be viewed as hedonic games. We formalise a three-dimensional variant using\ngeneral additively separable preferences, in which each agent provides an\ninteger valuation of every other agent. In this variant, we show that a stable\nmatching may not exist and that the related decision problem is NP-complete,\neven when the valuations are binary. In contrast, we show that if the\nvaluations are binary and symmetric then a stable matching must exist and can\nbe found in polynomial time. We also consider the related problem of finding a\nstable matching with maximum utilitarian welfare when valuations are binary and\nsymmetric. We show that this optimisation problem is NP-hard and present a\nnovel 2-approximation algorithm.\n