Envy-freeness in house allocation problems

DOI10.1016/J.MATHSOCSCI.2019.07.005MaRDI QIDQ2334840zbMATH OpenOpenAlexFDO

Authors Jiarui Gan, Warut Suksompong, Alexandros A. Voudouris

Publication date 8 November 2019

Published in Mathematical Social Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.00468, http://repository.essex.ac.uk/27268/1/1905.00468v2.pdf

zbMATH Keywords

polynomial-time algorithmhouse allocationenvy-free assignment

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: We consider the house allocation problem, where $m$ houses are to be assigned to $n$ agents so that each agent gets exactly one house. We present a polynomial-time algorithm that determines whether an envy-free assignment exists, and if so, computes one such assignment. We also show that an envy-free assignment exists with high probability if the number of houses exceeds the number of agents by a logarithmic factor.

Recommendations

• An algorithm for envy-free allocations in an economy with indivisible objects and money
• House allocation with fractional endowments
• Competitive envy-free division
• When do envy-free allocations exist?
• Fair assignment of indivisible objects under ordinal preferences

Cites work

• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• Algorithms and Computation
• Approximation Algorithms for Computing Maximin Share Allocations
• On a conjecture by Gale about one-sided matching problems
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• The Impossibility of Bayesian Group Decision Making with Separate Aggregation of Beliefs and Values

Cited in

(12)

• The envy-free matching problem with pairwise preferences
• Envy-free matchings with one-sided preferences and matroid constraints
• On the complexity of fair house allocation
• Your college dorm and dormmates: fair resource sharing with externalities
• Closing gaps in asymptotic fair division
• House allocation with fractional endowments
• On the number of almost envy-free allocations
• Fair multi-cake cutting
• Size versus truthfulness in the house allocation problem
• Algorithms and Computation
• Fair cake-cutting among families
• Envy-free matchings in bipartite graphs and their applications to fair division

This page was built for publication: Envy-freeness in house allocation problems

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