Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Your College Dorm and Dormmates: Fair Resource Sharing with Externalities
Authors: Jiarui Gan, Bo Li, Yingkai Li
JAIR 2023 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study a fair resource sharing problem, where a set of resources are to be shared among a group of agents. Each agent demands one resource and each resource can serve a limited number of agents. An agent cares about what resource they get as well as the externalities imposed by their mates, who share the same resource with them. Clearly, the strong notion of envy-freeness, where no agent envies another for their resource or mates, cannot always be achieved and we show that even deciding the existence of such a strongly envy-free assignment is an intractable problem. Hence, a more interesting question is whether (and in what situations) a relaxed notion of envy-freeness, the Pareto envyfreeness, can be achieved. Under this relaxed notion, an agent envies another only when they envy both the resource and the mates of the other agent. In particular, we are interested in a dorm assignment problem, where students are to be assigned to dorms with the same capacity and they have dichotomous preference over their dormmates. We show that when the capacity of each dorm is 2, a Pareto envy-free assignment always exists and we present a polynomial-time algorithm to compute such an assignment. Nevertheless, the result breaks immediately when the capacity increases to 3, in which case even Pareto envyfreeness cannot be guaranteed. In addition to the existential results, we also investigate the utility guarantees of (Pareto) envy-free assignments in our model. |
| Researcher Affiliation | Academia | Jiarui Gan EMAIL University of Oxford Oxford, United Kingdom Bo Li EMAIL (Corresponding author) Department of Computing, The Hong Kong Polytechnic University Hong Kong, China Yingkai Li EMAIL Cowles Foundation for Research in Economics, Yale University New Haven, CT, United States |
| Pseudocode | Yes | Algorithm 1: Find a PEF assignment when dorms have capacity 2. |
| Open Source Code | No | The paper does not provide any specific links to source code repositories or explicit statements about code availability. |
| Open Datasets | No | The paper uses constructed examples (e.g., Example 4.4, Example 5.7) to illustrate theoretical concepts and proofs, rather than relying on publicly available datasets for empirical evaluation. |
| Dataset Splits | No | The paper does not conduct empirical experiments with datasets, therefore, there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper focuses on theoretical analysis, algorithmic design, and complexity proofs. It does not describe any experimental setups that would require hardware specifications. |
| Software Dependencies | No | The paper focuses on theoretical analysis and algorithmic design, including complexity proofs and algorithms. It does not mention any specific software or library versions used for implementation or experimentation. |
| Experiment Setup | No | The paper is theoretical in nature, presenting models, definitions, proofs, and algorithms. It does not describe any empirical experiments, and therefore, no experimental setup details like hyperparameters or training configurations are provided. |