Streaming Condorcet Voting: Preference Aggregation with Limited Memory
- Prof. Lirong Xia, Rutgers University-New Brunswick
- Time: 2026-11-03 10:30
- Host: Prof. Yuqing Kong
- Venue: Room 204, Courtyard No.5, Jingyuan
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.