AFTD Auto-Formalizing Theoretical Domains

周报 · 2026-W44 · 2026年10月26日至11月1日

社会最优易受联盟破坏、拉丁杨表公式获证与通用谱界被推翻

English

一分钟看本周

博弈论中的一个问题得以解决:研究人员构造出一个182个顶点的反例,推翻了社会最优网络着色总能免于群体背叛的猜想。组合学方面,阶梯形拉丁杨表的精确计数公式获证,且在图块面积仅含两个素因数的情形下排除了完美蒙德里安分割。量子理论方面,一条提出的通用谱界在所有三维及以上维度均被推翻。其他结果还证明了野数公式并给出了新的公平性保证。

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

研究级成果

本周故事

社会最优的网络选择仍可能被串谋破坏

设想一个社交网络中的参与者要在三支队伍中做出选择。每个人都能从对方队伍中的朋友那里获得满足感,这自然会促进整个网络的多样性。当一种队伍划分方案使所有成员之间的跨队友谊总数达到最大时,该方案便达到了社会最优。

如果一个社会实现了一种使总福利最大化的安排,它是否仍可能从内部被瓦解?具体而言,协同一致的一群参与者是否可能商定共同更换队伍,使得串谋中的每个成员最终处境都严格变好?对于这类无权网络博弈,博弈论学者曾猜想,每个网络都至少存在一种能完全免受此类群体背叛的社会最优分配方案。

如今该猜想已被推翻。研究人员构造了一个包含182名参与者的网络,其中任何一种福利最大化的划分方案都会给成功的串谋留下可乘之机。在这个网络中,无论选择哪种社会最优的队伍分配方案,总有一组人可以通过协同更换队伍,让每位串谋者都获得更多身处对方队伍的朋友。

该反例始于一个刚性的91顶点核心,将每位参与者复制为独立的孪生顶点,并附加锚定引脚。这种结构迫使每种最优划分都落入无法消除有利群体背叛的构型。

本周全部结果

  1. 否定

    社会最优割着色未必是强均衡

    在博弈方追求相反颜色的网络博弈中,使割边总数最大化的安排仍可能易受群体背叛的破坏。

  2. 部分结果

    猜想的野数公式对所有大型完全图获证

    在完全图的最优边着色中,连接每个颜色类所需的最小野边数对大型网络达到了其下界。

  3. 否定

    跳跃闭合与跃步闭合边集未能构成拟阵平坦集

    在图置换理论中,若不添加新置换便无法扩充的边子集并不构成任何拟阵的闭集。

  4. 证明

    具双三尾部的拉丁杨表精确计数公式获证

    行长递减且各行各列均无重复数字的网格排列,其精确计数等于9乘以4的幂次方。

  5. 新结果

    双三尾阶梯族中每个拉丁杨表均有四种延拓方式

    在该阶梯族的任一有效网格中添加下一尺寸的新行,总能得到恰好四种有效补全方案。

  6. 证明

    任何整数正方形都不存在双素因数面积的完美矩形密铺

    当公共面积仅有两个素因数时,不可能将正方形分割为面积相等且互不全等的矩形。

  7. 证明

    边长为素数乘素数幂的正方形不存在完美蒙德里安分割

    边长为一个素数乘以任意素数幂的正方形,无法被分割为面积相同且互不相同的矩形。

  8. 证明

    含一个一次因数的三素数公共面积不存在完美分割

    当图块面积涉及三个素数且其中一个为一次方时,将正方形分割为面积相同且互不全等的矩形仍不可能。

  9. 部分结果

    圈图的15次方图的精确等价覆盖数得以确定

    在跨度至多为15的步数均相连的大型圈图中,覆盖所有短距离边恰好需要6个聚类图。

  10. 部分结果

    圈图的7次方图的精确等价覆盖数得以确定

    覆盖环上距离至多为7的顶点间所有边,恰好需要5个等价子图。

  11. 形式化验证

    11面骰子存在长非传递优势循环

    一组11面骰子可以构成至少包含12枚骰子的环路,其中每枚骰子击败下一枚的概率都更高。

  12. 否定

    通用谱界对三维保迹正映射不成立

    关于类量子变换能如何拉伸矩阵迹的一条拟议数学极限,对3乘3矩阵不成立。

  13. 否定

    通用谱界在三维及以上所有维度均不成立

    在大于等于3的每个矩阵维度中,均存在超出拟议通用谱极限的保迹正变换。

  14. 形式化验证

    互信息次可加性在低于黄金比例共轭值时失效

    在信息论中,只要指数严格低于黄金比例共轭值,幂散度的标准次可加性不等式便不再成立。

  15. 证明

    物品数至多为玩家数两倍加1时循环选秀均衡满足EF1

    当各方轮流挑选物品时,只要物品总数不超过玩家人数的两倍加1,每种稳定的博弈结果都满足至多相差一件物品的公平性。

  16. 部分结果

    新增两件全局较小物品仍可保持EFX

    新增两件对所有人而言价值均低于既有物品的新物品,总能在不破坏至多相差任一物品公平性的前提下完成分配。

仍未解决

术语

EF1
至多相差一件物品的无嫉妒:一旦移去某一件物品(被嫉妒者分得的一件好物,或嫉妒者自身分得的一件苦差),嫉妒便消除。
EFX
至多相差任一物品的无嫉妒:无论移去哪一件物品(被嫉妒者分得的任一好物,或嫉妒者自身分得的任一苦差),嫉妒均消除。

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