An EF2X Allocation Protocol for Restricted Additive Valuations
Authors: Hannaneh Akrami, Rojin Rezvan, Masoud Seddighin
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of fairly allocating a set of indivisible goods to a set of n agents. Envy-freeness up to any good (EFX) criterion (which requires that no agent prefers the bundle of another agent after the removal of any single good) is known to be a remarkable analogue of envy-freeness when the resource is a set of indivisible goods. In this paper, we investigate EFX for restricted additive valuations, that is, every good has a non-negative value, and every agent is interested in only some of the goods. We introduce a natural relaxation of EFX called EFk X which requires that no agent envies another agent after the removal of any k goods. Our main contribution is an algorithm that finds a complete (i.e., no good is discarded) EF2X allocation for restricted additive valuations. In our algorithm we devise new concepts, namely configuration and envyelimination that might be of independent interest. We also use our new tools to find an EFX allocation for restricted additive valuations that discards at most n/2 1 goods. |
| Researcher Affiliation | Academia | 1Max Planck Institute for Informatics 2Graduiertenschule Informatik, Universit at des Saarlandes 3 University of Texas at Austin, Computer Science Department 4School of Computer Science, Institute for Research in Fundamental Sciences (IPM), P. O. Box: 19395 5746, Tehran, Iran |
| Pseudocode | Yes | Algorithm 1 Envy-elimination Input : instance (N, M, (v1, . . . , vn)) Output: configuration (X , R )... Algorithm 2 Complete EF2X allocation Input : instance (N, M, (v1, . . . , vn)) Output: allocation X ... Algorithm 3 EFX allocation with n/2 discarded goods Input : instance (N, M, (v1, . . . , vn)) Output: allocation X |
| Open Source Code | No | The paper does not provide concrete access to source code. It is a theoretical paper presenting algorithms and proofs without an implementation for release. |
| Open Datasets | No | The paper does not mention using any specific datasets, public or otherwise, for training or evaluation. This is a theoretical paper. |
| Dataset Splits | No | The paper is theoretical and focuses on algorithm design and proofs, not empirical experiments that would require training, validation, or test splits. Therefore, no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and describes algorithms and proofs, not empirical experiments. Therefore, no hardware specifications for running experiments are provided. |
| Software Dependencies | No | The paper is theoretical and describes algorithms and proofs, not empirical experiments. Therefore, no specific software dependencies with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and describes algorithms and proofs, not empirical experiments. Therefore, no specific experimental setup details like hyperparameters or training configurations are provided. |