本周故事
偏离联盟极小时着色博弈仍可无限循环
想象网络中的参与者各自选择3种颜色之一,试图与邻居颜色不同。若一组参与者的每位成员都能严格增加其异色邻居得分,该组便可协调同时改变颜色。
当单个个体切换颜色时,网络总得分会上升,从而保证博弈最终一定会停止。但协同群体是否可能无限循环?以往的循环构造都需要带权连接。当偏离被限制在不包含更小获利子群体的极小联盟时,无权网络是否能循环此前悬而未决。
一项新构造证明,在极小群体偏离下,无权网络也能无限循环。在一个具体的71顶点网络上,33个连续着色构成了一个无限循环。循环始于32名核心参与者在单次协同移动中同时变色,且没有任何子群体能单独做到这一点。随后32次单人调整每次一人逐步恢复原始着色,从而排除了存在任何势函数的可能。