论文标题
福利保证Schelling种族隔离
Welfare Guarantees in Schelling Segregation
论文作者
论文摘要
Schelling的模型是一个有影响力的模型，它揭示了个人的看法和激励措施如何导致住宅隔离。受近期工作流的启发，我们研究了该模型的福利保证和复杂性，以实现多种福利措施。首先，我们表明，尽管最大化社会福利是NP-HARD，但可以在多项式时间内将代理分配给任何拓扑图的节点，其中约有一半的最大福利。然后，我们考虑帕累托的最优性，基于它引入两个新的最优性概念，并在最坏的福利损失上建立了满足这些概念的最差福利损失以及计算此类作业的复杂性。此外，我们表明，对于树拓扑，有可能决定是否存在使每个代理在多项式时间内具有正效的作业。此外，当拓扑中的每个节点具有至少$ 2 $的学位时，总是存在这样的作业，并且可以有效地找到。
Schelling's model is an influential model that reveals how individual perceptions and incentives can lead to residential segregation. Inspired by a recent stream of work, we study welfare guarantees and complexity in this model with respect to several welfare measures. 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.
