Size versus truthfulness in the house allocation problem

DOI10.1007/S00453-019-00584-7MaRDI QIDQ2319628zbMATH OpenOpenAlexWikidataFDO

Authors Piotr Krysta, Baharak Rastegari, Jinshan Zhang, David F. Manlove

Publication date 20 August 2019

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1404.5245

zbMATH Keywords

assignment problemtruthfulnessPareto optimal matchinghouse allocation problemrandomised mechanisms

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Matching models (91B68) Mechanism design theory (91B03)

Abstract: We study the House Allocation problem (also known as the Assignment problem), i.e., the problem of allocating a set of objects among a set of agents, where each agent has ordinal preferences (possibly involving ties) over a subset of the objects. We focus on truthful mechanisms without monetary transfers for finding large Pareto optimal matchings. It is straightforward to show that no deterministic truthful mechanism can approximate a maximum cardinality Pareto optimal matching with ratio better than 2. We thus consider randomised mechanisms. We give a natural and explicit extension of the classical Random Serial Dictatorship Mechanism (RSDM) specifically for the House Allocation problem where preference lists can include ties. We thus obtain a universally truthful randomised mechanism for finding a Pareto optimal matching and show that it achieves an approximation ratio of $fracee-1$. The same bound holds even when agents have priorities (weights) and our goal is to find a maximum weight (as opposed to maximum cardinality) Pareto optimal matching. On the other hand we give a lower bound of $frac1813$ on the approximation ratio of any universally truthful Pareto optimal mechanism in settings with strict preferences. In the case that the mechanism must additionally be non-bossy with an additional technical assumption, we show by utilising a result of Bade that an improved lower bound of $fracee-1$ holds. This lower bound is tight since RSDM for strict preference lists is non-bossy. We moreover interpret our problem in terms of the classical secretary problem and prove that our mechanism provides the best randomised strategy of the administrator who interviews the applicants.

Recommendations

• Size versus fairness in the assignment problem
• Strategy-proofness and the core in house allocation problems
• On the complexity of fair house allocation
• Consistency in house allocation problems
• Envy-freeness in house allocation problems
• Strategy-proof and envy-free mechanisms for house allocation
• Strategy-proofness and population-monotonicity for house allocation problems
• On Low-Envy Truthful Allocations
• Algorithms and Computation
• Algorithms and Computation

Cites work

• scientific article; zbMATH DE number 1104328 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A new solution to the random assignment problem.
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• Algorithms and Computation
• An Analysis of the Greedy Heuristic for Independence Systems
• Assignment Problem Based on Ordinal Preferences
• Competitive weighted matching in transversal matroids
• Fair assignment of indivisible objects under ordinal preferences
• Incentive compatibility in a market with indivisible goods
• On a conjecture by Gale about one-sided matching problems
• On cores and indivisibility
• Online vertex-weighted bipartite matching and single-bid budgeted allocations
• Pairwise kidney exchange
• Pareto optimality in coalition formation
• Pareto optimality in many-to-many matching problems
• Queue allocation of indivisible goods
• Random Matching Under Dichotomous Preferences
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• Random serial dictatorship: the one and only
• Randomized primal-dual analysis of RANKING for online bipartite matching
• Size versus fairness in the assignment problem
• Social welfare in one-sided matching markets without money
• Strategyproof Assignment by Hierarchical Exchange
• The Impossibility of Bayesian Group Decision Making with Separate Aggregation of Beliefs and Values
• The complexity of computing the random priority allocation matrix
• The difference indifference makes in strategy-proof allocation of objects
• Truthful generalized assignments via stable matching
• Weak versus strong domination in a market with indivisible goods
• Welfare maximization and truthfulness in mechanism design with ordinal preferences

Cited in

(18)

• Efficiency of truthful and symmetric mechanisms in one-sided matching
• A pessimist's approach to one-sided matching
• Decomposing random mechanisms
• Pareto optimal matchings with lower quotas
• Allocating group housing
• Counting houses of Pareto optimal matchings in the house allocation problem
• Improved truthful rank approximation for rank-maximal matchings
• Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship
• Optimizing over serial dictatorships
• House markets with matroid and knapsack constraints
• On the complexity of fair house allocation
• Set systems related to a house allocation problem
• House allocation problems with existing tenants and priorities for teacher recruitment
• Pareto optimal matchings in many-to-many markets with ties
• Social welfare in one-sided matchings: random priority and beyond
• Tight social welfare approximation of probabilistic serial
• Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship
• Optimizing over serial dictatorships

This page was built for publication: Size versus truthfulness in the house allocation problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2319628)