On Improving Resource Allocations by Sharing
Authors: Robert Bredereck, Andrzej Kaczmarczyk, Junjie Luo, Rolf Niedermeier, Florian Sachse4875-4883
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 treelike (hierarchical) social networks. Our contributions. Introducing a new model for (indivisible) resource allocation with agents linked by social networks, we provide a view on improving existing allocations for several measures without, conceivably impossible, reallocations. We analyze the (parameterized) computational complexity of applying our model to improve utilitarian social welfare or egalitarian social welfare (Definition 4), and to decrease the number of envious agents (Definition 5). |
| Researcher Affiliation | Academia | Humboldt-Universit at zu Berlin, Berlin, Germany 2 Algorithmics and Computational Complexity, TU Berlin, Berlin, Germany 3 AGH University, Krak ow, Poland 4 Nanyang Technological University, Singapore |
| 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 available. It refers to a 'long version of the paper (Bredereck et al. 2021) for several proof details' but not code. |
| Open Datasets | No | The paper is theoretical and does not involve empirical experiments with datasets. Consequently, there is no mention of datasets being publicly available or used for training. |
| Dataset Splits | No | The paper is a theoretical work on algorithms and computational complexity. It does not describe any empirical experiments or the use of dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical, focusing on the design and analysis of algorithms and computational complexity. It does not describe any empirical experiments, and thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is a theoretical work on algorithms and computational complexity. It provides pseudocode but does not describe any specific software dependencies or version numbers required to replicate empirical experiments. |
| Experiment Setup | No | The paper focuses on theoretical analysis and algorithm design. It does not describe any empirical experimental setup, including hyperparameters or system-level training settings. |