Strategyproof Matching of Roommates and Rooms
Authors: Hadi Hosseini, Shivika Narang, Sanjukta Roy
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 SP mechanisms that maximize the social welfare. We further devise a SP 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. |
| Researcher Affiliation | Academia | Hadi Hosseini1, Shivika Narang2, Sanjukta Roy3 1Pennsylvania State University 2University of New South Wales, Sydney 3Indian Statistical Institute, Kolkata EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: Triangle-then-L Maximal Matching; Algorithm 2: Welfare Set Reduction Mechanism; Algorithm 3: Precedence-Based Search Mechanism |
| Open Source Code | No | The paper does not provide any explicit statement about releasing source code, nor does it include a link to a code repository for the described methodology. |
| Open Datasets | No | The paper focuses on theoretical analysis and algorithm design for matching roommates and rooms, defining a model with Leontief utilities and binary valuations. It does not report on experiments using any specific dataset, nor does it provide access information for any open datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation on datasets, thus no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setups or computational experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental implementations that would list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical analysis, algorithm design, and proof sketches, and does not include any experimental setup details such as hyperparameters or training configurations. |