北大静园五院前沿讲座邀请罗格斯大学夏立荣教授,围绕流式孔多塞投票做学术分享,核心研究目标就是在内存不够大、偏好数据源源不断流式抵达的场景里,不用存储全部原始投票偏好,依然可以准确完成偏好聚合、找出孔多塞赢家,这项研究打通了经典社会选择理论和流式算法,适合 DAO 链上投票、RLHF 人类偏好排序这类海量偏好数据场景,解决全量存储偏好带来的高昂存储开销问题。
一、讲座基础背景
- 讲座基础信息
- 时间:2026 年 11 月 3 日
- 地点:北大前沿计算研究中心静园五院(静 5)
- 主讲人:罗格斯大学夏立荣教授
- 主持人:孔雨晴副教授
- 合作作者:Mario Szegedy、Zhang Chengkai
- 传统孔多塞投票的痛点
经典孔多塞投票依靠两两对比所有备选项,构建加权多数图 WMG,常规做法是收下全部投票排序之后再统一统计;但大数据场景下,选票是流式陆续到来的,把所有人完整偏好全部存下来,内存成本很高,链上存储甚至会无法落地。
二、核心概念说明
| 名词 | 直白解释 |
|---|---|
| 孔多塞赢家 | 在两两对比里,赢过其他所有选项的备选方案 |
| 流式模型 | 选票一条一条依次输入,数据持续流入,不能等全部数据集齐再计算 |
| 加权多数图 WMG | 记录每两个选项之间谁更受偏好、优势差多少的有向图,是孔多塞类投票的核心数据 |
| 有限内存约束 | 工作内存不跟着投票人数同步膨胀,只保留摘要信息,不存全部原始偏好 |
三、本次研究两大核心问题与结论
- 给定 m 个候选、n 份排序选票,一共能生成多少种不同加权多数图 WMG?研究得到了渐近紧的理论上界。
- 想要构造出任意一张目标加权多数图 WMG,至少需要多少份选票?相比之前学界结果大幅收紧下界。
- 覆盖的主流孔多塞规则
这套理论结论直接给到 Copeland、Maximin、Schulze、Ranked Pairs 四种常用孔多塞投票规则,给出一遍扫描场景下严格内存边界;同时提供取舍方案:多遍历几遍数据,可以进一步降低运行内存占用。
四、典型落地应用场景
- DAO 去中心化自治组织:大量提案投票,链上存储成本昂贵,不适合存全部偏好
- RLHF 人类反馈对齐:大量人类对模型输出做偏好排序,偏好数据体量巨大
- 在线持续收集的调研、群体决策系统,数据持续流入、内存资源受限
五、研究方案使用思路步骤
- 接收流式到来的每一份偏好排序,不保存整张选票,只更新加权多数图的统计摘要;
- 依托理论边界控制摘要占用内存,保证内存不会随投票人数持续暴涨;
- 全部流数据接收完成之后,基于加权多数图摘要,运行 Copeland/Schulze 等规则求解孔多塞赢家;
- 如果内存资源特别紧张,可以选择多次遍历流数据,换取更低的内存开销。
总结
夏立荣教授这次流式孔多塞投票的工作,重点不是修改投票公平规则,而是解决 “海量偏好流、内存不够” 的工程理论难题,给在线群体偏好聚合提供可证明的空间复杂度边界,把孔多塞方法推向大数据、区块链、大模型人类反馈这类高数据量的实际场景。
【常见问题】
问题 1:流式孔多塞投票和普通孔多塞投票最大差别在哪?
回答 1:普通孔多塞投票一般收集完全部选票再统一统计,流式孔多塞投票是选票依次流入,在有限内存里只维护统计摘要,不存储全部原始偏好,适配持续到来的偏好数据流。
问题 2:夏立荣教授本次静 5 讲座里,流式孔多塞投票可以支持哪些投票规则?
回答 2:本次静 5 讲座中夏立荣教授的流式孔多塞投票研究,给出了 Copeland、Maximin、Schulze、Ranked Pairs 这四种主流孔多塞一致规则的一遍扫描内存理论边界。
问题 3:流式孔多塞投票里面的加权多数图 WMG 起到什么作用?
回答 3:在流式孔多塞投票框架里,加权多数图 WMG 用来记录备选项两两之间偏好优势差距,所有偏好聚合、判断孔多塞赢家的计算,都基于这张图的摘要信息完成。
问题 4:流式孔多塞投票适合用在大模型 RLHF 人类偏好收集吗?
回答 4:适合,RLHF 会源源不断产生大量人类偏好排序,刚好符合流式输入特征,流式孔多塞投票依靠有限内存聚合偏好,不用存储全部人类对比记录,降低存储压力。
【参考资料】
[2026-11-17](静 5 前沿讲座回顾 | 夏立荣教授谈流式孔多塞投票:有限内存中的偏好聚合)智源社区
[2026-11-03](Streaming Condorcet Voting: Preference Aggregation with Limited Memory)北京大学前沿计算研究中心讲座页面
[2026-11-03](Streaming Condorcet Voting: Preference Aggregation with Limited Memory)北大 CFCS 讲座摘要文档
【免责声明】
本文是基于北大静 5 前沿讲座公开分享内容整理的科普回顾,流式孔多塞投票属于理论计算机、社会选择交叉方向的前沿学术成果;理论边界、算法性能需要严格数学证明,实际工程落地还需要额外适配场景约束,内容不构成系统实现方案。
