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游戏中的互换平衡游戏的稳健性方面,我们得到了更低和上层的严格限制。

0
下载
关闭预览

相关内容

CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点,具有清晰的数学轮廓和严格的数学格式。官网链接:https://link.springer.com/journal/37
专知会员服务
91+阅读 · 2021年6月3日
专知会员服务
37+阅读 · 2021年4月27日
专知会员服务
22+阅读 · 2021年4月10日
【干货书】Linux命令行与shell脚本编程大全,第3版818页pdf
专知会员服务
61+阅读 · 2020年12月30日
专知会员服务
50+阅读 · 2020年12月14日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
70+阅读 · 2020年8月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
revelation of MONet
CreateAMind
5+阅读 · 2019年6月8日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年7月12日
Arxiv
0+阅读 · 2021年7月12日
VIP会员
相关VIP内容
专知会员服务
91+阅读 · 2021年6月3日
专知会员服务
37+阅读 · 2021年4月27日
专知会员服务
22+阅读 · 2021年4月10日
【干货书】Linux命令行与shell脚本编程大全,第3版818页pdf
专知会员服务
61+阅读 · 2020年12月30日
专知会员服务
50+阅读 · 2020年12月14日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
70+阅读 · 2020年8月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
相关资讯
revelation of MONet
CreateAMind
5+阅读 · 2019年6月8日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员