In the simplest game-theoretic formulation of Schelling's model of segregation on graphs, agents of two different types each select their own vertex in a given graph such as to maximize the fraction of agents of their type in their occupied neighborhood. Two ways of modeling agent movement here are either to allow two agents to swap their vertices or to allow an agent to jump to a free vertex. The contributions of this paper are twofold. First, we prove that deciding the existence of a swap-equilibrium and a jump-equilibrium in this simplest model of Schelling games is NP-hard, thereby answering questions left open by Agarwal et al. [AAAI '20] and Elkind et al. [IJCAI '19]. Second, we introduce a measure for the robustness of equilibria in Schelling games in terms of the minimum number of edges that need to be deleted to make an equilibrium unstable. We prove tight lower and upper bounds on the robustness of swap-equilibria in Schelling games on different graph classes.
翻译:在Schelling的图形隔离模型的最简单的游戏理论配方中,两种不同类型的代理人在一张特定图表中选择自己的顶点,例如最大限度地增加其类型在被占领社区中的代理人的分数。两个模拟代理人移动的方式是允许两个代理人交换他们的头顶或允许一个代理人跳跃到一个自由的顶点。本文的贡献是双重的。首先,我们证明在这种最简单的Schelling游戏模型中决定是否存在互换平衡和跳平衡是NP硬的,从而回答Agarwal等人[AAI'20]和Elkind等人(IJCAI'19])留下的开放问题。第二,我们引入了一种衡量标准,以Schelling游戏中需要删除的最起码数量的边缘来保持平衡的不稳定性。我们证明,在Schellelling游戏中的互换平衡游戏的稳健性方面,我们得到了更低和上层的严格限制。