Welfare Guarantees in Schelling Segregation
Authors: Martin Bullinger, Warut Suksompong, Alexandros A. Voudouris
JAIR 2021 | Venue 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 of agents to the nodes of any topology graph with approximately half of the maximum welfare can be done in polynomial time. We then consider Pareto optimality, introduce two new optimality notions based on it, and establish mostly tight bounds on the worst-case welfare loss for assignments satisfying these notions as well as the complexity of computing such assignments. In addition, we show that for tree topologies, 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 | Martin Bullinger EMAIL Institut f ur Informatik Technische Universit at M unchen Boltzmannstr. 3, 85748 Garching, Germany Warut Suksompong EMAIL School of Computing National University of Singapore 13 Computing Drive, Singapore 117417, Singapore Alexandros A. Voudouris EMAIL School of Computer Science and Electronic Engineering University of Essex Wivenhoe Park, Colchester CO4 3SQ, United Kingdom |
| Pseudocode | Yes | Algorithm 1 Assignment with high social welfare |
| Open Source Code | No | The paper does not contain any explicit statement about providing open-source code for the methodology described, nor does it provide a direct link to a code repository. |
| Open Datasets | No | The paper focuses on theoretical analysis of Schelling's model and does not use or reference any specific empirical datasets for evaluation. Therefore, no information about open datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation on datasets, thus there is no mention of dataset splits. |
| Hardware Specification | No | The paper is theoretical in nature, focusing on algorithms, complexity, and welfare guarantees. It does not describe any experimental setup involving specific hardware. |
| Software Dependencies | No | The paper is theoretical and focuses on mathematical proofs and algorithmic design. It does not mention any specific software packages, libraries, or their versions used for implementation or experimentation. |
| Experiment Setup | No | The paper is theoretical, presenting proofs and algorithms related to Schelling's model. It does not describe any empirical experimental setup, hyperparameters, or training configurations. |