Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements
Authors: Max Springer, MohammadTaghi Hajiaghayi, Hadi Yami
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We here address the problem of fairly allocating indivisible goods or chores to n agents with weights that define their entitlement to the set of indivisible resources. Stemming from well-studied fairness concepts such as envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) for agents with equal entitlements, we present, in this study, the first set of impossibility results alongside algorithmic guarantees for fairness among agents with unequal entitlements. Within this paper, we expand the concept of envy-freeness up to any good or chore to the weighted context (WEFX and XWEF respectively), demonstrating that these allocations are not guaranteed to exist for two or three agents. Despite these negative results, we develop a WEFX procedure for two agents with integer weights, and furthermore, we devise an approximate WEFX procedure for two agents with normalized weights. We further present a polynomial-time algorithm that guarantees a weighted envy-free allocation up to one chore (1WEF) for any number of agents with additive cost functions. Our work underscores the heightened complexity of the weighted fair division problem when compared to its unweighted counterpart. |
| Researcher Affiliation | Collaboration | Max Springer1, Mohammad Taghi Hajiaghayi2, Hadi Yami3 1University of Maryland, Department of Mathematics, College Park MD 2University of Maryland, Department of Computer Science, College Park MD 3Microsoft Corporation, Redmond WA {mss423, hajiagha}@umd.edu, hayami@microsoft.com |
| Pseudocode | Yes | Algorithm 1: Integer Weight WEFX Algorithm, Algorithm 2: Approximate WEFX Algorithm, Algorithm 3: Chore-Division Round-Robin |
| Open Source Code | No | The paper does not provide any concrete access to source code (specific repository link, explicit code release statement, or code in supplementary materials) for the methodology described in this paper. |
| Open Datasets | No | The paper is theoretical and does not describe the use of datasets for training; therefore, it does not provide concrete access information for a publicly available or open dataset. |
| Dataset Splits | No | The paper is theoretical and does not describe experimental data splits; therefore, it does not provide specific dataset split information. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments; therefore, it does not provide specific hardware details used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe experiments or their software dependencies; therefore, it does not provide specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe experiments; therefore, it does not contain specific experimental setup details like hyperparameter values or training configurations. |