AFTD Auto-Formalizing Theoretical Domains

周报 · 2026-W40 · 2026年9月28日至10月4日

投票博弈的刚性、说服常数以及策略性停止规则的局限

English

一分钟看本周

本周解决了博弈论、公平分配和投票领域的多个问题。在投票博弈中,证明了关键投票表能唯一确定加权系统。在贝叶斯说服中,接收者的最优效用比被确定为3/2。在家务分配中,双人公平分配的最坏情况成本被证明严格低于二分之一。在策略博弈中,发表选择问题的均衡唯一性被推翻,静态停止规则在伪装奖励下也无法保持稳健。离散公平性标准之间的四项未决推导关系也得以解决。

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

本周故事

加权投票博弈可由其关键投票表完全确定

在通过法案需要成员投出加权选票的投票委员会中,衡量政治权力的标准指标并不直接考察权重。相反,它们记录的是关键投票:成员将败选联盟转变为胜选联盟的频次。

这引出了一个自然的问题:两个本质上不同的加权投票系统,在所有标准权力指标下是否可能完全相同?此前有猜想认为这是不可能的,在所有简单投票博弈中,加权投票博弈可由其关键投票表唯一确定。

该猜想现已获证。任何加权投票系统都完全由每位投票者在各个联盟规模下所拥有的关键投票次数决定。

该证明将关键投票计数与经典阈值逻辑联系起来。将所有投票者的关键投票数相加,可以重构出各个规模下获胜联盟的总数。将其与个人的关键投票数相结合,便能复原包含每位投票者的获胜联盟的精确数量。1961年关于阈值函数的一项经典定理随后保证了这些计数能唯一确定加权规则。

本周全部结果

  1. 证明

    加权投票博弈由其关键投票表唯一确定

    获知每位投票者将败选联盟转变为胜选联盟的频次,便能唯一确定任何加权投票规则。

  2. 部分结果

    严格多数决下的班扎夫否决权失真至少为5/3

    权力指标对权重的失真程度,足以在严格多数决下赋予意料之外的否决权。

  3. 证明

    比特串说服中的接收者效用常数为3/2

    接收者从发送者的建议中最多只能获得其初始效用的3/2倍。

  4. 否定

    策略性奖励信号传递下静态阈值无法达到1/2稳健性

    当参与者策略性地伪装奖励时,固定阈值无法保证获得最优奖励的一半。

  5. 证明

    存在防女巫攻击、安全且无赢者通吃均衡的采购机制

    免受虚假身份影响的拍卖可以安全地在多个供应商之间分担工作且不产生亏损。

  6. 否定

    缺乏凸风险敞口时拟算术汇聚评分可能不满足凹性

    当评分规则缺乏曲率时,对专家预测进行平均可能无法保证凹性。

  7. 否定

    可加物品下MXS不蕴涵EEF1

    公平划分份额无法防止在移除一件物品后仍存在强烈嫉妒。

  8. 否定

    APS不蕴涵PROP1且成对MMS不蕴涵MMS

    定价或成对公平份额可能无法满足标准的比例性或群体公平性。

  9. 证明

    次模估值下MXS蕴涵PROP1

    公平划分份额可确保没有任何人觉得自己的亏损超过一件物品。

  10. 否定

    两人分担家务时EF1的成本严格低于1/2

    两人之间的公平家务分配使总成本增加最多3 − 2√2 ≈ 0.172。

  11. 部分结果

    多重图的无嫉妒定向所需补贴超过n − 2

    当节点间存在多条连接时,公平地为共享网络链路定向需要更多的现金补贴。

  12. 否定

    连通的家务EF1分配可能不满足帕累托最优

    沿一条线至多差一项任务地公平划分家务,可能会导致付出徒劳的努力。

  13. 部分结果

    家务分配中加权PROPX与帕累托最优在接近均等份额时发生冲突

    按照目标份额公平分配家务在接近均等份额时无法避免效率损失。

  14. 部分结果

    出度至多为2的图存在PROPm定向

    当链路能够以低出度进行定向时,网络资源可以得到公平共享。

  15. 证明

    字典序极大极小最优的EF1分配可能不满足帕累托最优

    在近似无嫉妒的方案中挑选最公平的分配,可能会产生无效率的结果。

  16. 否定

    论文发表选择问题可能存在多个纯策略均衡

    当研究人员策略性地选择投稿期刊时,可能会存在多个稳定结果。

  17. 证明

    门罗投票规则满足德鲁普比例代表制公理

    经典委员会投票规则保证了有凝聚力的选民群体获得公平代表权。

  18. 否定

    时序投票中Droop-FJR不蕴涵BFJR

    每一轮中的公平代表权并不能保证跨时间的均衡代表权。

  19. 证明

    几何普拉凯特-卢斯选择模型具有线性熵

    在几何偏好下,排名的随机性随候选人数量仅呈线性增长。

  20. 证明

    配额与人口单调性在同一议席规模下发生冲突

    公平的立法席位分配无法在符合人口份额的同时避免悖论。

  21. 部分结果

    空壳市场至多有⌊(n−1)²/4⌋个阻塞对

    偏好冲突的环形婚姻市场至多产生二次方数量的不稳定配对。

  22. 否定

    获知3名参与者信息时延迟接受算法可被安全操纵

    在匹配市场中,获知其他3人偏好的参与者可以安全地作弊。

  23. 部分结果

    素数幂长度的弱连续序列以1开头或结尾

    具有重复整除模式的排列在长度为素数幂时必须将1置于端点。

  24. 形式化验证

    N至多为11时的追赶博弈平局及奇偶性定理完成形式化验证

    检验了确定交替领先数字博弈何时以平局结束的计算。

仍未解决

术语

APS
任意价格份额:参与者在总和为1的任意价格向量下,购买其应得权益内的任意物品束所能保证获得的价值。
BFJR
BFJR:一种时序代表制公理,强于Droop-FJR。
EEF1
认知无嫉妒至多差一件物品:对每位参与者而言,其未持有的物品可以在其他人之间重新分配,使得该参与者对所有人均满足EF1。
EF1
无嫉妒至多差一件物品:一旦移除某个单件物品(从被嫉妒者的物品束中移除一件好物品,或从嫉妒者自己的物品束中移除一件家务),任何嫉妒都会消除。
FJR
完全合理代表性:扩展合理代表性(EJR)的强化版本,适用于仅部分达成一致的选民群体,要求每位成员都赞同候选人公共集合中的足够多候选人。
MMS
极大极小份额:参与者将所有物品划分为n个物品束并获得其中最差的一个时,所能保证获得的最好价值。
MXS
最小EFX份额:参与者在对其他所有参与者均满足EFX的任意分配中所获得的最小价值。
PROP1
比例性至多差一件物品:一旦向参与者的物品束中添加单件物品(好物品)或从中移除单件物品(家务),比例性即成立。
PROPm
比例性至多差极大极小物品:参与者的物品束加上其他参与者物品束中最无价值物品中的最大者,能够达到其比例份额。
PROPX
比例性至多差任意物品:在家务分配中,从参与者的物品束中移除任意单件家务,即可使其成本降至比例份额以内。

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