Research map / Multi-agent systems and games / Games and equilibria
Strategyproof Matching of Roommates and Rooms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies strategyproof matching of roommates to rooms under Leontief and additive utilities, showing that under binary Leontief utilities welfare-maximizing strategyproof mechanisms exist (exponential-time and FPT), alongside approximation bounds and impossibilities.
Problem
x
Approach
Models roommate-room preferences with Leontief (min) utilities to capture complementarity; shows that under binary valuations, a welfare-maximizing mechanism can be made strategyproof via a welfare-set reduction with agent-precedence tie-breaking, in contrast to the impossibility for additive utilities; also gives polynomial-time triangle-then-L greedy mechanisms with 1/3 welfare guarantees.
Key results
- Under binary Leontief utilities, a Welfare Set Reduction mechanism returns a maximum social welfare matching and is strategyproof, running in O*(13.36^n) randomized time via a precedence-based search.
- For general valuations under Leontief or additive utilities, no strategyproof mechanism guarantees any positive approximation of social welfare.
- For binary additive utilities, no strategyproof mechanism can guarantee more than a 2/3 approximation (3/4 when symmetric).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Welfare Set Reduction to select among maximum-welfare matchings | Roommate-room matching with binary Leontief utilities · Binary Leontief utilities | social welfare: maximum welfare | Helped |
| Use Precedence-Based Search with 3-Set Packing | Roommate-room matching with binary Leontief utilities · Binary Leontief utilities | social welfare: maximum welfare | Helped |
| Choose the highest-utility triple, preferring triangles over L-shapes | Roommate matching · All utility types and unrestricted valuations | social welfare approximation: \sfrac{1}{3} | Helped |
| Use Triangle-then-L with deterministic tie-breaking | Roommate matching mechanism · Binary Leontief utilities | strategyproof welfare approximation: \sfrac{1}{3} | Helped |
| Use L/T Serial Dictatorship | Roommate matching mechanism · Binary Leontief utilities | strategyproof welfare approximation: \sfrac{1}{6} | Helped |
| Choose an agent-agent edge before an agent-room edge | Naive maximal matching · Binary symmetric Leontief utilities | social welfare approximation: 0 -> \sfrac{1}{6} | Helped |
| Use a naive maximal matching from the preference graph | Roommate matching · Binary Leontief utilities | social welfare approximation: 0 | Hurt |
| Use a 3-Set Packing approximation algorithm | Welfare maximization in roommate matching · Leontief utilities | social welfare approximation: 0.559 | Helped |
| Use naive maximal matching | Roommate matching · Binary additive utilities | social welfare approximation: \sfrac{1}{4} | Helped |
| Require strategyproofness under unrestricted valuations | Any mechanism with Leontief or additive utilities · Unrestricted valuations | social welfare approximation: no non-zero approximation | Hurt |
| Require strategyproofness under binary additive valuations | Any mechanism · Binary additive utilities | social welfare approximation upper bound: \sfrac{2}{3} | Hurt |
| Require strategyproofness under binary symmetric additive valuations | Any mechanism · Binary symmetric additive utilities | social welfare approximation upper bound: \sfrac{3}{4} | Hurt |
Surprising findings
- Unlike the additive case, welfare-maximizing strategyproof mechanisms exist under binary Leontief utilities.
- Under general valuations, no strategyproof mechanism achieves any nonzero welfare approximation.
Limitations
- The strategyproof welfare-maximizing mechanisms are exponential time, and NP-hardness/APX-hardness rules out polynomial-time exact algorithms unless P=NP.
- Strategyproofness positive results rely on binary valuations; general valuations admit no strategyproof approximation.
Experimental setup
Metrics: utilitarian social welfare approximation ratio strategyproofness
Baselines: additive-utility welfare algorithm (2/3-approximation) naive maximal matching naive serial dictatorship
Builds on: 3-set packing serial dictatorship
Closest papers by meaning
- Welfare-Optimal Serial Dictatorships Have Polynomial Query Complexity (AAAI 2025 · similarity 0.87)
- Multi-Apartment Rent Division (AAAI 2025 · similarity 0.86)
- Envy-Free House Allocation under Uncertain Preferences (AAAI 2024 · similarity 0.86)
- Maximizing Nash Social Welfare under Two-Sided Preferences (AAAI 2024 · similarity 0.86)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.86)
- Weak Strategyproofness in Randomized Social Choice (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.