


Streaming Condorcet Voting: Preference Aggregation with Limited Memory
报告人
Prof. Lirong Xia
Rutgers University-New Brunswick
时间
2026年11月3日 星期二 10:30am
地点
静园五院204室
Host
孔雨晴 长聘副教授
Abstract
Modern computational systems increasingly need to aggregate large amounts of preference data. In a decentralized autonomous organization (DAO), participants may rank thousands of proposals or grants, while storing and processing all raw preferences on-chain can be prohibitively expensive. In reinforcement learning from human feedback (RLHF), large collections of human comparisons or rankings over model outputs must be aggregated and analyzed. These settings motivate a basic algorithmic question: how much working memory is necessary to aggregate preferences and determine a winner?
In this talk, we study this question through Condorcet methods, which aggregate preferences using pairwise comparisons among alternatives. The resulting pairwise information can be represented by a weighted majority graph (WMG): a directed weighted graph recording the margin by which one alternative is preferred to another. This connection turns the problem of preference aggregation under limited memory into two fundamental questions about WMGs: How many different WMGs can be generated by n rankings over m alternatives? And how many rankings are needed to generate an arbitrary WMG?
We obtain an asymptotically tight answer to the first question and substantially improve the known bounds for the second. These results lead to tight one-pass memory bounds for several well-known Condorcet methods, including Copeland, Maximin, Schulze, and Ranked Pairs, as well as algorithms that trade additional passes over the data for less working memory.
The talk is based on joint work with Mario Szegedy and Chengkai Zhang.
Biography
Lirong Xia is a Professor of Computer Science at Rutgers University - New Brunswick and the Deputy Director of DIMACS (the Center for Discrete Mathematics and Theoretical Computer Science). He was a faculty member at RPI and was a CRCS fellow and NSF CI Fellow at the Center for Research on Computation and Society at Harvard University. He received his Ph.D. in Computer Science and M.A. in Economics from Duke University, and B.E. in Computer Science and Technology from Tsinghua University. His research focuses on the intersection of computer science and microeconomics.

往 期 讲 座

静5前沿讲座回顾 | José Correa谈在线算法和剩余先知不等式

— 版权声明 —
本微信公众号所有内容,由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料,版权属北京大学前沿计算研究中心微信所有;从公开渠道收集、整理及授权转载的文字、图片和音视频资料,版权属原作者。本公众号内容原作者如不愿意在本号刊登内容,请及时通知本号,予以删除。

点“阅读原文”查看海报
内容中包含的图片若涉及版权问题,请及时与我们联系删除




评论
沙发等你来抢