Abstract
Schelling's model considers k types of agents each of whom needs to select a vertex on an undirected graph, where every agent prefers neighboring agents of the same type. We are motivated by a recent line of work that studies solutions that are optimal with respect to notions related to the welfare of the agents. We explore the parameterized complexity of computing such solutions. We focus on the well-studied notions of social welfare (WO) and Pareto optimality (PO), alongside the recently proposed notions of group-welfare optimality (GWO) and utility-vector optimality (UVO), both of which lie between WO and PO. Firstly, we focus on the fundamental case where k=2 and there are r red agents and b blue agents. We show that all solution-notions we consider are intractable even when b=1 and that they do not admit an FPT algorithm when parameterized by r and b, unless FPT = W[1]. In addition, we show that WO and GWO remain intractable even on cubic graphs. We complement these negative results with an FPT algorithm parameterized by r, b and the maximum degree of the graph. For the general case with k types of agents, we prove that for any of the notions we consider the problem remains hard when parameterized by k for a large family of graphs that includes trees. We accompany these negative results with an XP algorithm parameterized by k and the treewidth of the graph.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2024 |
| Publisher | International Foundation for Autonomous Agents and Multiagent Systems |
| Pages | 425-433 |
| Number of pages | 9 |
| ISBN (Electronic) | 9798400704864 |
| DOIs | |
| Publication status | Published - 6 May 2024 |
Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver