Convergence and Hardness of Strategic Schelling Segregation

Convergence and Hardness of Strategic Schelling Segregation
复制标题

战略谢林分离的收敛性和硬度

DOI：
10.1007/978-3-030-35389-6_12
复制
发表时间：
2019
期刊：
ArXiv
影响因子：
--
通讯作者：
David Stangl
David Stangl
中科院分区：
--
文献类型：
--
作者：
Hagen Echzell;T. Friedrich;Pascal Lenzner;Louise Molitor;Marcus Pappik;Friedrich Schöne;Fabian Sommer;David Stangl

文献摘要

被引文献

相似文献

居住隔离的现象被谢林的著名隔离模型所捕获，其中两种类型的代理被放置在网格上，如果与她具有相同类型的邻居的比例至少为$\tau$，则代理对她的位置感到满意，大约为$0<\tau<1$。不满的代理人只是交换他们的位置与随机选择的其他不满的代理人或跳转到一个随机的空单元格。 我们分析了广义博弈论模型的谢林隔离，允许两个以上的代理类型和更一般的基础图形建模的住宅区。为此，我们表明，这两个方面严重影响的动态特性和找到一个最佳位置的易处理性。我们绘制了改善响应动态（IRD）时的边界，即，寻找平衡态的自然方法，保证收敛。为此，我们证明了几个尖锐的阈值结果，保证IRD收敛突然变成最强的可能的非收敛结果：违反弱非周期性。特别是，我们也谢林的原始模型，这是在许多实证论文的标准假设相反，这样的阈值结果。此外，我们表明，在收敛的情况下，IRD找到一个平衡在$\mathcal{O}（m）$步骤，其中$m$是在底层图形中的边缘的数量，并表明，这个界限是满足从随机初始代理位置开始的经验模拟。
The phenomenon of residential segregation was captured by Schelling's famous segregation model where two types of agents are placed on a grid and an agent is content with her location if the fraction of her neighbors which have the same type as her is at least $\tau$, for some $0<\tau<1$. Discontent agents simply swap their location with a randomly chosen other discontent agent or jump to a random empty cell. We analyze a generalized game-theoretic model of Schelling segregation which allows more than two agent types and more general underlying graphs modeling the residential area. For this we show that both aspects heavily influence the dynamic properties and the tractability of finding an optimal placement. We map the boundary of when improving response dynamics (IRD), i.e., the natural approach for finding equilibrium states, are guaranteed to converge. For this we prove several sharp threshold results where guaranteed IRD convergence suddenly turns into the strongest possible non-convergence result: a violation of weak acyclicity. In particular, we show such threshold results also for Schelling's original model, which is in contrast to the standard assumption in many empirical papers. Furthermore, we show that in case of convergence, IRD find an equilibrium in $\mathcal{O}(m)$ steps, where $m$ is the number of edges in the underlying graph and show that this bound is met in empirical simulations starting from random initial agent placements.