AFTD Auto-Formalizing Theoretical Domains

周报 · 2026-W41 · 2026年10月5日至11日

家务分配的两两公平界限、偏序集精确查询复杂度与被否定的猜想

English

一分钟看本周

公平分配领域解决了若干公开问题:一般情况下三人之间依据两两份额公平分配家务是不可能的,两人最大化效用乘积的精确福利保证得以确定,一个图连通性猜想被推翻。在算法领域,在双链偏序集中寻找极小元被证明需要严格多于先前猜想的比较次数。在机制设计中,反例否定了带缩放设施选址问题的独裁猜想,并推翻了委托代理与匹配竞赛中两项已发表的论断。

  • 6 证明
  • 5 否定
  • 5 部分结果
  • 5 仍未解决

本周故事

家务并不总能在三人之间公平分配

假设三名室友需要分担九项令人不快的家务。每个人对每项任务都承受正的成本,任何人的总负担就是分配给自己的各项家务成本之和。

一个自然的公平基准是两两最大最小份额保证。在该标准下,任何人在将自己的家务与另一名室友对比时,都应当觉得两人之间的划分是公平的:如果将分配给他们两人的所有家务合并并分成两堆,自己那一堆的负担不应重于两堆中更差的一堆。家务是否总能这样分配,使得每个人相对于其他任何人都满足这一两两公平检验?

并不能。对于三个人和特定的九项家务,没有任何家务分配能对每个人都满足该保证。在只有两人时,这样的公平分配总是可行的,这使得三人成为公平性可能破裂的最小人数。该结果通过评估全部 3^9 种可能的家务分配,并验证每种分配都至少让一人分得不公平的份额来完成核验。

本周全部结果

  1. 证明

    三人主体分担家务时可能不存在 PMMS 分配

    平分家务使得任何两人将各自家务合并分成两堆后都不嫉妒对方,有时对三人而言是不可能的。

  2. 证明

    两人主体的最大纳什福利代价等于 27/23

    两人分配物品时,选择使各自价值乘积最大化的方案,可保证达到可能最优总价值的已知比例。

  3. 否定

    关于两人连通性代价的图链接度猜想不成立

    一项基于图连通性性质预测网络连通部分能如何公平划分的猜想,在一个八节点网络上失效。

  4. 部分结果

    各天相同情形下时序 EFX 的近似比不能超过 1/√2

    在跨多天且每天价值相同的情况下公平分配物品时,任何分配都无法保证超过标准公平基准的某一特定比例。

  5. 证明

    两人单调最大最小份额的阈值恰为三件物品

    两人对物品具有一般偏好价值时,若至多有三件物品总能获得各自的公平份额,但四件物品时则不然。

  6. 否定

    宽度为 2 的偏序集极小元确定性查询复杂度为 2n − 3

    在沿两条平行链偏序排列的物品集合中寻找极小元,所需的比较次数严格多于先前的猜想。

  7. 否定

    比赛对抗中最佳团队出场阵容的上限公式不成立

    一项已发表的用于限制教练通过调整队员出场顺序能提高多少胜率的公式,即使在简单比赛中也不成立。

  8. 否定

    缩放函数已知时带缩放设施选址的独裁猜想不成立

    在成本呈非线性缩放的直线上放置共享设施时,存在既公平又防操纵且不赋予单个人完全控制权的规则。

  9. 否定

    广义委托代理硬度证明中的凹化恒等式不成立

    用于证明最优合同设计难以近似的一个数学等式并不成立,需要为该近似比提供新的论证。

  10. 部分结果

    策略数至多为 4 的匿名博弈纯近似均衡界限得以确定

    在博弈方仅关心有多少其他人做出各种选择的大型博弈中,当可选策略较少时,保证稳定结果所需的误差已被求出。

  11. 部分结果

    小图上最大 k-割博弈的最优染色构成强均衡

    当博弈方通过选择颜色来最大化异色邻居时,在至多六个节点的图中,社会最优结果不会被协同结盟的群体破坏。

  12. 部分结果

    林-陆-丘正曲率边连通度阈值公式在三个顶点时不成立

    一项为保证所有边均具有正几何曲率所需的网络连接强度公式,在一个简单的三节点图上失效。

  13. 证明

    四顶点及以上图的局部平均支配集阶数严格低于 (5n−1)/6

    对于任何至少有四个节点且无孤立节点的网络,包含任意给定节点的支配节点集的平均大小严格低于已知界限。

  14. 证明

    长度为 8、9 和 10 的圈存在完全圈标号

    1 到 8 的数字可以排列在一个八节点环上,使得所有可能的子段和都能实现。

  15. 证明

    杜鲁普-门罗投票规则满足杜鲁普合理代表性

    一种标准的委员会投票规则能够保证,任何就某候选人达成一致的足够大的选民群体,至少能让一名获认可的候选人当选。

  16. 部分结果

    四名候选人选举的孔多塞维度至多为 3

    在至多四名候选人的任何选举中,总存在一个至多三名候选人的小子集,其无法被外部任何人击败。

仍未解决

术语

EFX
至多差一件物品无嫉妒:无论拿走哪一件物品(被嫉妒者的任意物品,或嫉妒者自身的任意家务),嫉妒都会消除。
PMMS
两两最大最小份额:对于任意两名主体,将两人合并的物品重新分成两堆,都无法让其中任何一人获得更好的较差堆。

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