Robust Rent Division

Dominik Peters (), Ariel D. Procaccia and David Zhu
Additional contact information
Dominik Peters: LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision - Université Paris Dauphine-PSL - PSL - Université Paris Sciences et Lettres - CNRS - Centre National de la Recherche Scientifique
Ariel D. Procaccia: SEAS - Harvard John A. Paulson School of Engineering and Applied Sciences - Harvard University
David Zhu: SEAS - Harvard John A. Paulson School of Engineering and Applied Sciences - Harvard University

Post-Print from HAL

Abstract: In fair rent division, the problem is to assign rooms to roommates and fairly split the rent based on roommates' reported valuations for the rooms. Envy-free rent division is the most popular application on the fair division website Spliddit. The standard model assumes that agents can correctly report their valuations for each room. In practice, agents may be unsure about their valuations, for example because they have had only limited time to inspect the rooms. Our goal is to find a robust rent division that remains fair even if agent valuations are slightly different from the reported ones. We introduce the lexislack solution, which selects a rent division that remains envy-free for valuations within as large a radius as possible of the reported valuations. We also consider robustness notions for valuations that come from a probability distribution, and use results from learning theory to show how we can find rent divisions that (almost) maximize the probability of being envy-free, or that minimize the expected envy. We show that an almost optimal allocation can be identified based on polynomially many samples from the valuation distribution. Finding the best allocation given these samples is NP-hard, but in practice such an allocation can be found using integer linear programming.

Date: 2022-11-28
New Economics Papers: this item is included in nep-des
Note: View the original document on HAL open archive server: https://hal.science/hal-03883471v1
References: Add references at CitEc
Citations:

Published in Advances in Neural Information Processing Systems 35 (NeurIPS 2022), Nov 2022, New Orleans, United States

Downloads: (external link)
https://hal.science/hal-03883471v1/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-03883471

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().