We study the max k-cut game on an undirected and unweighted graph in order to find out whether an optimal solution is also a strong equilibrium. While we do fail to show that, by proving an alternate formula for computing the cut value difference for a strong deviation, we show that optimal solutions are 7-stable equilibria. Furthermore, we prove some properties of minimal subsets with respect to a strong deviation, showing that each of their nodes will deviate towards the color of one of their neighbors and that those subsets induce connected subgraphs.


翻译:我们用一个未定向且未加权的图表来研究最大 K- cut 游戏, 以便找出最佳解决方案是否也是强烈的平衡。 虽然我们没有证明, 通过证明计算切分差的替代公式, 以获得强烈偏差, 我们证明最佳的解决方案是 7 个稳定的平衡。 此外, 我们证明, 与强烈偏差相比, 最小子集的一些特性, 表明每个节点会偏离其邻居的颜色, 而这些节点会诱发连接子集 。

0
下载
关闭预览

相关内容

【ICLR2021】彩色化变换器,Colorization Transformer
专知会员服务
9+阅读 · 2021年2月9日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
110+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
最佳实践:深度学习用于自然语言处理(三)
待字闺中
3+阅读 · 2017年8月20日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年9月18日
Arxiv
0+阅读 · 2021年9月11日
VIP会员
相关资讯
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
最佳实践:深度学习用于自然语言处理(三)
待字闺中
3+阅读 · 2017年8月20日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员