Envy-Free House Allocation under Uncertain Preferences
DOI:
https://doi.org/10.1609/aaai.v38i9.28802Keywords:
GTEP: Fair Division, GTEP: Social Choice / VotingAbstract
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.Downloads
Published
2024-03-24
How to Cite
Aziz, H., Iliffe, I., Li, B., Ritossa, A., Sun, A., & Suzuki, M. (2024). Envy-Free House Allocation under Uncertain Preferences. Proceedings of the AAAI Conference on Artificial Intelligence, 38(9), 9477-9484. https://doi.org/10.1609/aaai.v38i9.28802
Issue
Section
AAAI Technical Track on Game Theory and Economic Paradigms