Schelling's model is an influential model that reveals how individual perceptions and incentives can lead to racial 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 with approximately half of the maximum welfare can be done in polynomial time. We then consider Pareto optimality and introduce two new optimality notions, and establish mostly tight bounds on the worst-case welfare loss for assignments satisfying these notions. In addition, we show that for trees, 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.


翻译:Schelling的模型是一个具有影响力的模式,它揭示了个人观点和激励因素如何导致种族隔离。在近期工作流的启发下,我们研究了福利保障和这一模式中若干福利措施的复杂性。首先,我们表明,在尽量扩大社会福利的同时,PN-硬体化,计算一项拥有大约一半最大福利的派任可以在多民族时期完成。然后,我们考虑Pareto最佳性,引入两个新的最佳性理念,并对满足这些理念的派任的最坏情况的福利损失规定大致严格的界限。 此外,我们表明,对于树木,我们有可能确定是否有一项任务在多民族时期给每个代理带来积极效用;此外,当每个顶层的节点至少具有2美元的水平时,这种派任总是存在,并且能够有效找到。

0
下载
关闭预览

相关内容

Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
104+阅读 · 2020年5月15日
专知会员服务
157+阅读 · 2020年1月16日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
76+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
89+阅读 · 2019年10月10日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
已删除
将门创投
11+阅读 · 2019年4月26日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年1月22日
Arxiv
0+阅读 · 2021年1月21日
Arxiv
0+阅读 · 2021年1月20日
VIP会员
相关资讯
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
已删除
将门创投
11+阅读 · 2019年4月26日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员