论文标题
福利的参数复杂性保证了Schelling隔离
The Parameterized Complexity of Welfare Guarantees in Schelling Segregation
论文作者
论文摘要
Schelling的模型考虑了$ K $类型的代理，每个代理需要在无向图上选择顶点，每个代理都喜欢相同类型的邻居代理。我们的动机是最近的一项工作，该工作研究解决了与代理人福利相关的概念最佳的解决方案。我们探索了计算此类解决方案的参数化复杂性。我们专注于社会福利（WO）和Pareto最优性的良好概念（PO），以及最近提出的集体福利最优性（GWO）和公用事业 - 武器最优性（UVO）的概念，它们都位于WO和PO之间。首先，我们专注于$ k = 2 $的基本情况，并且有$ r $ $ $红色代理商和$ b $蓝色代理商。我们表明，我们考虑的所有解决方案通知都是$ \ textsf {np} $ - 即使$ b = 1 $，也很难计算，并且它们是$ \ textsf {w} [1] $ - 当通过$ r $和$ b $参数化时，很难。此外，我们证明WO和GWO是$ \ textsf {np} $ - 即使在立方图上也很难。我们通过$ r，b $和图表的最高度对这些负面结果进行补充这些负面结果。对于具有$ k $类型的代理商的一般情况，我们证明，对于任何一个概念，我们认为问题是$ \ textsf {w} [1] $ - 当通过$ k $参数化的大型图形家庭时，很难。我们以$ \ textsf {xp} $算法为$ k $和图表的树宽参数commintsf {xp} $算法伴随着这些负面结果。
Schelling's model considers $k$ types of agents each of whom needs to select a vertex on an undirected graph, where every agent prefers to neighbor 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 $\textsf{NP}$-hard to compute even when $b=1$ and that they are $\textsf{W}[1]$-hard when parameterized by $r$ and $b$. In addition, we show that WO and GWO are $\textsf{NP}$-hard even on cubic graphs. We complement these negative results by an $\textsf{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 is $\textsf{W}[1]$-hard when parameterized by $k$ for a large family of graphs that includes trees. We accompany these negative results with an $\textsf{XP}$ algorithm parameterized by $k$ and the treewidth of the graph.
