Weighted Envy-Freeness for Submodular Valuations
Authors: Luisa Montanari, Ulrike Schmidt-Kraepelin, Warut Suksompong, Nicholas Teh
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate the fair allocation of indivisible goods to agents with possibly different entitlements represented by weights. Previous work has shown that guarantees for additive valuations with existing envy-based notions cannot be extended to the case where agents have matroid-rank (i.e., binary submodular) valuations. We propose two families of envy-based notions for matroid-rank and general submodular valuations, one based on the idea of transferability and the other on marginal values. We show that our notions can be satisfied via generalizations of rules such as picking sequences and maximum weighted Nash welfare. In addition, we introduce welfare measures based on harmonic numbers, and show that variants of maximum weighted harmonic welfare offer stronger fairness guarantees than maximum weighted Nash welfare under matroid-rank valuations. |
| Researcher Affiliation | Academia | 1Technische Universit at Berlin, Germany 2TU Eindhoven, The Netherlands 3National University of Singapore, Singapore 4University of Oxford, UK |
| Pseudocode | Yes | Algorithm 1: For finding a clean TWEF(x, 1 x) allocation maximizing P i N vi(Ai) |
| Open Source Code | No | The paper does not contain any explicit statement about providing open-source code for the described methodology or a link to a code repository. |
| Open Datasets | No | The paper is theoretical and does not involve empirical experiments with datasets for training or evaluation. |
| Dataset Splits | No | The paper focuses on theoretical analysis and does not involve empirical experiments requiring validation dataset splits. |
| Hardware Specification | No | The paper describes theoretical concepts, algorithms, and proofs, and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe software dependencies with version numbers for empirical reproduction. |
| Experiment Setup | No | The paper describes theoretical algorithms and their properties, rather than empirical experimental setups with hyperparameters or training configurations. |