Streaming Condorcet Voting: Preference Aggregation with Limited Memory

Date & Time

Date: Thursday, Sep 24, 2026

Time: 11:30 AM – 12:30 PM

Venue: IB 1012

Speaker

Dr. Lirong Xia

Professor of Computer Science, Rutgers University – New Brunswick 

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. Along the way, we will encounter ideas from combinatorics, probability, geometry, streaming algorithms, and communication complexity. The talk will focus on the main questions and mathematical ideas and should be accessible to audience with a basic background in discrete mathematics or algorithms.

The talk is based on joint work with Mario Szegedy and Chengkai Zhang.

Bio:

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. He has served on the editorial board of Artificial Intelligence Journal (AIJ), Journal of Artificial Intelligence Research (JAIR), Transactions on Machine Learning Research (TMLR), IEEE Transactions on artificial intelligence (TAI), and Mathematical Social Sciences (MSS). He is the recipient of an NSF CAREER award, a Simons-Berkeley Research Fellowship, and was named as one of “AI’s 10 to watch” by IEEE Intelligent Systems.