Thumbnail - No thumbnail

Robust Rent Division

Peters, Dominik; Procaccia, Ariel; Zhu, David (2022-10), Robust Rent Division, Thirty-sixth Conference on Neural Information Processing Systems (NeurIPS 2022), 2022-11, New Orleans, United States

Type
Communication / Conférence
External document link
https://hal.archives-ouvertes.fr/hal-03883471
Date
2022-10
Conference title
Thirty-sixth Conference on Neural Information Processing Systems (NeurIPS 2022)
Conference date
2022-11
Conference city
New Orleans
Conference country
United States
Pages
21
Metadata
Show full item record
Author(s)
Peters, Dominik
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Procaccia, Ariel
Harvard John A. Paulson School of Engineering and Applied Sciences [SEAS]
Zhu, David
Harvard John A. Paulson School of Engineering and Applied Sciences [SEAS]
Abstract (EN)
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.