AFTD Auto-Formalizing Theoretical Domains

周报 · 2026-W43 · 2026年10月19日至25日

轮流选择的极小失效情形、圈幂覆盖界与负数邮票基

English

一分钟看本周

博弈论、数论与图算法领域的若干关键问题得到解决。三人策略性轮流选择在七件物品时被证明满足至多差一件无嫉妒,表明八件物品是出现不公的极小失效点。关于等价图覆盖圈幂的问题,七次幂情形给出了界。新的差值与分类结果确定了允许负面额的三邮票基的性质,并且在线立方伴随式表示方面给出了适用于所有维度的统一构造。

  • 2 证明
  • 2 部分结果
  • 2 新结果
  • 3 形式化验证
  • 5 仍未解决

研究级成果

本周故事

三人策略性轮流选择在至多七件物品时仍保持公平

当三个人从共享池中轮流挑选物品时,他们往往会向前权衡推演,而不是简单地抓取眼前最好的可用物品。经济学家研究由此产生的稳定结果是否仍然保持公平——即从对方分得的物品中移除任意一件后,没有任何人会嫉妒他人。

近年来的研究表明,在有八件物品时,策略性选择确实会打破这种公平性保证;即使扣除竞争对手最好的一件物品,仍有参与者真正产生嫉妒。这留下了一个未决问题:不公是否会在物品更少时出现,还是说八件物品的失效是最早可能出现的故障。

如今的一项完整分析证实,在有三名参与者和七件物品时,每一个稳定结果都满足至多差一件无嫉妒。由于此前已知六件或更少物品的实例均保持公平,因此八件物品恰好是策略性轮流选择可能产生不公分配的确切阈值。

本周全部结果

  1. 证明

    三名参与者与七件物品下轮换选择的纯纳什均衡满足EF1

    当三人轮流挑选至多七件物品时,每个稳定的策略性结果在移去一件物品后都不会让任何人产生嫉妒。

  2. 形式化验证

    三名参与者与八件物品下轮换选择的纯纳什均衡可不满足EF1

    当三人从八件物品中轮流挑选时,其策略性选择可能导致移去一件物品后仍有人感到嫉妒的结果。

  3. 证明

    线立方伴随式具有2n加1个支承的奇偶表示

    一个特定的量子门化简问题总能使用与输入规模成正比的确定数量的组件来求解。

  4. 新结果

    允许负数的三邮票基产生单位差值当且仅当h模12余9

    在允许负数的三邮票组合中,恰在邮票预算模十二余九时,所达到的范围比经典最大值恰好少一。

  5. 新结果

    在h = 419时允许负数的三邮票数比最大值至少小六

    在419张邮票的预算下,允许负值会导致数值减少至少六个整数,推翻了此前猜想的差值四。

  6. 形式化验证

    三维盒体达文波特常数的三次下界确立

    三维盒体中极小零和序列的最大长度随盒体半径呈三次增长。

  7. 部分结果

    当八不整除n时七次圈幂至少需要五个等价子图

    除非网络规模能被八整除,否则覆盖跨度为七的环形网络中的所有连接至少需要五个简单聚类图。

  8. 部分结果

    K_279的每个极小正常边着色的荒野数均为186

    279个节点的完全网络的每个最高效边着色都可以恰好使用186条边连接所有颜色。

  9. 形式化验证

    顶点度数加初始正权重界内存在加法着色

    每个图都可以赋予正数,使得相邻顶点具有不同的邻点和,且不超过每个顶点的度数加初始权重。

仍未解决

术语

EF1
至多差一件无嫉妒:一旦移去某单件物品(从被嫉妒者分得的物品中移去一件好物品,或从嫉妒者自身分得的物品中移去一件苦差),任何嫉妒便会消除。

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