Envy-Free House Allocation under Uncertain Preferences
Haris Aziz, Isaiah Iliffe, Bo Li, Angus Ritossa, Ankang Sun, Mashbat Suzuki
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.
BibTeX
@article{Aziz_Iliffe_Li_Ritossa_Sun_Suzuki_2024, title={Envy-Free House Allocation under Uncertain Preferences}, volume={38}, url={https://ojs.aaai.org/index.php/AAAI/article/view/28802}, DOI={10.1609/aaai.v38i9.28802}, abstractNote={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.}, number={9}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Aziz, Haris and Iliffe, Isaiah and Li, Bo and Ritossa, Angus and Sun, Ankang and Suzuki, Mashbat}, year={2024}, month={Mar.}, pages={9477-9484} }