Welfare Guarantees in Schelling Segregation
Authors: Martin Bullinger, Warut Suksompong, Alexandros A. Voudouris5236-5243
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | First, we show that while maximizing the social welfare is NP-hard, computing an assignment with approximately half of the maximum welfare can be done in polynomial time. We then consider Pareto optimality and introduce two new optimality notions, and establish mostly tight bounds on the worst-case welfare loss for assignments satisfying these notions. In addition, we show that for trees, it is possible to decide whether there exists an assignment that gives every agent a positive utility in polynomial time; moreover, when every node in the topology has degree at least 2, such an assignment always exists and can be found efficiently. |
| Researcher Affiliation | Academia | 1 Institut f ur Informatik, Technische Universit at M unchen 2 School of Computing, National University of Singapore 3 School of Computer Science and Electronic Engineering, University of Essex |
| Pseudocode | Yes | Algorithm 1 Assignment with high social welfare |
| Open Source Code | No | The paper is theoretical and focuses on proofs and algorithmic design. It does not mention releasing open-source code for the methodologies described, nor does it provide any links to a code repository. |
| Open Datasets | No | This paper is theoretical and does not involve experimental evaluation using datasets, so there is no mention of training data availability. |
| Dataset Splits | No | This paper is theoretical and does not involve experimental evaluation using datasets, so there is no mention of dataset splits (train/validation/test). |
| Hardware Specification | No | This is a theoretical paper. It does not describe any experimental setups that would require specific hardware, and therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | This is a theoretical paper that focuses on proofs and algorithmic properties. It does not involve software implementations or experimental setups that would require specific software dependencies or versions. |
| Experiment Setup | No | This is a theoretical paper and does not describe empirical experiments, thus no experimental setup details like hyperparameters or training settings are provided. |