Linear Social Choice with Few Queries: A Moment-Based Approach

Luise Ge; Daniel Halpern; Gregory Kehne; Yevgeniy Vorobeychik

cs.GTMar 19, 2026

Linear Social Choice with Few Queries: A Moment-Based Approach

Authors: Luise Ge, Daniel Halpern, Gregory Kehne, Yevgeniy Vorobeychik

Organizations: Washington University in St. Louis. · Google Research.

Abstract

Most social choice rules assume access to full rankings, while current alignment practice -- despite aiming for diversity -- typically treats voters as anonymous and comparisons as independent, effectively extracting only about one bit per voter. Motivated by this gap, we study social choice under an extreme communication budget in the linear social choice model, where each voter's utility is the inner product between a latent voter type and the embedding of the context and candidate. The candidate and voter spaces may be very large or even infinite. Our core idea is to model the electorate as an unknown distribution over voter types and to recover its moments as informative summary statistics for candidate selection. We show that one pairwise comparison per voter already suffices to select a candidate that maximizes social welfare, but this elicitation cannot identify the second moment and therefore cannot support objectives that account for inequality. We prove that two pairwise comparisons per voter, or alternatively a single graded comparison, identify the second moment; moreover, these richer queries suffice to identify all moments, and hence the entire voter-type distribution. These results enable principled solutions to a range of social choice objectives including inequality-aware welfare criteria such as taking into account the spread of voter utilities and choosing a representative subset.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Symbol	Description
$\mathbb{S}^{d-1}$	The unit sphere in $\mathbb{R}^{d}$
$\bar{\sigma}$	Uniform probability measure (normalized surface area measure) on $\mathbb{S}^{d-1}$
$\Theta$	The underlying population distribution of voter types over $\mathbb{S}^{d-1}$
$x\in\mathcal{X},y\in\mathcal{Y}$	Prompts and Responses
$\Phi(x,y)$ or $\phi$	Embedding vector of a candidate (or prompt-response pair)
$u_{\theta}(\phi)$	Utility of voter $\theta$ for candidate $\phi$ , given by $\theta\cdot\phi$

Appendix

Table 1: Notation used throughout this work.

Social Choice Theory

Social choice theory studies how individual preferences can be combined into collective decisions, fair allocations, and representative outcomes.

See all 52 papers

Axiom Satisfiability of Linear Rewards in Alignment
Sep 26, 2026Soumya Nasipuri, Sayak Ray Chowdhury, Sanjukta RoyReward Modeling Preference Alignment
Indian Statistical Institute, India · Indian Institute of Technology Kanpur, India
Metric Distortion of Social Welfare Functions
Aug 22, 2026Fatih Erdem Kizilkaya, Aaryaman Aggarwal, Evi MichaSocial Choice Theory Rank Aggregation
University of Southern California · Indian Institute of Technology Kanpur
The End Justifies the Mean: A Linear Ranking Rule for Proportional Sequential Decisions
May 12, 2026Carmel Baharav, Niclas Boehmer, Bailey Flanigan +1Sequential Decision Making Group Fairness
MIT, USA · Hasso Plattner Institute, University of Potsdam, Germany

Sep 26, 2026J/K move · Enter open · S save

Axiom Satisfiability of Linear Rewards in Alignment

Soumya Nasipuri, Sayak Ray Chowdhury, Sanjukta Roy

Indian Statistical Institute, India · Indian Institute of Technology Kanpur, India

Reward Modeling Preference Alignment LLM Alignment Pairwise Preference Learning Social Choice Theory

Open paper AskPDF arXiv

Learning from human preference data is the dominant route to aligning language models with human values. In linear social choice, where rewards are linear in a fixed feature representation of prompt-response pairs, Ge et al.[2024] show that fitting such a reward by minimizing any non-decreasing convex loss, including BTL, fails PO and PMC. Moreover, no rule that reads only the majority relation can satisfy PO once the output is required to be linearly induced. We ask what it costs to enforce these axioms anyway. To this end, we relax the linear model to allow per-candidate slack. We compute the relaxed linear reward with the smallest total slack that satisfies the axioms with a margin

η

, the minimum required difference between two reward values. Our solution satisfies the axioms under no assumptions about the voters or how comparisons were collected. We bound the optimal total slack by

O(1)

when

η

is at most

O(\frac{1}{m^2})

for

m

candidates. Furthermore, we exhibit an instance that forces this bound, concluding that the rate is tight up to constants. In practice, the no. of candidates far exceeds the feature dimension, and only a linear reward can be evaluated on unseen responses. We therefore introduce a new method that charges the linear part for each comparison it gets wrong. It simultaneously minimizes the total slack and the no. of violations, with a parameter

λ

trading off between them. We show that the total slack is monotone but saturating in

λ

: raising it reduces the violations of the deployed linear reward and increases the slack, yet the slack stays below

(η+Δ\sqrt{d})\lfloor m^2/4\rfloor

, where

Δ

and

d

are the diameter and dimension of the features, respectively. Experiments on both synthetic and real-life preference data corroborate our theory and show that the linear reward output by our method beats linear BTL.

Abstract

Social Choice Theory

Explore similar work

Axiom Satisfiability of Linear Rewards in Alignment

Metric Distortion of Social Welfare Functions

The End Justifies the Mean: A Linear Ranking Rule for Proportional Sequential Decisions