Aggregating Preferences with Limited Queries

Title: Aggregating Preferences with Limited Queries

Abstract: Social choice theory studies how to aggregate individual preferences into a single collective decision. Traditionally, this assumes complete access to each individual’s complete preferences. However, in a variety of settings, this assumption does not hold. For example, modern online platforms promoting civic participation, such as Pol.is, aggregate complex preferences over a vast space of alternatives, rendering it infeasible to learn any individual's preferences completely. Instead, preferences are elicited by asking each user a query about a small subset of their preferences.

In this talk, I will present a simple framework for analyzing what social choice guarantees are possible in these setups, where preferences can only be elicited via small queries. It covers two recent papers:
EC’24 paper on ranking-based preferences: https://arxiv.org/abs/2402.11104
AAAI’23 paper on approval-based preferences: https://arxiv.org/abs/2211.15608
Contributions include: 
- Positive algorithmic results: Efficient algorithms that produce representative outcomes with limited queries.
- Information-theoretic impossibilities: Fundamental limits on what can be learned, regardless of the number of queries.
- Query-complexity lower bounds: Situations where, even if it is possible in theory to achieve a desired outcome, an exponential number of queries may be required, making it practically infeasible.

Based on joint work with Safwan Hossain, Gregory Kehne, Ariel Procaccia, Jamie Tucker-Foltz, and Manuel Wüthrich.

Bio: Daniel Halpern is a final-year PhD student at Harvard University advised by Ariel Procaccia. He is supported by an NSF Graduate Research Fellowship and a Siebel Scholarship. His research broadly sits at the intersection of algorithms, economics, and artificial intelligence. Specifically, he considers novel settings where groups of people need to make collective decisions, such as summarizing population views on large-scale opinion aggregation websites, using participant data to fine-tune large language models, and selecting panel members for citizens’ assemblies. In each, he develops provably fair solutions to aggregate individual preferences.