Envy-freeness in house allocation problems

DOI10.1016/J.MATHSOCSCI.2019.07.005zbMATH Open1426.91145arXiv1905.00468OpenAlexW3102305729MaRDI QIDQ2334840FDOQ2334840

Authors: Jiarui Gan, Warut Suksompong, Alexandros A. Voudouris 

Publication date: 8 November 2019

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

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.

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

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

zbMATH Keywords

polynomial-time algorithmhouse allocationenvy-free assignment

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

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

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)