AFTD Auto-Formalizing Theoretical Domains

周报 · 2026-W45 · 2026年11月2日至8日

无权网络博弈可无限循环、有向半覆盖成立与三值零和问题获解

English

一分钟看本周

本周解决了网络博弈、有向图、公平资源分配与加性组合学中的若干未决问题。一个显式网络博弈证明,即使没有边权且偏离联盟极小,参与者也能通过有利移动无限循环。在图论中,确立了非邻域含核的有向图的半邻域覆盖,并否定了次三次网络聚类划分界的一个猜想。其他获解问题包括三维零和向量序列的精确阈值,以及两人间分配不可分家务的更优保证。

  • 4 证明
  • 1 否定
  • 3 部分结果
  • 8 形式化验证
  • 5 仍未解决

研究级成果

本周故事

偏离联盟极小时着色博弈仍可无限循环

想象网络中的参与者各自选择3种颜色之一,试图与邻居颜色不同。若一组参与者的每位成员都能严格增加其异色邻居得分,该组便可协调同时改变颜色。

当单个个体切换颜色时,网络总得分会上升,从而保证博弈最终一定会停止。但协同群体是否可能无限循环?以往的循环构造都需要带权连接。当偏离被限制在不包含更小获利子群体的极小联盟时,无权网络是否能循环此前悬而未决。

一项新构造证明,在极小群体偏离下,无权网络也能无限循环。在一个具体的71顶点网络上,33个连续着色构成了一个无限循环。循环始于32名核心参与者在单次协同移动中同时变色,且没有任何子群体能单独做到这一点。随后32次单人调整每次一人逐步恢复原始着色,从而排除了存在任何势函数的可能。

本周全部结果

  1. 证明

    无权网络割博弈允许极小联盟偏离的无休止循环

    在博弈者选色以求与邻居不同的网络博弈中,即便没有任何子群体能单独获利,团队仍可通过变色无限循环。

  2. 证明

    无权三色网络割博弈存在循环联盟偏离

    即使没有边权,网络着色博弈中的参与者也可以通过群体变色无限循环。

  3. 证明

    九顶点割博弈中公平性与联盟稳定性不可兼得

    在9人着色博弈中,个体稳定性可保证每人至少得4分,但群体稳定性会迫使至少一人得分低于4分。

  4. 形式化验证

    历史感知修复打破近似均衡的单参与者扩展壁垒

    在多人博弈中,近似均衡可以通过显式的混合界扩展至新加入的一名参与者。

  5. 证明

    非邻域核保证有向图中的加权半邻域覆盖

    在每个非邻接点集都含有核的网络中,总能找到一个覆盖任意给定正权重至少一半的小枢纽。

  6. 否定

    莫比乌斯阶梯否定次三次图的分支阶划分猜想

    并非总能将每个节点至多3条连边的网络划分为一个分散群体和若干至多3个节点的小聚类。

  7. 部分结果

    显式有向图表明出度为4时的局部扩张比至少为5/4

    一个24顶点的定向网络表明,删除闭邻域可使源点数量的扩张超出出度界的限制。

  8. 形式化验证

    直径为3的坚果图邻接行空间存在非行二元向量

    在每个节点都参与零空间的特定图中,距离为3的各点行向量之和构成了一个新的0-1向量。

  9. 部分结果

    三维三值空间中极小零和序列长度等于13

    任意由13个模3数构成的3维非零向量列表中,必包含模3和为零但模9和不为零的子列表。

  10. 形式化验证

    单层集族的层数确立二项式与线性上界

    每层互不相交的集合族,其规模界限可同时由线性公式与对数二项式系数给出。

  11. 形式化验证

    10点构型在莫德尔距离乘积上超越带中心正九边形

    平面上的10个点可经排列使其两两距离之积严格超过正多边形保持已久的基准。

  12. 部分结果

    等边际下两人家务分配达到精确的(r+1)/2最大最小份额

    两人分担成本比为r的2值家务时,可在2种分配方案间抛硬币,以保证至多为公平份额(r+1)/2倍的成本。

  13. 形式化验证

    同序家务实例满足1/3与4/3成本界

    当所有人对家务难度的排序达成一致时,配对后剩余的家务成本至多为公平份额的1/3。

  14. 形式化验证

    2×2矩阵的有死性归约为直线可达性

    判定一组2×2矩阵相乘能否得到零矩阵,等价于询问是否存在某个矩阵序列将一条直线映射到另一条直线。

  15. 形式化验证

    主导资源公平性(DRF)的竞争比至少为1加上资源数的平方根

    在多任务共享多种资源的系统中,任何基于主导份额的调度策略其最坏情况延迟因子都随资源数的平方根增长。

  16. 形式化验证

    d²个测量组成的族全局不相容但在每个子空间上可联合测量

    在d维空间中,一组d²个简单测量可能整体上无法同时测量,但在限制到任何更小子空间时完全兼容。

仍未解决

术语

DRF
DRF:主导资源公平性,一种多资源分配策略,旨在使分配给各竞争用户的主导资源份额相等

本文由模型(gemini-3.8-flash)根据本期经 Lean 验证的结果撰写,并从英文版翻译而来。文中提到的每个定理都经过 Lean 检查;本摘要只是阅读辅助,本身未经机器检查。