Envy-Free House Allocation under Uncertain Preferences
Authors: Haris Aziz, Isaiah Iliffe, Bo Li, Angus Ritossa, Ankang Sun, Mashbat Suzuki
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the envy-free house allocation problem 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. |
| Researcher Affiliation | Academia | Haris Aziz1, Isaiah Iliffe1, Bo Li2, Angus Ritossa1, Ankang Sun2, Mashbat Suzuki1 1UNSW Sydney 2Hong Kong Polytechnic University haris.aziz@unsw.edu.au, i.iliffe@student.unsw.edu.au, bo.li@polyu.edu.hk, a.ritossa@student.unsw.edu.au, ankang.sun@polyu.edu.hk, mashbat.suzuki@unsw.edu.au |
| Pseudocode | Yes | Algorithm 1: Additive Approximation for MAX-PROBEF |
| Open Source Code | No | The paper does not provide a direct link to a source-code repository or explicitly state that the code for the described methodology is being released. |
| Open Datasets | No | This paper is theoretical and does not use datasets for training or evaluation. |
| Dataset Splits | No | This paper is theoretical and does not involve data splits for training, validation, or testing. |
| Hardware Specification | No | This paper is theoretical and does not report on specific hardware used for experiments. |
| Software Dependencies | No | This paper is theoretical and does not specify software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | This paper is theoretical and does not include details on an experimental setup, hyperparameters, or training configurations. |