Envy-Free House Allocation Under Uncertain Preferences
Abstract
Envy-freeness is one of the most important fairness concerns when allocating items. We study envy-free house allocation when agents have uncertain preferences over items and consider several well-studied preference uncertainty models. The central problem that we focus on is computing an allocation that has the highest probability of being envy-free. We show that each model leads to a distinct set of algorithmic and complexity results, including detailed results on (in-)approximability. En route, we consider two related problems of checking whether there exists an allocation that is possibly or necessarily envy-free. We give a complete picture of the computational complexity of these two problems for all the uncertainty models we consider.
Cite
Text
Aziz et al. "Envy-Free House Allocation Under Uncertain Preferences." AAAI Conference on Artificial Intelligence, 2024. doi:10.1609/AAAI.V38I9.28802Markdown
[Aziz et al. "Envy-Free House Allocation Under Uncertain Preferences." AAAI Conference on Artificial Intelligence, 2024.](https://mlanthology.org/aaai/2024/aziz2024aaai-envy/) doi:10.1609/AAAI.V38I9.28802BibTeX
@inproceedings{aziz2024aaai-envy,
title = {{Envy-Free House Allocation Under Uncertain Preferences}},
author = {Aziz, Haris and Iliffe, Isaiah and Li, Bo and Ritossa, Angus and Sun, Ankang and Suzuki, Mashbat},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2024},
pages = {9477-9484},
doi = {10.1609/AAAI.V38I9.28802},
url = {https://mlanthology.org/aaai/2024/aziz2024aaai-envy/}
}