Improving Resource Allocations by Sharing in Pairs
Authors: Robert Bredereck, Andrzej Kaczmarczyk, Junjie Luo, Rolf Niedermeier, Florian Sachse
JAIR 2023 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in pathand tree-like (hierarchical) social networks. |
| Researcher Affiliation | Academia | Robert Bredereck EMAIL Institut f ur Informatik, Algorithm Engineering, Humboldt-Universit at zu Berlin, Berlin, Germany; Institut f ur Informatik, TU Clausthal, Clausthal-Zellerfeld, Germany Andrzej Kaczmarczyk EMAIL AGH University of Krakow, Krak ow, Poland; Faculty IV, Algorithmics and Computational Complexity, Technische Universit at Berlin, Berlin, Germany Junjie Luo EMAIL School of Mathematics and Statistics, Beijing Jiaotong University, Beijing, China Rolf Niedermeier EMAIL Florian Sachse EMAIL Faculty IV, Algorithmics and Computational Complexity, Technische Universit at Berlin, Berlin, Germany |
| Pseudocode | Yes | Algorithm 1: Testing existence of a feasible realization of sharing configuration M for set C of target agents. |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating that open-source code for the described methodology is provided. The acknowledgements refer to a previously published short version of the paper, not a code release. |
| Open Datasets | No | The paper is theoretical and focuses on models and algorithms. It does not describe experiments that would use specific datasets, therefore no information about dataset availability is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments with datasets, thus no information on dataset splits is provided. |
| Hardware Specification | No | The paper describes theoretical models and algorithms and does not report on experimental results that would require hardware specifications. |
| Software Dependencies | No | The paper describes theoretical models and algorithms and does not report on experimental results that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe experiments, therefore no experimental setup details like hyperparameters or training settings are provided. |