Paper deep dive
Linear Social Choice with Few Queries: A Moment-Based Approach
Luise Ge, Daniel Halpern, Gregory Kehne, Yevgeniy Vorobeychik
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 94%
Last extracted: 3/23/2026, 12:05:35 PM
Summary
The paper introduces a moment-based approach to social choice under extreme communication constraints, specifically within a linear utility model. It demonstrates that the first moment of the voter distribution is identifiable with one pairwise comparison per voter, while higher-order moments (necessary for inequality-aware objectives) require additional queries. The authors prove that two pairwise comparisons per voter are sufficient to identify the entire voter-type distribution, enabling principled solutions for social welfare and committee selection.
Entities (5)
Relation Signals (3)
Pairwise Comparison Query → identifies → First Moment
confidence 98% · The first moment of the voter distribution is identifiable using one pairwise comparison query per voter.
Two Pairwise Comparison Queries → identifies → Voter Distribution
confidence 95% · The voter distribution is identifiable using 2 pairwise comparison queries per voter.
Linear Social Choice Model → uses → Voter Distribution
confidence 90% · Our core idea is to model the electorate as an unknown distribution over voter types
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2603.19510v1
- Canonical: https://arxiv.org/abs/2603.19510v1
Trouble viewing inline? Open PDF directly →
Full Text
129,956 characters extracted from source content.
Expand or collapse full text
Linear Social Choice with Few Queries: A Moment-Based Approach Luise Ge Washington University in St. Louis. g.luise@wustl.edu Daniel Halpern Google Research. dhalpern@google.com Gregory Kehne Washington University in St. Louis. kehne@wustl.edu Yevgeniy Vorobeychik Washington University in St. Louis. yvorobeychik@wustl.edu 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. 1 Introduction A fundamental problem in social choice is to map potentially diverse preferences of a collection of voters over a set of candidates to a subset of winners. The classical model assumes that voter preferences are elicited as full rankings. In many real settings, however, the voter population can be massive and the candidate space is enormous or unbounded—for example, voters may be users of an AI system (such as an LLM) and candidates may be possible outputs like images, music, recipes, or answers to complex prompts. Moreover, preferences over candidates may depend a great deal on context, which itself can defy enumeration: for example, preferences over responses clearly depend on the question. This situation has become particularly salient in the context of AI value alignment, such as training large language models (LLMs) to align with (i.e., behave according to) humans’ subjective values such as helpfulness and harmlessness Bai et al. (2022); Ji et al. (2023); Ouyang et al. (2022, 2025). Since the space of candidates cannot be explicitly enumerated, a typical paradigm would present specific pairs of candidates to human annotators, who would select which of these they prefer, or indicate indifference. Such datasets are typically collected without retaining annotator identifiers; hence, the feedback per voter can be as sparse as one bit. Approaches such as reinforcement learning from human feedback (RLHF) then use these pairwise comparisons to first train a parametric reward (utility) function. This reward model is subsequently plugged into a conventional RL framework such as PPO Schulman et al. (2017) to achieve context-dependent behavioral alignment Christiano et al. (2017); Stiennon et al. (2020). While there has been an increasing interest in incomplete vote elicitation Halpern et al. (2023, 2024), the practice of AI alignment has pushed the feedback constraint to an extreme. On the one hand, if we wish to achieve useful guarantees about selecting good candidates in such settings (e.g., in terms of social welfare if voter preferences reflect latent utility functions), the situation seems hopeless. On the other hand, it is typical in settings such as value alignment that the space of candidates and voters is structured. In particular, generative AI methods rely on embedding digital objects such as music, images, or text, as vectors. It is then natural to posit that human preferences, too, have a structured representation as parametric utility functions over these vectors, an assumption that is exploited in the reward model learning step of RLHF. This motivates our central research question: Is it possible to leverage vector representations of candidates and parametric representations of voter utilities to obtain sufficiently reliable information from few per-voter pairwise comparison queries to select good winning candidates, when voter and candidate spaces are both large? To study this question, we assume that each voter has a utility function over the vector space of candidates which is linear in the candidate embedding. Motivated by the linear representation hypothesis Park et al. (2024), this effectively assumes that LLM text embeddings are rich enough that user preferences can be represented as linear functions over them. Yet even in this structured setting, the initial results have been bleak. Even with access to full rankings, many aggregation rules including the standard RLHF procedure fail the most basic social choice properties like Pareto Optimality Ge et al. (2024a). Moreover, it is information-theoretically impossible to identify a candidate to achieve social welfare within a constant factor of optimal Ge et al. (2025). Crucially, these negative conclusions are obtained in a finite-electorate setting with a fixed dataset of comparisons. Our focus is instead on preference elicitation under limited communication. We assume access to a large population that can be sampled repeatedly, and we can choose the comparisons we ask, but each voter provides only a small number of binary responses. Still, suppose that we aim to choose a single candidate to (approximately) maximize social welfare. How many pairwise rankings do we need to elicit from each voter? Moreover, assuming we cannot ask all possible voters (e.g., the entire population of a country), how many voters suffice, if we treat each as a sample from an unknown voter distribution? Furthermore, how does this picture change as we ask more complex questions, such as (a) maximizing welfare while accounting for inequality aversion, or (b) selecting a committee rather than a single candidate? 1.1 Our Contributions We cast our setting as social choice under sparse elicitation: each voter has a latent preference vector θ∈d−1θ ^d-1, but the mechanism can ask only a small number of comparison-style queries per voter. This raises three basic questions: (i) which social objectives are meaningful in this limited-information regime, (i) what information should be elicited to evaluate those objectives, and (i) how many samples (voters) are required. Our answers are organized around a single principle: moments are appropriate summaries of the preference distribution. We show how different query families identify different moments, and we give finite-sample guarantees that translate moment estimation into guarantees for downstream social-choice objectives. Concretely, first consider selecting a single candidate. If the goal is to maximize social welfare, it turns out only a single such query suffices. That is, we show that we can both identify (Section 3) and effectively estimate (Section 4) the first moment of the voter distribution with only a single pairwise comparison query per voter: Theorem 1.1 (informal). The first moment of the voter distribution is identifiable using one pairwise comparison query per voter. Moreover, we can estimate it to within ε with sample complexity polynomial in 1/ε1/ and d. As a direct consequence of this result, we can find an approximately welfare-optimal candidate by asking each voter only one pairwise comparison query (Section 5). While maximizing welfare is a natural goal in social choice, it has a significant limitation: the result can be extremely inequitable, for example, with some voters having very high, while many others very low, utility over the final candidate. It is often desirable to moderate this criterion by using welfare objectives that also account for inequality Atkinson and others (1970). fOne measure of inequality is utility variance, which we can leverage to construct welfare functions that combine average utility with variance. In order to identify a candidate that maximizes a variance-adjusted welfare function, a crucial subproblem is to estimate the second moment of the voter distribution. Is a single pairwise comparison query to each voter sufficient for this? We show that it is not (Section 3): Theorem 1.2 (informal). The second moment of the voter distribution is not identifiable from one pairwise comparison query per voter. Thus, we need more than a single pairwise comparison per voter to obtain variance information. Do two such comparisons suffice? We show that they do—in fact, we show that this generalizes directly for any k (Section 3 shows identifiability while Section 4 considers estimation): Theorem 1.3 (informal). The first k moments of the voter distribution are identifiable using k pairwise comparison queries per voter, and can be estimated from such data to within ε with sample complexity polynomial in 1/ε1/ and d. Intuitively, it seems that k pairwise queries are also necessary to identify k moments of a distribution. Remarkably, this is not true: only 2 per voter queries suffice to estimate any properties of the distribution (including arbitrary moments): Theorem 1.4 (informal). The voter distribution is identifiable using 22 pairwise comparison queries per voter, and the kkth moment can be estimated from such data to within ε with sample complexity polynomial in 1/ε1/ and d. We can also significantly generalize the above results to stochastic response models; details are provided in Appendix D. Furthermore, if voters only respond if they strongly prefer one response to another (formally defined in Section 2.5), then only one query per voter is necessary to identify the distribution. Our moment-based approach is also useful in selecting candidates under other objectives. For example, we show how moments can be used to approximate Nash welfare. We also apply this to selecting committees of candidates in multi-winner elections. In this context, we need to extend the voter utility functions to sets of candidates. For example, we can assume that each voter’s utility of a set is the maximum utility from any candidate in the set. By approximating this using a k-degree polynomial and maximizing the resulting function, we can obtain an approximately social-welfare-optimal committee. 1.2 Related Work Our work operates within the Linear Social Choice framework, a new paradigm of social choice in which voter utilities are linear functions of context and candidate embeddings. Prior results emphasize worst-case aspects from axiom violations Ge et al. (2024a) to distortion bounds Ge et al. (2025). In contrast, we take a bottom-up perspective and ask information-theoretic questions. There is a rich literature on dealing with incomplete information in social choice (Brandt et al., 2016, Chapter 10). Our work is most closely related to recent frameworks that combine elicitation with distributional assumptions, where only minimal information is elicited from each voter Halpern et al. (2023, 2024). These works, however, focus on different feedback models (e.g., approval) and different questions (e.g., computing voting rules), and do not operate in the linear-utility setting. Our contributions also intersect with the extensive preference learning literature whose roots lie in learning to rank Cohen et al. (1997); Burges et al. (2005), and which has been adopted for virtual democracy Noothigattu et al. (2018); Kahng et al. (2019). More recently, learning a parametric utility model has been analyzed theoretically Ge et al. (2024b) and used in practice as part of RLHF-style training Christiano et al. (2017) to enable generalization over large candidate sets. Notably, these works deal with a single preference, and observed disagreement is treated as noise. In contrast, pluralistic alignment and the increasing use of LLM-based auto-raters Li et al. (2025) shift the focus toward learning the voter population itself. Efforts in this direction are so far predominantly empirical Chakraborty et al. (2024); Melnyk et al. (2024); Siththaranjan et al. (2024); Kim et al. (2025). The more theoretical works to date Chidambaram et al. (2025); Cherapanamjeri et al. (2025); Shirali et al. (2025) adopt different models but, broadly, resonate with our findings: the standard alignment data pipeline is insufficient for learning heterogeneity in the underlying population. Our estimation strategy relies on the Generalized Method of Moments (GMM) Hansen (1982); Pearson (1936). While GMM has been applied to estimate parameters of probabilistic ranking models like Plackett-Luce Azari Soufiani et al. (2013), we adapt the principle to the linear setting. At a technical level, our problem is also related to 1-Bit Compressed Sensing in signal processing Boufounos and Baraniuk (2008); Plan and Vershynin (2013), which recovers signals from the signs of random linear measurements. Our setting shares this structure of receiving single bits of information per sample (comparison queries), though we focus on recovering distributional moments rather than sparse vectors, and allowing multiple comparison queries at once. At a more fundamental level, our identifiability results connect to geometric tomography and the Cramér-Wold theorem Cramér and Wold (1936), which states that a high-dimensional distribution is determined by its lower-dimensional projections. We extend these insights to show how “projections” obtained via pairwise queries are sufficient to recover properties of the voter distribution. 1.3 Organization The rest of the paper is organized as follows. First, we provide formal preliminaries in Section 2. Our main results regarding identifiability of moments of the voter distribution from pairwise comparison queries then follow in Section 3. Next, we build on the positive identifiability results to characterize how to estimate moments in Section 4. Finally, we illustrate our results on moment estimation in the context of social choice applications in both single-winner and committee selection in Section 5. 2 Preliminaries 2.1 Voters and Utilities We assume that voters v∈Vv∈ V are distributed according to a distribution V which represents our underlying voter population. Each voter is characterized by a type vector θv _v lying on the unit sphere d−1≔θ∈ℝd:‖θ‖2=1S^d-1 \θ ^d:\|θ\|_2=1\ to control for utility scale invariance of preference rankings. This mapping induces a voter type distribution Θ over d−1S^d-1. For ease of exposition, we assume that Θ is absolutely continuous with respect to the Lebesgue measure on the sphere.111Informally, this implies that the probability mass of the voter distribution is not concentrated on lower-dimensional subsets. However, with additional technical care, our results can be extended to hold without this assumption. We consider a space of contexts (prompts) X and a space of candidates (responses) Y. An embedding function Φ:×→ℝd :X×Y ^d maps each context-candidate pair to a real vector. We assume that voter utilities are linear in these embeddings; specifically, the utility of a voter with type θ for a pair (x,y)(x,y) is given by the inner product uθ(x,y)=θ⋅Φ(x,y)u_θ(x,y)=θ· (x,y). Since utilities are fully determined by voter types and candidate embeddings, we will henceforth identify voters directly with their types θ and refer to Θ as the voter distribution. Similarly, we will often refer to a context-candidate pair (x,y)(x,y) by its embedding ϕ=Φ(x,y)φ= (x,y), writing the utility function simply as uθ(ϕ)=θ⋅ϕu_θ(φ)=θ·φ. Finally, we will write ϕU_φ for the distribution of utilities induced by ϕφ, i.e., ϕU_φ is the distribution induced by uθ(ϕ)u_θ(φ) over the randomness of θ. A reference table is provided in Appendix A. 2.2 Welfare Objectives The first objective to consider is social welfare, which is the expected utility w.r.t. the voter distribution θ∼Θ[uθ(ϕ)]E_θ [u_θ(φ) ]. However, simply maximizing welfare can yield considerable inequality in realized utility across voters. A number of alternative welfare notions therefore aim to adjust for potential inequality. A natural way to do this is maximizing risk-adjusted welfare (raw), maximize the expected welfare but penalize a candidate by α times the standard deviation: Definition 2.1 (α-risk-adjusted welfare). For α≥0α≥ 0, the α-risk-adjusted welfare of ϕφ is given by rawα(ϕ)≔Θ[uθ(ϕ)]−α⋅Θ[(uθ(ϕ)−Θ[uθ(ϕ)])2]. raw_α(φ) _ [u_θ(φ) ]-α· E_ [ (u_θ(φ)-E_ [u_θ(φ) ] )^2 ]. Another common objective that has the effect of being more equitable than social welfare is Nash welfare, which in our setting is defined as θ∼Θ[loguθ(ϕ)]E_θ [ u_θ(φ) ]. Of course, for this to be well-defined and meaningful, voter utilities uθ(ϕ)u_θ(φ) must be strictly positive. Alternatively, it is often possible and desirably to compute a set of winning candidates (that is, a committee) W rather than a single winner. In a welfarist context, we need to extend a voter’s utility over individual candidates to a utility function over sets. One natural extension is that the voter’s utility for W stems from their most preferred candidate in W, i.e., uθ(W)=maxϕ∈Wuθ(ϕ)u_θ(W)= _φ∈ Wu_θ(φ). This yields a welfare objective that we refer to as top-choice welfare: Definition 2.2 (Top-choice welfare). For a user distribution Θ and a set of candidate responses Φ , the top-choice welfare of a set of candidates W⊆ΦW is given by tcwΘ(W)≔Θ[maxϕ∈Wuθ(ϕ)]. tcw_ (W) _ [ _φ∈ Wu_θ(φ) ]. We refer to the problem of optimizing tcw tcw subject to |W|≤ℓ W ≤ for a given ℓ as ℓ -tcw tcw maximization. 2.3 Preference Elicitation As is typical in the value alignment literature, voters do not report their utilities directly (it is typically too much to ask). Instead, we elicit preference information via pairwise comparison queries. A single query consists of a context x and a pair of candidate responses y1,y2y_1,y_2. When presented with such a query, a voter θ indicates which response yields higher utility, returning 11 if they prefer y1y_1 and 0 if they prefer y2y_2.222Our framework can be naturally extended to incorporate stochastic responses; see Appendix D. We encode this response as respθ((x,y1,y2))=uθ(x,y1)≥uθ(x,y2)resp_θ((x,y_1,y_2))=I\u_θ(x,y_1)≥ u_θ(x,y_2)\.333This formulation effectively breaks ties in favor of y1y_1, but the specific tie-breaking mechanism does not impact our results. By the absolute continuity of Θ , the probability that a random voter assigns exactly equal utility to any two distinct candidate embeddings is zero. In our linear utility model, the condition uθ(x,y1)≥uθ(x,y2)u_θ(x,y_1)≥ u_θ(x,y_2) is equivalent to θ⋅(Φ(x,y1)−Φ(x,y2))≥0θ·( (x,y_1)- (x,y_2))≥ 0. Since the response depends solely on the difference between the embeddings, we define the query vector q≔Φ(x,y1)−Φ(x,y2)q (x,y_1)- (x,y_2) and allow the response function to operate directly on these differences, i.e., respθ(q)≔θ⊤q≥0resp_θ(q) 1\θ q≥ 0\. Our results rely on a geometric assumption that for any direction, we can identify a context and pair of candidates that (approximately) induce this vector by the difference in the associated embeddings. In effect, this means that the space of contexts and candidates must be sufficiently rich, at least with respect to the induced embedding space. This assumption allows us to establish the fundamental limits of this form of preference elicitation. Impossibility results in our setting imply impossibility under any weaker query model. Conversely, positive identifiability results establish a theoretical ceiling, reducing the alignment problem to the engineering challenge of generation. Assumption 2.3. The embedding space is sufficiently expressive such that for any direction q∈d−1q ^d-1, we can generate (x,y1,y2)(x,y_1,y_2) such that Φ(x,y1)−Φ(x,y2)∝q (x,y_1)- (x,y_2) q. Under Assumption 2.3, the problem of selecting a comparison (x,y1,y2)(x,y_1,y_2) reduces to directly choosing a direction q∈d−1q ^d-1. We refer to such a vector q as a query and treat these queries as the primary decision variables for the data collector. 2.4 Multi-Query Responses Given a sequence of t queries =(q1,…,qt)q=(q_1,…,q_t), a random voter θ∼Θθ arrives and provides a response vector (respθ(q1),…,respθ(q1))∈0,1t(resp_θ(q_1),…,resp_θ(q_1))∈\0,1\^t indicating their preferences. Consequently, a fixed query sequence q induces a distribution over binary response vectors. We define Qt(,;Θ)Q_t(q,b; ) as the probability that a random voter drawn from Θ produces the response vector ∈0,1tb∈\0,1\^t when presented with queries q. When the underlying distribution Θ is clear from context, we will omit it from the notation. Thus, for any fixed q, the function Qt(,⋅)Q_t(q,·) represents a probability distribution over 0,1t\0,1\^t. Throughout, we will use the shorthand Qt()Q_t( q) to denote the probability of the all-positive response vector, Qt(,)Q_t( q, 1), where =(1,…,1) 1=(1,…,1). Formally, we have Qt(q1,…,qt)≔Prθ∼Θ[[respθ(q1)=1]∧…∧[respθ(qt)=1]].Q_t(q_1,…,q_t) _θ [[resp_θ(q_1)=1] … [resp_θ(q_t)=1] ]. It is worth noting that the probability of any arbitrary response pattern ∈0,1tb∈\0,1\^t can be recovered solely from the values of Qt()Q_t(q) (for instance, by negating specific query vectors qiq_i to target zeros, since respθ(−q)=1−respθ(q)resp_θ(-q)=1-resp_θ(q) almost surely). Finally, we remark that we assume deterministic voter responses in the main paper for clarity of presentation. Nevertheless, our results for multi-query elicitation extend directly to stochastic response models (e.g., Bradley–Terry); see Appendix D. 2.5 Graded-Query Responses Beyond ordinal comparisons, recent work shows that even a few bits of cardinal utility can improve distortion in single-winner elections Amanatidis et al. (2021); Ebadian and Shah (2025). But reporting cardinal values remains cognitively challenging. By contrast, reporting preference intensity (e.g., “strong” versus “weak”) is often less demanding and is already collected in many preference datasets. We therefore follow the line of work that incorporates preference intensity Kahng et al. (2023). Concretely, we model a graded preference query as whether the utility margin exceeds a threshold τ∈(0,1)τ∈(0,1): gradθ(q)≔θ⊤q≥τgrad_θ(q) 1\θ q≥τ\. Then for a distribution Θ , Gτ(q)=Prθ∼Θ[gradθ(q)]G_τ(q)= _θ [grad_θ(q)] returns the fraction of voters having a τ-strong preference. Since the inner product θ⊤qθ q depends on the norm of q, for results on graded queries, we need to further assume that the query space is rich enough to produce q∈d−1.q ^d-1. Assumption 2.4. The embedding space is sufficiently expressive such that for any direction q∈d−1q ^d-1, we can generate (x,y1,y2)(x,y_1,y_2) such that Φ(x,y1)−Φ(x,y2)=q (x,y_1)- (x,y_2)=q. 2.6 Distributions and their Moments We adopt the standard measure-theoretic formalism of probability, in which probability distributions are defined over a sample space Ω with an associated σ-algebra ℛR of measurable events. Probability measures are then measures μ on (Ω,ℛ)( ,R) that are normalized such that μ(Ω)=1μ( )=1. We will use σ¯ σ to describe the uniform probability measure over the sphere d−1S^d-1, to differentiate it from σ which is the unnormalized surface area measure over d−1S^d-1. Any measure μ over ℝR has an associated sequence of moments =(m0,m1,m2,…) m=(m_0,m_1,m_2,…) given by mn≔∫ℝxnμ(x)m_n _Rx^n\>dμ(x). Under certain assumptions, as in the Hausdorff moment problem, where μ is restricted to [0,1][0,1], they are sufficient to uniquely specify μ (up to sets of measure 0). We use tensors to represent the higher-order moments. Formally, a kkth order tensor T∈(ℝd)⊗kT∈(R^d) k is a multidimensional array indexed by a tuple (i1,…,ik)(i_1,…,i_k) where each ij∈[d]i_j∈[d]. For vectors v1,…,vk∈ℝdv_1,…,v_k ^d, the outer product v1⊗⋯⊗vkv_1 … v_k is a tensor with entries given by the product of the coordinates: (v1⊗⋯⊗vk)i1,…,ik=(v1)i1⋅(v2)i2⋯(vk)ik.(v_1 … v_k)_i_1,…,i_k=(v_1)_i_1·(v_2)_i_2·s(v_k)_i_k. When k=1k=1, this is equivalent to the vector itself; when k=2k=2, this corresponds to the matrix outer product v1v2⊤v_1v_2 . For two tensors A,B∈(ℝd)⊗kA,B∈(R^d) k, their inner product is the sum of the products of their corresponding entries: ⟨A,B⟩≔∑i1,…,ik=1dAi1,…,ikBi1,…,ik. A,B _i_1,…,i_k=1^dA_i_1,…,i_kB_i_1,…,i_k. We sometimes reshape tensors into matrices. For a partition of the modes 1,…,k\1,…,k\ into two sets I and J, the matricization matI|J(T)mat_I|J(T) flattens the tensor into a matrix where the rows are indexed by I and the columns by J. And sometimes we symmetrize a tensor of rank k as Sym(T)≔1k!∑π∈SkTπSym(T) 1k! _π∈ S_kT^π, with SkS_k the symmetric group and TπT^π the tensor re-indexed according to the permutation π. For a vector-valued distribution Θ over ℝdR^d, the moments =(M0,M1,M2,…) M=(M_0,M_1,M_2,…) can then be expressed using k-tensors: Mk≔θ∼Θ[θ⊗k]=∫ℝdθ⊗kμ(θ).M_k _θ [θ k ]= _R^dθ k\>dμ(θ). Intuitively, this is a k-dimensional array with entries indexed by sequences of k indices, i1,…,ik∈[d]i_1,…,i_k∈[d], where entries are the scalars (Mk)i1,…,ik=θ∼Θ[θi1⋯θik](M_k)_i_1,…,i_k=E_θ [ _i_1·s _i_k ]. We will write (Θ) M( ) and Mk(Θ)M_k( ) when the distribution (measure) is not clear from context. We can now relate the moments of the distribution over utilities ϕU_φ for a candidate ϕφ to the moments of θ. In particular, let mk=θ∼Θ[uθ(ϕ)k]m_k=E_θ [u_θ(φ)^k ] be the kkth moment. Then by tensor arithmetic and linearity of uθ(ϕ)u_θ(φ), mk=⟨Mk,ϕ⊗k⟩m_k= M_k,φ k . 2.7 Moment Identifiability and Estimation Our first concern is information-theoretic: what properties P of the voter distribution Θ (e.g., its kkth moment tensor Mk(Θ)M_k( )) can be determined by the responses? We say that P is identifiable from QtQ_t if, for any two distributions Θ,Θ′ , that yield identical query responses (e.g., Qt(Θ)=Qt(Θ′)Q_t( )=Q_t( )), it holds that (Θ)=(Θ′)P( )=P( ). For example, the kkth moment is identifiable with t-sized queries if, for any two distributions with distinct kkth moments, there exist a =(q1,…,qt)q=(q_1,…,q_t) and =(b1,…,bt)b=(b_1,…,b_t) such that Qt(,;Θ1)≠Qt(,;Θ2)Q_t(q,b; _1)≠ Q_t(q,b; _2). In applications, we must estimate moments from finitely many voters. Since we are ultimately interested in using moments to estimate the utility distribution of given ϕφ, we measure estimation error using the spectral norm, which for a kkth order tensor T∈(ℝd)⊗kT∈(R^d) k is defined as ‖T‖≔supu1,…,uk∈d−1|⟨T,u1⊗⋯⊗uk⟩|.\|T\| _u_1,…,u_k ^d-1 | T,u_1 ·s u_k |. For k=1k=1, the spectral norm corresponds to the standard L2L_2 norm. Control over the spectral norm guarantees uniform accuracy in estimating the moments of the utility distribution. Specifically, if M^k M_k satisfies ‖M^k−Mk‖≤ε\| M_k-M_k\|≤ , then for any ϕ∈ℝdφ ^d, the estimated kkth moment of the utility distribution satisfies: |⟨M^k,ϕ⊗k⟩−θ∼Θ[⟨θ,ϕ⟩k]|≤ε‖ϕ‖k. | M_k,φ k -E_θ [ θ,φ ^k ] |≤ \|φ\|^k. 3 Identifiability of Moments from Queries A key first step toward estimating moments from pairwise comparisons is understanding the minimum number of queries per voter needed for identifiability. In this section, we provide such results in the form of identifiability. We start by considering the first moment M1M_1, which in our setting translates to effective social welfare maximization, showing that only a single per-voter query suffices. Next, we show several more general results: 1) we can identify the first k moments using k per-voter queries, and 2) only two queries or only a single graded query per voter are sufficient to identify all moments (and hence, the distribution). 3.1 Identifying the Average Voter This first moment M1M_1 is the average voter, i.e., M1≔θ¯=θ∼Θ[θ]M_1 θ=E_θ [θ ]. Observation 3.1. Knowing θ¯=M1 θ=M_1 suffices to maximize welfare of Θ ; in particular, for any candidate embedding ϕφ, we have θ∼Θ[uθ(ϕ)]=θ∼Θ[θ⊤ϕ]=θ¯⊤ϕE_θ [u_θ(φ) ]=E_θ [θ φ ]= θ φ. We now show that M1M_1 can be identified from 11-sized queries alone. Recall that Q1Q_1 denotes pairwise comparison queries. Consider the contribution of a voter type θ to Q1Q_1 when averaged over all query directions q, which we denote by I(θ)≔∫d−1respθ(q)⋅qσ¯(q).I(θ) _S^d-1resp_θ(q)· q\>d σ(q). As query directions q are uniform, symmetry implies that this is itself in the direction of θ. Lemma 3.2. For any θ∈d−1θ ^d-1 it holds that I(θ)=cd⋅θI(θ)=c_d·θ, where cd=Γ(d/2)2πΓ(d+12)=Θ(d−1/2).c_d= (d/2)2 π ( d+12)= (d^-1/2). (1) In particular, cd≥12π⋅d−1/2c_d≥ 1 2π· d^-1/2. Proof of Lemma 3.2. Let R be any rotation in ℝdR^d. Because ⟨Rθ,q⟩=⟨θ,R−1q⟩ Rθ,q = θ,R^-1q and dσ¯d σ is rotation invariant, I(Rθ)= I(Rθ)= ∫⟨Rθ,q⟩≥0⋅qσ¯(q)=∫⟨θ,R−1q⟩≥0⋅qσ¯(q) 1\ Rθ,q ≥ 0\· q\>d σ(q)= 1\ θ,R^-1q ≥ 0\· q\>d σ(q) = = ∫⟨θ,q′⟩≥0Rq′σ¯(q′)=RI(θ). 1\ θ,q ≥ 0\\,Rq \,d σ(q )=R\,I(θ). Let ℛθR_θ be the subgroup of rotations of ℝdR^d that fix θ. For any R∈ℛθR _θ, we have Rθ=θRθ=θ, and therefore by the equivariance established above, RI(θ)=I(Rθ)=I(θ).R\,I(θ)=I(Rθ)=I(θ). Therefore I(θ)I(θ) is the fixed point of the linear action of the group ℛθR_θ. However, as ℛθR_θ is acting as the full rotation group on the orthogonal complement of θ, the only fixed point in θ⟂θ is the zero vector, and the only dimension left is for the span of the vector itself; hence I(θ)=cd⋅θ+0I(θ)=c_d·θ+0 for some scalar cdc_d. To calculate this constant, we set θ=e1θ=e_1 to obtain cd c_d ≔∫d−1q1≥0q1σ¯(q)=12Γ(d/2)πΓ((d−1)/2)∫01t(1−t2)d−32t _S^d-1 1\q_1≥ 0\q_1\>d σ(q)= 12 (d/2) π ((d-1)/2) _0^1t(1-t^2) d-32dt =1d−1Γ(d/2)πΓ((d−1)2)=Γ(d/2)2πΓ(d+12)≥12π⋅d−1/2, = 1d-1 (d/2) π ( (d-1)2)= (d/2)2 π ( d+12)≥ 1 2π· d^-1/2, where the second to last step follows from the Gamma recurrence Γ(x+1)=xΓ(x) (x+1)=x (x), and the last using Wendel’s Inequality Wendel (1948); Luo and Qi (2012); plugging in x=d/2x=d/2 and s=1/2s=1/2 yields Γ(d/2)Γ(d/2+1/2)>2d1/2 (d/2) (d/2+1/2)> 2d^1/2. ∎ This identity allows us to recover the first moment. Lemma 3.3. The first moment M1M_1 is identifiable with access to Q1Q_1. Proof. By applying first Lemma 3.2 and then Fubini’s theorem, we can write M1M_1 as θ∼Θ[θ] _θ [θ ] =θ∼Θ[1cd⋅∫⟨θ,q⟩≥0⋅qσ¯(q)]=1cd⋅∫⟨θ,q⟩≥0⋅qσ¯(q)Θ(θ) =E_θ [ 1c_d· 1\ θ,q ≥ 0\· q\>d σ(q) ]= 1c_d· 1\ θ,q ≥ 0\· q\>d σ(q)\>d (θ) =1cd⋅∫⟨θ,q⟩≥0⋅qΘ(θ)σ¯(q)=1cd⋅∫Q1(q)⋅qσ¯(q).∎ = 1c_d· 1\ θ,q ≥ 0\· q\>d (θ)\>d σ(q)= 1c_d· Q_1(q)· q\>d σ(q). Combining Lemma 3.3 with Observation 3.1, we have our first major result. Theorem 3.4. Welfare-maximizing candidates are identifiable from Q1Q_1. 3.2 Pairwise Queries and Higher Moments We may naturally wonder whether Q1Q_1 suffices to identify higher moments. As we show in the following example, it does not even for the second moment. Example 1. Consider the voter type distribution Θ±θ _±θ over d−1S^d-1 given by placing half of the probability mass in an ε -neighborhood around the vector θ and the other half (antipodally) symmetrically around −θ-θ. By symmetry, Q1(q)=1/2Q_1(q)=1/2 for all queries q regardless of θ. Furthermore, all candidates ϕ∈d−1φ ^d-1 confer expected welfare 0. But candidates orthogonal to θ have variance ≈0≈ 0, while candidates c≔βθc βθ for a fixed β have variance β2β^2. This example illustrates that some distributions are indistinguishable from one another via Q1Q_1 and therefore from their first moments M1M_1, but that optimizing well-motivated nonlinear objectives requires distinguishing them. Naturally, this trend continues: knowing the moment tensors M1,…,MkM_1,…,M_k does not determine subsequent moments, or the distribution overall, even when its support is constrained to d−1S^d-1. Observation 3.5. For d≥2d≥ 2 and let k≥1k≥ 1. There exist two probability measures μ+ _+ and μ− _- on the sphere d−1S^d-1 such that they have the same first k moments but have different (k+1)(k+1)-st moments. We defer details to Appendix C. In particular, this means that we should not hope to derive M2M_2 from M1M_1. Can we derive M2M_2 from Q2Q_2? We now show that we can; in fact, we show that we can derive MkM_k from QkQ_k, for any k. Theorem 3.6. The kkth moment tensor MkM_k is identifiable from Mk=1cdk⋅q1,…,qk∼σ¯k[Qk(q1,…,qk)⋅q1⊗⋯⊗qk],M_k= 1c_d^k·E_q_1,…,q_k σ^k [Q_k(q_1,…,q_k)· q_1 ·s q_k ], where cdc_d is defined as in Lemma 3.2. Proof. In Lemma 3.2, we showed that for any fixed θ and for uniform q∼σ¯q σ, q[⟨θ,q⟩≥0⋅q]=cd⋅θ.E_q [ 1\ θ,q ≥ 0\· q ]=c_d·θ. We will now generalize this to the expectation over k independently chosen pairwise comparison directions. Consider sampling k uniformly independent comparison directions ∼σ¯k q σ^k, where =(q1,…,qk) q=(q_1,…,q_k). For fixed θ, due to independence, [⟨θ,q1⟩≥0,…,⟨θ,qk⟩≥0⋅q1⊗⋯⊗qk] _ q [ 1\ θ,q_1 ≥ 0,…, θ,q_k ≥ 0\· q_1 ·s q_k ] =⨂j=1kqj[⟨θ,qj⟩≥0⋅qj]=cdk⋅θ⊗k, = _j=1^kE_q_j [ 1\ θ,q_j ≥ 0\· q_j ]=c_d^k·θ k, where last step follows from Lemma 3.2. Taking the expectation over Θ and applying Fubini yields θ∼Θ[[⟨θ,q1⟩≥0,…,⟨θ,qk⟩≥0⋅q1⊗⋯⊗qk]] _θ [E_ q [ 1\ θ,q_1 ≥ 0,…, θ,q_k ≥ 0\· q_1 ·s q_k ] ] =[Qk()⋅q1⊗⋯⊗qk] =E_ q [Q_k( q)· q_1 ·s q_k ] =cdk⋅θ∼Θ[θ⊗k]. =c_d^k·E_θ [θ k ]. Rearranging gives the stated claim. ∎ 3.3 Identifying the Voter Distribution via Size-2 Queries Having established that kkth moments of Θ are identifiable from k pairwise comparison queries, we now show an even stronger result: the full voter distribution is identifiable from two pairwise queries. Although in Section 4, we observe that the associated sample complexity is higher, it is quite remarkable that this is even possible. First, we note that the set of all moments M uniquely identify Θ . This is a well-known fact in probability and real analysis, even for the more general setting where the support of the distribution is a compact subset of ℝdR^d (e.g. (Schmüdgen, 2017, Corollary 14.9)). Lemma 3.7. If voter distributions Θ and Θ′ have equal moments (Θ)=(Θ′) M( )= M( ), then they are in fact equal: for all measurable sets T⊆d−1T ^d-1 it holds that Θ(T)=Θ′(T) (T)= (T). We outline the argument for completeness in Appendix C. Combined with Theorem 3.6, this says that if we can ask each voter infinitely many queries, we can distinguish any two distributions Θ and Θ′ . The problem is, of course, that asking a single voter an unbounded number of queries is infeasible. We now demonstrate that this is unnecessary. Theorem 3.8. Distributions are identifiable from 22-sized queries. The high-level proof relies on the spectral decomposition of functions on the sphere into spherical harmonics. Recall that a single query effectively measures the fraction of voters residing in a specific hemisphere. In the spherical harmonic literature, this mapping is known as the hemispherical transform. This transform is invertible on the subspace of odd-degree spherical harmonics, allowing us to identify Θ[p(θ)]E_ [p(θ)] for any odd-degree harmonic p. Using linearity of expectation, this allows us to reconstruct all odd-degree moments. To identify even moments, we observe that any even-degree polynomial can be decomposed into a sum of a product of two odd-degree harmonics. This reduces the problem to identifying values of the form Θ[p(θ)p′(θ)]E_ [p(θ)p (θ)]. By asking two queries to each arriving voter, we can estimate the joint expectation of the responses, which identifies this product and allows us to recover all even moments. Proof of Theorem 3.8. We will show that all moments are identifiable. Lemma 3.7 then implies that distributions are identifiable. Our analysis relies on the spectral theory of functions on the sphere (Groemer, 1996, Chapter 3). For each j≥0j≥ 0, let ℋjH_j denote the finite-dimensional space of spherical harmonics of degree j on d−1S^d-1. An important fact is that any homogeneous polynomial can be decomposed into a sum of spherical harmonics (Groemer, 1996, Lemma 3.2.5). Specifically, if p is a homogeneous polynomial of degree k, we can write it as a sum of spherical harmonics, one for each degree j≤kj≤ k such that k−jk-j is even. We begin with odd k, and show how to extend our analysis to even k later. In particular, if k is odd, there exists fj∈ℋjf_j _j for each odd j≤kj≤ k such that for all θ∈d−1θ ^d-1, p(θ)=∑j≤kj is oddfj(θ).p(θ)= _ subarraycj≤ k\ j is odd subarrayf_j(θ)\>. For our purposes, p will be a k-degree monomial (e.g., p(θ)=∏j=1kθij)p(θ)= _j=1^k _i_j) for some indices i1,…,iki_1,…,i_k). Our goal is equivalent to recover θ∼Θ[p(θ)]E_θ [p(θ) ] for all monomial p. We now use a second property of spherical harmonics, i.e., Funk-Hecke Theorem (see Thm. B.1). It suggests that for any fixed spherical harmonic f∈ℋjf _j with j being odd, we have f(θ)=1μj∫Sd−1⟨θ,q⟩≥0f(q)σ¯(q),f(θ)= 1 _j _S^d-1 1\ θ,q ≥ 0\f(q)\;d σ(q), for a nonzero constant μj _j. Taking the expectation over Θ , θ∼Θ[f(θ)] _θ [f(θ) ] =1μj∬⟨θ,q⟩≥0f(q)σ¯(q)Θ(θ)=1μj∬⟨θ,q⟩≥0f(q)Θ(θ)σ¯(q) = 1 _j 1\ θ,q ≥ 0\f(q)\;d σ(q)d (θ)= 1 _j 1\ θ,q ≥ 0\f(q)\;d (θ)d σ(q) =1μj∫f(q)∫⟨θ,q⟩≥0Θ(θ)σ¯(q). = 1 _j f(q) 1\ θ,q ≥ 0\\;d (θ)d σ(q). The exchange of integrals is justified by Fubini’s theorem, as the integrand is bounded (⟨θ,q⟩≥0 1\ θ,q ≥ 0\ is trivially bounded, and spherical harmonics are continuous functions on the compact sphere), and the measures are finite. The inner integral corresponds to the expected query response: ∫⟨θ,q⟩≥0Θ(θ)=PrΘ[⟨q,θ⟩≥0]=Q1(q). 1\ θ,q ≥ 0\\,d (θ)= _ [ q,θ ≥ 0]=Q_1(q). Thus, the expected value of the harmonic is fully determined by Q1Q_1: θ∼Θ[f(θ)]=∫f(θ)Θ(θ)=1μj∫f(q)Q1(q,1)σ¯(q).E_θ [f(θ) ]= f(θ)\>d (θ)= 1 _j f(q)Q_1(q,1)\>d σ(q). Next, consider even k. We can decompose any monomial p of degree k into a product of two monomials of odd degrees p1p_1, p2p_2 of degrees k1k_1 and k2k_2 (e.g., by partitioning the index set such that k1+k2=k_1+k_2=k). As we have just seen, both p1p_1 and p2p_2 have decompositions into odd-degree spherical harmonics fj∈ℋjf_j _j for odd j≤k1j≤ k_1 and fj′∈ℋj′f _j _j for j′≤k2j ≤ k_2 such that, p1=∑j≤k1:j is odd fjandp2=∑j′≤k2:j′ is odd fj′.p_1= _j≤ k_1:j is odd f_j p_2= _j ≤ k_2:j is odd f _j . Thus, we can write p(x)=∑j≤k1,j′≤k2,j,j′ are odd fj(x)⋅fj′(x).p(x)= _j≤ k_1,j ≤ k_2,j,j are odd f_j(x)· f _j (x). (2) By (2), to determine θ∼Θ[p(θ)]E_θ [p(θ) ] for even-degree p it therefore suffices to deduce the expectation of the product of any two odd-degree spherical harmonics f and f′f ; that is, θ∼Θ[f(θ)f′(θ)]E_θ [f(θ)f (θ) ]. Fix two such spherical harmonics f and f′f of odd degrees j and j′j . As above, we can write f(θ)=1μj∫⟨θ,q⟩≥0f(q)σ¯(q)andf′(θ)=1μj′∫⟨θ,q⟩≥0f′(q)σ¯(q).f(θ)= 1 _j 1\ θ,q ≥ 0\f(q)\>d σ(q) f (θ)= 1 _j 1\ θ,q ≥ 0\f (q)\>d σ(q). By the linearity of the integral, f(θ)⋅f′(θ)=1μjμj′∬⟨θ,q⟩≥0⟨θ,q′⟩≥0f(q)f′(q′)σ¯(q)σ¯(q′).f(θ)· f (θ)= 1 _j _j 1\ θ,q ≥ 0\ 1\ θ,q ≥ 0\f(q)f (q )\>d σ(q)\>d σ(q ). Taking the expectation with respect to Θ , we have θ∼Θ[f(θ)⋅f′(θ)] _θ [f(θ)· f (θ) ] =1μjμj′∬⟨θ,q⟩≥0⟨θ,q′⟩≥0f(q)f′(q′)σ¯(q)σ¯(q′) = 1 _j _j 1\ θ,q ≥ 0\ 1\ θ,q ≥ 0\f(q)f (q )\>d σ(q)\>d σ(q ) =1μjμj′∬f(q)f′(q′)[∫⟨θ,q⟩≥0⟨θ,q′⟩≥0Θ(θ)]σ¯(q)σ¯(q′), = 1 _j _j f(q)f (q ) [ 1\ θ,q ≥ 0\ 1\ θ,q ≥ 0\\,d (θ) ]\>d σ(q)\>d σ(q ), where we again use Fubini’s theorem for the integral swap. Finally, letting =(q,q′) q=(q,q ) we have ∫⟨θ,q⟩≥0⟨θ,q′⟩≥0dΘ(θ)=PrΘ[⟨q,θ⟩≥0∧⟨q′,θ⟩≥0]=Q2(). 1\ θ,q ≥ 0\ 1\ θ,q ≥ 0\\>d (θ)= _ [ 1\ q,θ ≥ 0\ 1\ q ,θ ≥ 0\]=Q_2( q). Hence, θ∼Θ[f(θ)⋅f′(θ)]=1μjμj′∬f(q)f′(q′)Q2()σ¯(q)σ¯(q′),E_θ [f(θ)· f (θ) ]= 1 _j _j f(q)f (q )Q_2( q)\>d σ(q)\>d σ(q ), implying identifiability. ∎ 3.4 Identifying the Voter Distribution via Graded Queries Next, we consider graded queries. While these require the stronger Assumption 2.4, they yield a powerful return: the entire distribution is identifiable using only a single query per voter. Theorem 3.9. For almost all τ∈(0,1)τ∈(0,1), distributions are identifiable with access to GτG_τ. The proof is deferred to Appendix C. The high level approach is to show that each moment k is identifiable by (strong) induction on k. Suppose we know the first k−1k-1 moments. We consider the correlation between the graded response probability Gτ(q)G_τ(q) and the k-th tensor power of the query vector q, integrated over the uniform distribution of queries. Using the rotational symmetry of the sphere, this integral simplifies into a linear equation involving the unknown k-th moment of the voter distribution scaled by a specific scalar coefficient, plus terms composed entirely of lower-order moments (which are known by the inductive hypothesis). Crucially, this scaling coefficient depends on the threshold τ and behaves like a polynomial with a finite number of roots. Therefore, for almost all choices of τ (i.e., any τ not in this finite set of roots), the coefficient is non-zero, allowing us to invert the equation and uniquely recover the k-th moment. By excluding the countable union of such roots across all k, we can identify all moments, and hence the entire distribution, for almost every τ. Notably, if we only care about the first two moments, any τ∈(0,1)τ∈(0,1) suffices. 4 Moment Estimation In order to make our identifiability results useful, we must contend with the fact that we do not have perfect knowledge of these distributions, but instead can only obtain a finite set of samples of such comparisons. How many voters are sufficient in order to approximately learn the moments of Θ ? In general, we could have an algorithm that chooses which query q to make based on all previous responses. For all of our positive results, it will suffice to have q be selected uniformly at random. Our goal in this section is to bound the sample complexity of moment estimation. Definition 4.1 (Sample Complexity). Estimating the kkth moment from comparison queries has sample complexity T if there is an estimator M^k M_k taking in T t-sized regular query-response pairs =i,(respθi(i)i=1T r=\ q_i,(resp_ _i( q_i)\_i=1^T of T i.i.d. voters θi∼Θ _i to T uniformly random t-sized queries 1,…,T∼σ¯t q_1,…, q_T σ^t, such that for all unknown Θ , Pr[‖M^k()−Mk(Θ)‖≤ε]≥1−δ. _ r [ \| M_k( r)-M_k( ) \|≤ ]≥ 1-δ. 4.1 Warmup: Welfare Maximization from Queries Our first result shows that we can successfully estimate the first moment of the voter distribution by requesting a response to a single pairwise query from a polynomial number of voters. Theorem 4.2. The sample complexity of estimating the first moment from single queries is O(dε2log1δ)O( d ^2 1δ). Proof. Consider the double integral over the probability measure for both the voter distribution Θ and the query distribution Unif(d−1)Unif (S^d-1 ), which we denote by dΘd and dσ¯(q)d σ(q) respectively: ∬d−1×d−1respθ(q)⋅qσ¯(q)Θ(θ)=∫d−1cd⋅θΘ(θ)=cd⋅θ¯. _S^d-1×S^d-1resp_θ(q)· q\>d σ(q)\>d (θ)= _S^d-1c_d·θ\>d (θ)=c_d· θ. The corresponding estimator from T samples is θ¯^=1cdT⋅∑i∈[T]⟨qi,θi⟩≥0⋅qi. θ= 1c_dT· _i∈[T] 1 \ q_i, _i ≥ 0 \· q_i. We would like to bound the rate at which this approaches θ¯ θ in spectral norm, which is just L2L_2 norm. That is, we would like to upper bound the T required to satisfy Pr[‖θ¯−θ¯^‖2>ε]≤δ. [ \| θ- θ \|_2> ]≤δ. We take a standard approach and appeal to McDiarmid’s inequality McDiarmid and others (1989). To this end, let θ^i≔1cd⋅respθi(qi)⋅qi θ_i 1c_d·resp_ _i(q_i)· q_i define the auxiliary random variable yi≔θ¯−θ^iy_i θ- θ_i, and let f(y1,…,yT)≔‖∑iyi‖2=‖θ¯−θ¯^‖2.f(y_1,…,y_T) \| _iy_i \|_2= \| θ- θ \|_2. Our goal is then equivalent to upper bounding Pr[f(y1,…,yT)≥ε⋅T] [f(y_1,…,y_T)≥ · T ]. By the triangle inequality, this f satisfies the bounded difference property that for all yiy_i and yi′y_i it holds that |f(y1,…,yi,…,yT)−f(y1,…,yi′,…,yT)|≤‖θ^i−θ^i′‖2=O(cd−1) f(y_1,…,y_i,…,y_T)-f(y_1,…,y_i ,…,y_T) ≤ \| θ_i- θ_i \|_2=O(c_d^-1), since our sampled qiq_i have unit norm. Therefore by McDiarmid’s inequality, Pr[‖θ¯−θ¯^‖2>ε]=Pr[f(y1,…,yT)≥ε⋅T]≤exp(−2ε2TC⋅cd−2) [ \| θ- θ \|_2> ]= [f(y_1,…,y_T)≥ · T ]≤ ( -2 ^2TC· c_d^-2 ) for some constant C. Setting this upper bound on the failure probability to δ, solving for T, and recalling that cd=Θ(d−1/2)c_d= (d^-1/2) finally yields T=O(dε2log1δ)T=O( d ^2 1δ), as claimed. ∎ 4.2 Moments from k-Wise Queries Our next result significantly generalizes our observation above that the first moment can be efficiently estimated, showing that this, in fact, holds true more generally. Theorem 4.3. The sample complexity of estimating the kkth moment from k-sized queries is O((2π)k⋅k⋅d⌈k/2⌉ε2log(dδ)).O ( (2π)^k· k· d k/2 ^2 ( dδ ) ). A technical challenge is that tensors are not simply matrices with more indices; even extending familiar matrix notions—such as computing the norm of higher-order tensors is nontrivial Hillar and Lim (2013). And there is no comparably sharp, general-purpose concentration theory for tensors. We therefore work with matricizations of the relevant moment tensors, which allows us to leverage the matrix Bernstein inequality (Tropp, 2012, Theorem 1.6.2). Theorem 4.4 (Matrix Bernstein Inequality for real-valued matrices). Let S1,…,SnS_1,…,S_n be independent, centered real random matrices with common dimension d1×d2d_1× d_2, and assume that each one is uniformly bounded, i.e., [Sk]=0E [S_k ]=0 and ‖Sk‖≤L\|S_k\|≤ L for each k=1,…,nk=1,…,n. Let Z=∑k=1nSkZ= _k=1^nS_k, and let ν(Z)ν(Z) denote the matrix variance statistic of the sum: ν(Z)=max‖(ZZT)‖,‖(ZTZ)‖=max‖∑k=1n(SkSkT)‖,‖∑k=1n(SkTSk)‖.ν(Z)= \\|E(Z^T)\|,\|E(Z^TZ)\| \= \ \| _k=1^nE(S_kS_k^T) \|, \| _k=1^nE(S_k^TS_k) \| \. Then, for all t≥0t≥ 0, ℙ‖Z‖≥t≤(d1+d2)⋅exp(−t2/2ν(Z)+Lt/3).P \\|Z\|≥ t \≤(d_1+d_2)· ( -t^2/2ν(Z)+Lt/3 ). The following standard result shows that it is sufficient to bound the norm of the matricization. Lemma 4.5 (Proposition 4.1, Wang et al. (2017)). Let T∈(ℝd)⊗kT∈(R^d) k and let I⊔J=1,…,kI J=\1,…,k\. Then ‖T‖≤‖MatI|J(T)‖.\|T\|≤\|Mat_I|J(T)\|. Note that had we not matricized, typical vector-based concentration inequalities would end up with a dominant dkd^k factor. The matricization and more sophisticated matrix Bernstein inequality allow us to cut ≈d⌊k/2⌋≈ d k/2 off of the sample complexity. Proof of Theorem 4.3. We will make use of Theorem 3.6. Recall that Qk(q1,…,qk)Q_k(q_1,…,q_k) is the probability that a random voter θ has respθ(qi)=1resp_θ(q_i)=1 for all i. Thus, we can rewrite the statement as Mk=1cdk⋅q1,…,qk∼σ¯k,θ∼Θ[respθ(qi)=1∀i⋅q1⊗⋯⊗qk].M_k= 1c_d^k·E_q_1,…,q_k σ^k,θ [ 1\resp_θ(q_i)=1\,∀ i\· q_1 ·s q_k ]. Given T sampled queries and responses =i,(respθi(i)i=1T r=\ q_i,(resp_ _i( q_i)\_i=1^T, we let χi≔respθi(qi,j)=1∀j _i 1\resp_ _i(q_i,j)=1\,∀ j\ be the indicator that the i-th voter agreed with all k queries. We define the empirical estimator for the kkth moment as: M^k()≔1T∑i=1Tχicdk(qi,1⊗⋯⊗qi,k), M_k( r) 1T _i=1^T _ic_d^\,k(q_i,1 ·s q_i,k), which, by above, is an unbiased estimate of MkM_k. To bound the estimation error ‖M^k−Mk‖ \| M_k-M_k \|, we fix an arbitrary partition of the modes I⊔J=1,…,kI J=\1,…,k\ with |I|=s|I|=s and |J|=k−s|J|=k-s. Let (d1,d2)≔(ds,dk−s)(d_1,d_2) (d^s,d^k-s). By Lemma 4.5, it suffices to bound the spectral norm of the matricized difference as ‖MatI|J(M^k−Mk)‖. \|Mat_I|J( M_k-M_k) \|. We define independent random matrices Ai∈ℝd1×d2A_i ^d_1× d_2 such that: Ai≔MatI|J(1cdk⋅χi⋅qi,1⊗⋯⊗qi,k).A_i _I|J ( 1c_d^k· _i· q_i,1 ·s q_i,k ). Notice that [Ai]=MatI|J(Mk).E [A_i ]=Mat_I|J(M_k). Then, MatI|J(M^k−Mk)=1T∑i=1TSiMat_I|J( M_k-M_k)= 1T _i=1^TS_i, where Si≔Ai−[Ai]S_i A_i-E [A_i ] are independent, zero-mean random matrices. To apply the Matrix Bernstein inequality, we must compute a uniform bound L on the spectral norm of the summands and a bound ν on the total variance statistic. Towards establishing this uniform bound, for each i we can write the random matrix as an outer product Ai=χicdk⋅uivi⊤A_i= _ic_d^\,k· u_iv_i , where ui≔⨂j∈Iqi,j∈ℝd1u_i _j∈ Iq_i,j ^d_1 and vi≔⨂j∈Jqi,j∈ℝd2v_i _j∈ Jq_i,j ^d_2. Using the identity that ‖x⊗y‖=‖x‖⋅‖y‖\|x y\|=\|x\|·\|y\|, since the queries are all unit norm, ‖ui‖2=‖vi‖2=1 \|u_i \|_2= \|v_i \|_2=1. Because χi∈0,1 _i∈\0,1\, we have: ‖Ai‖=χicdk⋅‖ui‖2‖vi‖2≤1cdk. \|A_i \|= _ic_d^\,k· \|u_i \|_2 \|v_i \|_2≤ 1c_d^\,k. Since all norms are convex, by Jensen’s inequality ‖[Ai]‖≤[‖Ai‖]≤maxi‖Ai‖≤cd−k \|E [A_i ] \| [ \|A_i \| ]≤ _i \|A_i \|≤ c_d^-k. Then by the triangle inequality, we have ∥Si∥≤∥Ai∥+∥[Ai]∥≤2cdk=:L. \|S_i \|≤ \|A_i \|+ \|E [A_i ] \|≤ 2c_d^\,k=:L. We now bound the variance statistic ν≔max‖∑i=1T[SiSi⊤]‖,‖∑i=1T[Si⊤Si]‖ν \ \| _i=1^TE [S_iS_i ] \|, \| _i=1^TE [S_i S_i ] \| \. Since the T voters are independent, the total variance is bounded by: ν≤T⋅maximax[‖SiSi⊤‖],‖[Si⊤Si]‖.ν≤ T· _i \E [ \|S_iS_i \| ], \|E [S_i S_i ] \| \. (3) Next note that [SiSi⊤]=[AiAi⊤]−[Ai][Ai]⊤E [S_iS_i ]=E [A_iA_i ]-E [A_i ]E [A_i ] . We show that this implies ‖[SiSi⊤]‖≤‖[AiAi⊤]‖. \|E [S_iS_i ] \|≤ \|E [A_iA_i ] \|. (4) Indeed, for any unit vector x, x⊤[SiSi⊤]x=x⊤([AiAi⊤]−[Ai][Ai]⊤)x=x⊤[AiAi⊤]x−x⊤[Ai][Ai]⊤x. x E [S_iS_i ]x=x (E[A_iA_i ]-E[A_i]E[A_i] )x=x E[A_iA_i ]x-x E[A_i]E[A_i] x. Letting y=[Ai]⊤xy=E[A_i] x, this is equal to x⊤[AiAi⊤]x−y⊤y.x E[A_iA_i ]x-y y. Since y⊤y≥0y y≥ 0, this implies x⊤[AiAi⊤]x≥x⊤[SiSi⊤]x E[A_iA_i ]x≥ x E [S_iS_i ]x for all x. Hence ‖[SiSi⊤]‖≤‖[AiAi⊤]‖ \|E [S_iS_i ] \|≤ \|E[A_iA_i ] \|. With this established, we turn to upper bounding ‖[AiAi⊤]‖ \|E [A_iA_i ] \|. Utilizing the structure of AiA_i, the fact that viv_i is a unit vector (and hence vi⊤vi=1v_i v_i=1) and χi2=χi≤1 _i^2= _i≤ 1, we have: ‖AiAi⊤‖=‖χi2cd2k⋅ui(vi⊤vi)ui⊤‖≤‖1cd2k⋅uiui⊤‖. \|A_iA_i \|= \| _i^2c_d^2k· u_i(v_i v_i)u_i \|≤ \| 1c_d^2k· u_iu_i \|. Since the query vectors qi,jq_i,j are drawn independently and uniformly from d−1S^d-1, [qi,jqi,j⊤]=1dIdE [q_i,jq_i,j ]= 1dI_d. By independence across the distinct queries: [uiui⊤]=([qi,jqi,j⊤])⊗s=(1dId)⊗s=1dsId1.E [u_iu_i ]= (E [q_i,jq_i,j ] ) s= ( 1dI_d ) s= 1d^sI_d_1. Furthermore, ‖1dsId1‖=1ds \| 1d^sI_d_1 \|= 1d^s, so we get that ‖[AiAi⊤]‖≤1cd2kds. \|E [A_iA_i ] \|≤ 1c_d^2kd^s. Applying the analogous argument to ‖[Ai⊤Ai]‖ \|E [A_i A_i ] \|, we get ‖[Ai⊤Ai]‖≤1cd2kdk−s. \|E [A_i A_i ] \|≤ 1c_d^2kd^k-s. From (3) and (4), this implies ν≤Tcd2kmax(d−s,ds−k)=Tcd2kd−min(s,k−s)ν≤ Tc_d^2k (d^-s,\>d^s-k )= Tc_d^2kd^- (s,k-s). Applying the Matrix Bernstein inequality then yields: Pr(‖1T∑i=1TSi‖≥ε)≤(d1+d2)exp(−T2ε2/2ν+LTε/3). ( \| 1T _i=1^TS_i \|≥ )≤(d_1+d_2) (- T^2 ^2/2ν+LT /3 ). To ensure the error satisfies ‖M^k−Mk‖≤ε \| M_k-M_k \|≤ with probability at least 1−δ1-δ, we enforce the failure probability bound ≤δ≤δ. Substituting the derived bounds for ν and L, a sufficient condition for the sample complexity is: T≥2ε2(1cd2kdmin(s,k−s)+2ε3cdk)log(ds+dk−sδ).T≥ 2 ^2 ( 1c_d^2kd (s,k-s)+ 2 3c_d^k ) ( d^s+d^k-sδ ). We set s=⌊k/2⌋s= k/2 . Furthermore, recall from Lemma 3.2 that cd>12πd−1/2c_d> 1 2πd^-1/2. Furthermore, it is without loss of generality to assume ε≤1 ≤ 1, as the 0-tensor is a trivial 11-approximation as ‖Mk‖≤1 \|M_k \|≤ 1. Thus, T T =O(1ε2(d−⌊k/2⌋cd2k+1cdk)log(d⌈k/2⌉δ))=O(1ε2(dk−⌊k/2⌋⋅(2π)k+dk/2⋅(2π)k/2)log(d⌈k/2⌉δ)) =O ( 1 ^2 ( d^- k/2 c_d^2k+ 1c^k_d ) ( d k/2 δ ) )=O ( 1 ^2 (d^k- k/2 ·(2π)^k+d^k/2·(2π)^k/2 ) ( d k/2 δ ) ) =O((2π)k⋅k⋅d⌈k/2⌉ε2log(dδ)).∎ =O ( (2π)^k· k· d k/2 ^2 ( dδ ) ). 4.3 Estimating All Moments from Few Queries Our general result about moment estimation above requires k queries per voter. In Section 3, on the other hand, we showed that we can identify all moments with only two regular queries. How does this translate into sample efficiency? The following result shows that it is still possible to estimate, although our upper bound is weaker, requiring on the order of d3k+2d^3k+2 rather than d⌈k/2⌉d k/2 . Theorem 4.6. The sample complexity of estimating the kkth moment from size-22 queries is O(k(d+1)3k+2ε2log(dδ)).O ( k(d+1)^3k+2 ^2 ( dδ ) ). The proof is deferred to Appendix C. Our high-level approach mirrors the strategy used for k-wise queries in Theorem 4.3: we construct an unbiased estimator for the k-th moment tensor and bound its convergence using the Matrix Bernstein inequality. However, the construction of this estimator is considerably more involved than in the k-wise case, analogous to how Theorem 3.8 was more involved than Theorem 3.6. Recall that the constructive proof of Theorem 3.8 establishes that the expectation of any degree-k monomial can be recovered by integrating the product of two specific spherical harmonic functions against the query distribution Q2Q_2. Consequently, we can define our estimator via the empirical mean of these harmonic functions evaluated on sampled query pairs. The central technical challenge lies in bounding the magnitude of this estimator; for this, we must turn to more explicit constructions of spherical harmonics. These magnitude bounds lead to less efficient reconstruction: the sample complexity scales as O(d3k+2)O(d^3k+2) compared to the O(d⌈k/2⌉)O(d k/2 ) achieved with k-wise queries. Regarding graded queries, we leave the sample complexity bound to future work. While Theorem 3.9 establishes identifiability for almost all thresholds τ and provides a corresponding unbiased estimator, the reconstruction relies on inverting a specific coefficient that depends on τ. This coefficient vanishes at certain “blind spots,” and without a quantitative bound on how close an arbitrary τ is to these problematic points, we cannot control the magnitude or variance of the resulting estimator. 5 Social Choice with Sparse Query Responses Classical social choice rules take full rankings as input. Here we show it is possible to design a complementary class of rules that only require extremely sparse query responses from voters. All missing proofs in this section are deferred to Appendix C. 5.1 Moment-based Objectives We begin by considering our moment-based-objectives. Leveraging our sample complexity results for estimating moments, we can provide end-to-end guarantees. Maximizing Social Welfare. In a utilitarian setting, a natural and common objective is to maximize social welfare. Our results imply that this can be done with polynomial sample complexity: Proposition 5.1. By asking 1 query per voter, with at least T∈O(dε2log1δ)T∈ O( d ^2 1δ) arriving voters, with probability 1−δ1-δ over the arriving voters, for any candidate ϕφ with ‖ϕ‖≤B\|φ\|≤ B, we can estimate the social welfare θ[uθ(ϕ)]E_θ [u_θ(φ) ] up to additive error εB B. In particular, given a context x and ℓ candidates y1,…,yℓy_1,…,y_ such that ‖Φ(x,yi)‖≤B\| (x,y_i)\|≤ B, we can select y^i y_i within 2εB2 B of the optimal welfare. Maximizing Risk-Adjusted Welfare. A significant limitation of social welfare maximization is that it can yield extremely inequitable outcomes when voter preferences are highly diverse. Risk-adjusted welfare addresses this by explicitly accounting for inequality aversion. Armed with the first two moments, we can approximately maximize such welfare objectives. Proposition 5.2. By asking 2 queries per voter, for all ε≤1 ≤ 1, with at least T∈O(dε2logdδ)T∈ O( d ^2 dδ) arriving voters, with probability 1−δ1-δ over the arriving voters, for any candidate ϕφ with ‖ϕ‖≤B\|φ\|≤ B, we can estimate rawα(ϕ) raw_α(φ) up to 3⋅(α+1)Bε 3·(α+1)B . In particular, given a prompt x and ℓ possible responses y1,…,yℓy_1,…,y_ such that ‖Φ(x,yi)‖≤B\| (x,y_i)\|≤ B, we will be able to select one within 23⋅(α+1)Bε2 3·(α+1)B of the optimal risk-adjusted welfare. 5.2 Beyond Moment-based Objectives Next, we show how moments can be used to approximate other, more general objectives. Maximizing Nash Welfare. Like risk-adjusted welfare, Nash welfare, aims to balance social welfare and distributed fairness. Defined as Nash(ϕ)=Θ[log(uθ(ϕ))]Nash(φ)=E_ [ (u_θ(φ)) ], this objective corresponds to maximizing the geometric mean of utilities (or the product in the finite case). Naturally, this is only well-defined if voter utilities are strictly positive. While Nash welfare cannot be computed exactly from a finite set of moments, we show that if the candidate’s induced utilities lie within a known bounded interval, we can efficiently approximate the objective using moments. Theorem 5.3. Let ϕφ be a candidate and let [a,b]⊂(0,∞)[a,b]⊂(0,∞) be a known interval such that voter utilities satisfy uθ(ϕ)∈[a,b]u_θ(φ)∈[a,b] almost surely. Let r≔a/br a/b. The Nash welfare can be estimated using the first k moment tensors M1,…,MkM_1,…,M_k up to an additive error of: |Estk−Nash(ϕ)|≤r−1k+1(1−2r+1)k. |Est_k-Nash(φ) |≤ r-1k+1 (1- 2 r+1 )^k. Thus, we can achieve an approximation that improves exponentially quickly once k∈Ω(r)k∈ ( r). The proof uses standard techniques for approximating logarithm using kkth-degree polynomials, specifically, using Chebyshev polynomials Mason and Handscomb (2002). The expectation of any kkth-degree polynomial can then be computed using the first k moments. Proof of Theorem 5.3. The proof proceeds in two steps: first, we construct a kkth-degree polynomial PkP_k such that |Pk(x)−log(x)|≤r−1k+1(1−2r+1)k|P_k(x)- (x)|≤ r-1k+1 (1- 2 r+1 )^k for all x∈[a,b]x∈[a,b]. Then, we will show how to use PkP_k to estimate Nash welfare. We will use Chebyshev polynomials to approximate log on the interval. See Mason and Handscomb (2002) for an overview. Each Tk(x)T_k(x) is a kkth-degree polynomial, defined on [−1,1][-1,1], such that |Tk(x)|≤1|T_k(x)|≤ 1. They are defined such that Tk(cos(θ))=cos(kθ)T_k( (θ))= (kθ) (which, perhaps surprisingly, defines a kkth-degree polynomial mapping [−1,1][-1,1] to [−1,1][-1,1]). We would like to approximate log(x) (x) on [a,b][a,b]. We first reduce this to approximating on [−1,1][-1,1]. We map the interval [−1,1][-1,1] to [a,b][a,b] using the affine transformation g(t)≔b+a2+b−a2tg(t) b+a2+ b-a2t, and we let δ≔b−ab+a=1−r1+rδ b-ab+a= 1-r1+r where r=a/br=a/b. Substituting this into the logarithm function, we have log(g(t))=log(1+δt)+log((b+a)/2). (g(t))= (1+δ t)+ ((b+a)/2). Now, if we have a kkth-degree polynomial p′p that is uniformly within ε of log∘g g for t∈[−1,1]t∈[-1,1], then p′(g−1(⋅))p (g^-1(·)) is a kkth-degree polynomial that is within ε of log(x) (x) on [a,b][a,b]. Furthermore, it suffices to find a kkth-degree polynomial that approximates log(1+δt) (1+δ t), as log(g(t)) (g(t)) differs from this function only by the constant log(b+a2) ( b+a2). To get this in a form using Chebyshev polynomials, we will make use of the identity (Gradshteyn and Ryzhik, 2014, Equation 1.514) log(1−2αcos(φ)+α2)=−2∑j=1∞cos(jφ)j⋅αj, (1-2α ( )+α^2)=-2 _j=1^∞ (j )j·α^j, for α2≤1α^2≤ 1 and αcos(φ)≠1α ( )≠ 1. In Appendix C, we show how to use this to derive that log(1+tδ)=−log(1+α2)−2∑j=1∞αj⋅Tj(t), (1+tδ)=- (1+α^2)-2 _j=1^∞ α^jj· T_j(t), (5) for α=−r−1r+1α=- r-1 r+1. We can choose the kkth-degree polynomial Rk(t)≔−log(1+α2)−2∑j=1kαj⋅Tj(t)R_k(t) - (1+α^2)-2 _j=1^k α^jj· T_j(t) to approximate log(1+δt) (1+δ t). The error is |log(1+tδ)−Rk(t)|=|2∑j=k+1∞αj⋅Tj(t)|. | (1+tδ)-R_k(t) |= |2 _j=k+1^∞ α^jj· T_j(t) |. (6) Using that |Tj(t)|≤1|T_j(t)|≤ 1 for t∈[−1,1]t∈[-1,1], we can upper bound this error by ∑j=k+1∞2|α|j _j=k+1^∞ 2|α|^jj ≤2k+1∑j=k+1∞|α|j=2|α|k+1(k+1)(1−|α|)=r+1k+1(r−1r+1)k+1 ≤ 2k+1 _j=k+1^∞|α|^j= 2|α|^k+1(k+1)(1-|α|)= r+1k+1 ( r-1 r+1 )^k+1 =r−1k+1(r−1r+1)k=r−1k+1(1−2r+1)k. = r-1k+1 ( r-1 r+1 )^k= r-1k+1 (1- 2 r+1 )^k. We have therefore constructed a kkth-degree polynomial Pk(x)≔Rk∘g−1P_k(x) R_k g^-1, which can be written as Pk(x)=∑j=0kcjxjP_k(x)= _j=0^kc_jx^j for some coefficients cjc_j. Our proposed estimator is the expected value of this polynomial: Nash^≔θ∼Θ[Pk(uθ(ϕ))]=∑j=0kcjθ∼Θ[(uθ(ϕ))j]=∑j=0kcj⋅⟨Mj⋅ϕ⊗j⟩. Nash _θ [P_k(u_θ(φ))]= _j=0^kc_jE_θ [(u_θ(φ))^j]= _j=0^kc_j· M_j·φ j . Since |Pk+1(uθ(ϕ))−log(uθ(ϕ))||P_k+1(u_θ(φ))- (u_θ(φ))| is uniformly bounded for uθ(ϕ)∈[a,b]u_θ(φ)∈[a,b] as in (6) by the arguments above, this yields the same bound on the Nash approximation. ∎ Maximizing Welfare over Candidate Sets. In the paradigm of pluralistic alignment, a natural objective is to identify a set of candidates that represents most “reasonable” viewpoints Sorensen et al. (2024).555This goes by the name of Overton Pluralism. One way to operationalize this is to define the utility of each voter for a set of candidates as their maximum utility over the candidates in this set. In Section 2, we defined the associated welfare notion as top-choice welfare. Next, we show that we can obtain an approximate welfare maximizer in this setting by considering k moments of the voter distribution. Theorem 5.4 (Approximability of ℓ -tcw tcw maximization from moments). Fix ε>0 >0, ℓ , and a set of candidate responses Φ . Let ℓ≔(Φℓ)W_ be the collection of all sets of ℓ candidate. It is possible to identify a W^∈ℓ W _ for which tcwΘ(W^)≥maxW∈ℓtcwΘ(W)−ε tcw_ ( W)≥ _W _ tcw_ (W)- from only the moments M1,…,MkM_1,…,M_k of Θ for k=2Bd/εk=2Bd/ , where B is an upper bound on all uθ(ϕ)u_θ(φ). The proof relies on establishing that any two distributions sharing the first k moments are close in the 1-Wasserstein distance, which in turn bounds the estimation error for any Lipschitz-continuous welfare function. 6 Discussion We study social choice problems when each voter provides only minimal preference feedback. In the linear social choice model—where candidates have vector embeddings and voter utilities are linear—such inference is possible. We analyze pairwise queries with and without intensity, formalizing the latter as a thresholded additive difference. We find a sharp divide between one comparison per voter and slightly richer elicitation. A single pairwise comparison suffices to identify and efficiently estimate the first moment (the “average voter”), enabling approximately welfare-optimal selection. However, the second moment is not identifiable from one comparison, so objectives that depend on dispersion or inequality, such as risk-adjusted and Nash welfare, cannot generally be supported by asking only a single query per voter. On the other hand, with more comparisons per voter (or appropriately designed graded comparisons), higher-order structure becomes recoverable: with k comparisons we can identify the first k moments with polynomial sample complexity. Remarkably, two comparisons or one graded comparison per voter suffice to identify the full distribution, though with substantially weaker estimation efficiency. These moment-recovery results enable principled social choice methods beyond social welfare maximization. For single-winner selection, estimating the first two moments supports risk-adjusted and Nash welfare objectives, while for multi-winner selection, moments can be used to approximately optimize coverage-style committee objectives. Several challenges remain. Our analysis relies on geometric expressivity assumptions, making learnability under constrained query spaces an important open problem. Moreover, existing approximation bounds suggest that large k may be required; developing objectives and algorithms that perform well with low-order moments and realistic sample sizes is key. Additionally, while using one size-1 graded query per vote to identify the distribution has theoretical guarantees, how to properly elicit and use preference intensity queries in practice is nontrivial. Finally, extending moment-based approaches such as tensor decomposition Anandkumar et al. (2014) and sum-of-squares methods Laurent (2008) for more complex tasks is an interesting direction. More broadly, our work highlights a design principle for preference collection in social choice and beyond: small increases in per-user feedback richness can qualitatively expand what society-level properties are learnable, enabling alignment systems that capture not only average preferences but also disagreement and representation. References G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, and A. A. Voudouris (2021) Peeking behind the ordinal curtain: improving distortion via cardinal queries. Artificial Intelligence 296, p. 103488. Cited by: §2.5. A. Anandkumar, R. Ge, D. J. Hsu, S. M. Kakade, M. Telgarsky, et al. (2014) Tensor decompositions for learning latent variable models.. J. Mach. Learn. Res. 15 (1), p. 2773–2832. Cited by: §6. A. B. Atkinson et al. (1970) On the measurement of inequality. Journal of economic theory 2 (3), p. 244–263. Cited by: §1.1. K. Atkinson and W. Han (2012) Spherical harmonics and approximations on the unit sphere: an introduction. Springer Science & Business Media. Cited by: §C.4. S. Axler, P. Bourdon, and R. Wade (2001) Harmonic function theory. Vol. 137, Springer Science & Business Media. Cited by: §C.1. H. Azari, D. Parks, and L. Xia (2012) Random utility theory for social choice. Advances in Neural Information Processing Systems 25. Cited by: Appendix D. H. Azari Soufiani, W. Chen, D. C. Parkes, and L. Xia (2013) Generalized method-of-moments for rank aggregation. Advances in Neural Information Processing Systems 26. Cited by: §1.2. Y. Bai, A. Jones, K. Ndousse, A. Askell, A. Chen, N. DasSarma, D. Drain, S. Fort, D. Ganguli, T. Henighan, et al. (2022) Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.05862. Cited by: §1. P. T. Boufounos and R. G. Baraniuk (2008) 1-bit compressive sensing. In 2008 42nd Annual Conference on Information Sciences and Systems, p. 16–21. Cited by: §1.2. F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia (2016) Handbook of computational social choice. Cambridge University Press. Cited by: §1.2. C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G. Hullender (2005) Learning to rank using gradient descent. In Proceedings of the 22nd international conference on Machine learning, p. 89–96. Cited by: §1.2. S. Chakraborty, J. Qiu, H. Yuan, A. Koppel, F. Huang, D. Manocha, A. Bedi, and M. Wang (2024) Maxmin-rlhf: towards equitable alignment of large language models with diverse human preferences. In ICML 2024 Workshop on Models of Human Feedback for AI Alignment, Cited by: §1.2. S. Chen, V. Kontonis, and K. Shah (2025) Learning general gaussian mixtures with efficient score matching. In The Thirty Eighth Annual Conference on Learning Theory, 30-4 July 2025, Lyon, France, N. Haghtalab and A. Moitra (Eds.), Proceedings of Machine Learning Research, Vol. 291, p. 1029–1090. External Links: Link Cited by: §C.8. Y. Cherapanamjeri, C. Daskalakis, G. Farina, and S. Mohammadpour (2025) Learning correlated reward models: statistical barriers and opportunities. arXiv preprint arXiv:2510.15839. Cited by: §1.2. K. Chidambaram, K. V. Seetharaman, and V. Syrgkanis (2025) Direct preference optimization with unobserved preference heterogeneity: the necessity of ternary preferences. arXiv preprint arXiv:2510.15716. Cited by: §1.2. P. Christiano, J. Leike, T. B. Brown, M. Martic, S. Legg, and D. Amodei (2017) Deep reinforcement learning from human preferences. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1.2, §1. W. W. Cohen, R. E. Schapire, and Y. Singer (1997) Learning to order things. Advances in neural information processing systems 10. Cited by: §1.2. H. Cramér and H. Wold (1936) Some theorems on distribution functions. Journal of the London Mathematical Society 1 (4), p. 290–294. Cited by: §1.2. F. Dai and Y. Xu (2013) Approximation theory and harmonic analysis on spheres and balls. Springer. Cited by: Appendix B, Appendix B. S. Ebadian and N. Shah (2025) Every bit helps: achieving the optimal distortion with a few queries. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39, p. 13788–13795. Cited by: §2.5. P. Funk (1915) Beiträge zur theorie der kugelfunktionen. Mathematische Annalen 77 (1), p. 136–152. Cited by: Appendix B. L. Ge, D. Halpern, E. Micha, A. D. Procaccia, I. Shapira, Y. Vorobeychik, and J. Wu (2024a) Axioms for ai alignment from human feedback. Advances in Neural Information Processing Systems 37, p. 80439–80465. Cited by: §1.2, §1. L. Ge, B. Juba, and Y. Vorobeychik (2024b) Learning linear utility functions from pairwise comparison queries. arXiv preprint arXiv:2405.02612. External Links: Document Cited by: §1.2. L. Ge, G. Kehne, and Y. Vorobeychik (2025) Optimized distortion in linear social choice. In AAAI Conference on Artificial Intelligence, Cited by: §1.2, §1. I. S. Gradshteyn and I. M. Ryzhik (2014) Table of integrals, series, and products. Academic press. Cited by: §C.7, §5.2. H. Groemer (1996) Geometric applications of fourier series and spherical harmonics. Vol. 61, Cambridge University Press. Cited by: Appendix B, §C.4, §3.3, footnote 4. D. Halpern, S. Hossain, and J. Tucker-Foltz (2024) Computing voting rules with elicited incomplete votes. In Proceedings of the 25th ACM Conference on Economics and Computation, p. 941–963. Cited by: §1.2, §1. D. Halpern, G. Kehne, A. D. Procaccia, J. Tucker-Foltz, and M. Wüthrich (2023) Representation with incomplete votes. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37, p. 5657–5664. Cited by: §1.2, §1. L. P. Hansen (1982) Large sample properties of generalized method of moments estimators. Econometrica: Journal of the econometric society, p. 1029–1054. Cited by: §1.2. E. Hecke (1917) Über orthogonal-invariante integralgleichungen. Mathematische Annalen 78 (1), p. 398–404. Cited by: Appendix B. C. J. Hillar and L. Lim (2013) Most tensor problems are np-hard. Journal of the ACM (JACM) 60 (6), p. 1–39. Cited by: §4.2. J. Ji, M. Liu, J. Dai, X. Pan, C. Zhang, C. Bian, B. Chen, R. Sun, Y. Wang, and Y. Yang (2023) Beavertails: towards improved safety alignment of llm via a human-preference dataset. Advances in Neural Information Processing Systems 36, p. 24678–24704. Cited by: §1. A. Kahng, M. Latifian, and N. Shah (2023) Voting with preference intensities. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37, p. 5697–5704. Cited by: §2.5. A. Kahng, M. K. Lee, R. Noothigattu, A. Procaccia, and C. Psomas (2019) Statistical foundations of virtual democracy. In International conference on machine learning, p. 3173–3182. Cited by: §1.2. K. Kim, J. Zhang, A. Ozdaglar, and P. A. Parrilo (2025) Population-proportional preference learning from human feedback: an axiomatic approach. arXiv preprint arXiv:2506.05619. Cited by: §1.2. M. Laurent (2008) Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geometry, p. 157–270. Cited by: §6. Z. Li, X. Li, C. Huang, G. Li, K. Goshvadi, B. Dai, D. Schuurmans, P. Zhou, H. Palangi, Y. Song, and B. A. Malin (2025) Judging with confidence: calibrating autoraters to preference distributions. arXiv preprint arXiv:2510.00263v1. External Links: Link Cited by: §1.2. Q. Luo and F. Qi (2012) Bounds for the ratio of two gamma functions—from wendel’s and related inequalities to logarithmically completely monotonic functions. Banach Journal of Mathematical Analysis 6 (2), p. 132–158. Cited by: §3.1. J. C. Mason and D. C. Handscomb (2002) Chebyshev polynomials. Chapman and Hall/CRC. Cited by: §5.2, §5.2. C. McDiarmid et al. (1989) On the method of bounded differences. Surveys in combinatorics 141 (1), p. 148–188. Cited by: §4.1. I. Melnyk, Y. Mroueh, B. Belgodere, M. Rigotti, A. Nitsure, M. Yurochkin, K. Greenewald, J. Navratil, and J. Ross (2024) Distributional preference alignment of llms via optimal transport. Advances in Neural Information Processing Systems 37, p. 104412–104442. Cited by: §1.2. D. J. Newman and H. S. Shapiro (1964) Jackson’s theorem in higher dimensions. In Proceedings of Conference in Oberwolfach, International Series of Numerical Mathematics, Vol. 5, Basel-Stuttgart, p. 208–219. Note: ISNM 5 Cited by: §C.8. R. Noothigattu, S. Gaikwad, E. Awad, S. Dsouza, I. Rahwan, P. Ravikumar, and A. Procaccia (2018) A voting-based system for ethical decision making. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 32. Cited by: §1.2. L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al. (2022) Training language models to follow instructions with human feedback. Advances in neural information processing systems 35, p. 27730–27744. Cited by: §1. S. Ouyang, Y. Hu, G. Chen, Q. Li, F. Zhang, and Y. Liu (2025) Towards reward fairness in rlhf: from a resource allocation perspective. arXiv preprint. Cited by: §1. K. Park, Y. J. Choe, and V. Veitch (2024) The linear representation hypothesis and the geometry of large language models. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. Cited by: §1. K. Pearson (1936) Method of moments and method of maximum likelihood. Biometrika 28 (1/2), p. 34–59. Cited by: §1.2. Y. Plan and R. Vershynin (2013) One-bit compressed sensing by linear programming. Communications on pure and Applied Mathematics 66 (8), p. 1275–1297. Cited by: §1.2. K. Schmüdgen (2017) The moment problem. Vol. 9, Springer. Cited by: §3.3. J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov (2017) Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. Cited by: §1. A. Shirali, A. Nasr-Esfahany, A. Alomar, P. Mirtaheri, R. Abebe, and A. Procaccia (2025) Direct alignment with heterogeneous preferences. arXiv preprint arXiv:2502.16320. Cited by: §1.2. A. Siththaranjan, C. Laidlaw, and D. Hadfield-Menell (2024) Distributional preference learning: understanding and accounting for hidden context in rlhf. Neurips. Cited by: §1.2. T. Sorensen, J. Moore, J. Fisher, M. Gordon, N. Mireshghallah, C. M. Rytting, A. Ye, L. Jiang, X. Lu, N. Dziri, et al. (2024) A roadmap to pluralistic alignment. arXiv preprint arXiv:2402.05070. Cited by: §5.2. N. Stiennon, L. Ouyang, J. Wu, D. M. Ziegler, C. V. Ryan Lowe, A. Radford, D. Amodei, and P. Christiano (2020) Learning to summarize with human feedback. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1. J. A. Tropp (2012) User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics 12 (4), p. 389–434. External Links: Document, Link Cited by: §4.2. M. Wang, K. D. Duc, J. Fischer, and Y. S. Song (2017) Operator norm inequalities between tensor unfoldings on the partition lattice. Linear algebra and its applications 520, p. 44–66. Cited by: Lemma 4.5. J. G. Wendel (1948) Note on the gamma function. The American Mathematical Monthly 55 (9), p. 563. Cited by: §3.1. Appendix A Notation Reference Symbol Description d−1S^d-1 The unit sphere in ℝdR^d σ¯ σ Uniform probability measure (normalized surface area measure) on d−1S^d-1 Θ The underlying population distribution of voter types over d−1S^d-1 x∈,y∈x ,y Prompts and Responses Φ(x,y) (x,y) or ϕφ Embedding vector of a candidate (or prompt-response pair) uθ(ϕ)u_θ(φ) Utility of voter θ for candidate ϕφ, given by θ⋅ϕθ·φ q Pairwise comparison query vector (difference of embeddings q≔ϕ1−ϕ2q _1- _2) respθ(q)resp_θ(q) Binary response of voter θ to query q (e.g., θ⋅q≥0 1\θ· q≥ 0\) gradθ(q)grad_θ(q) Binary response of voter θ to query q (e.g., θ⋅q≥τ 1\θ· q≥τ\) Qk(;Θ)Q_k( q; ) or Qk()Q_k( q) Probability that a random voter θ∼Θθ responds positively to all queries q Gτ(;Θ)G_τ( q; ) or Gτ()G_τ( q) Probability that a random voter θ∼Θθ has strong preference to q cdc_d The constant from the first moment identity (see Equation 1) ZkZ_k The set of τ∈(0,1)τ∈(0,1) for which GτG_τ fails to identify MkM_k Table 1: Notation used throughout this work. Appendix B Spherical Harmonics Basics A spherical harmonic of degree j is the restriction to d−1S^d-1 of a degree-j homogeneous polynomial whose Laplacian Δ≔∑i=1d∂i2 _i=1^d _i^2 vanishes. Spherical harmonics arise naturally in our analysis because the distributions we study are supported on the sphere, and moment functionals correspond to homogeneous polynomials. There are many excellent references on spherical harmonics, including the classical text Groemer [1996] and the more recent Dai and Xu [2013]; we refer interested readers to these sources for further background. Spherical harmonics enjoy many useful properties, including orthogonality and an L2L^2-decomposition into harmonic subspaces. The main tool deferred from the main text is the classic Funk–Hecke formula, which dates back to the work of Funk [1915] and Hecke [1917]. Theorem B.1 (Funk-Hecke Theorem). Suppose d≥2d≥ 2 and let Y∈ℋjY _j, x∈d−1x ^d-1, K is bounded. Then, for all y∈d−1y ^d-1, ∫Sd−1K(x⋅y)Y(x)σ(x)=μj⋅Y(y) _S^d-1K(x· y)Y(x)\;dσ(x)= _j· Y(y) where μj=Γ(d2)πΓ(d−12)∫−11Pj(t)K(t)(1−t2)d−32t _j= ( d2) π ( d-12) _-1^1P_j(t)K(t)(1-t^2) d-32dt, where PjP_j being the j-th Gegenbauer polynomial with parameter d−22 d-22. Gegenbauer polynomials form a classical family of orthogonal polynomials on [−1,1][-1,1] and are closely connected to spherical harmonics. In the main text, we use the basic parity property: the polynomial is even when j is even and odd when j is odd. Further background and properties can be found in Appendix B of Dai and Xu [2013]. Appendix C Omitted Results and Proofs C.1 Proof of Observation 3.5 Proof. Having the same k-th moment tensor is the same as having same expected values for each monomials of degree k, and if the two distribution have the same first k moments, for any polynomial with degree less or equal to k, their expected values over the distributions will also be the same by the linearity of the expected values. Let σ denote the uniform probability measure on d−1S^d-1. By Axler et al. [2001][Proposition 5.9] for any polynomial p and any homogeneous harmonic polynomial q on ℝdR^d satisfying deg(q)>deg(p) (q)> (p), ∫d−1p(x)q(x)σ(x)=0. _S^d-1p(x)\,q(x)\,dσ(x)=0. Choose any nonzero homogeneous harmonic polynomial of degree k+1k+1; for instance h(x)=ℜ((x1+ix2)k+1),h(x)= ((x_1+ix_2)^k+1 ), where x1,x2x_1,x_2 are the first and second coordinates of the vector x and ℜ represents the real part of a complex number. By the mean value property of a harmonic function, ∫h(x)σ(x)=h(0)=0 h(x)dσ(x)=h(0)=0. Thus we are able to define dμ±(x)=(1±εh(x))dσ(x)d _±(x)=(1± h(x))\,dσ(x) for some sufficiently ε>0 >0 such that 1±εh(x)≥0for all x∈d−1.1± h(x)≥ 0 all x ^d-1. Let xαx^α be a monomial with |α|≤k|α|≤ k. Applying Proposition 5.9 with p(x)=xαp(x)=x^α and q(x)=h(x)q(x)=h(x) gives ∫Sd−1xα(x)h(x)σ(x)=0, _S^d-1x^α(x)\,h(x)\,dσ(x)=0, since deg(h)=k+1>|α|=deg(p) (h)=k+1>|α|= (p). Hence ∫xαμ+−∫xαμ−=2ε∫Sd−1xα(x)h(x)σ(x)=0, x^α\,d _+- x^α\,d _-=2 _S^d-1x^α(x)\,h(x)\,dσ(x)=0, so all moments up to order k agree. Because h is not identically zero, ∫Sd−1h(x)2σ(x)>0. _S^d-1h(x)^2\,dσ(x)>0. Thus ∫hμ+−∫hμ−=2ε∫Sd−1h(x)2σ(x)≠0. h\,d _+- h\,d _-=2 _S^d-1h(x)^2\,dσ(x)≠ 0. Since h is a homogeneous polynomial of degree k+1k+1, this implies that the (k+1)(k+1)-st moments of μ+ _+ and μ− _- differ. ∎ C.2 Proof of Lemma 3.7 Sketch. Proofs of this sort proceed generally in three steps. The first is to argue that the moment tensor MkM_k for a distribution μ suffices to compute the expectation μ[p(x)]E_μ [p(x) ] of any homogeneous degree-k polynomial p on d−1S^d-1. The second step is invoke the Stone-Weierstrass theorem for d−1S^d-1, which says that the set of polynomials is dense in the larger space of continuous functions C(d−1)C(S^d-1). Here density means uniform convergence; for all continuous f∈C(d−1)f∈ C(S^d-1) there is a sequence of polynomials which converges to it in ‖f−p‖∞=maxx∈d−1|f(x)−p(x)| \|f-p \|_∞= _x ^d-1 f(x)-p(x) . This is quite strong, and it is possible because the domain is compact. The last step is to invoke the Riesz-Markov-Kakutani representation theorem, which states that any two measures that agree on all continuous functions [f(x)]E [f(x) ] are in fact the same. Since the polynomials are dense in C(d−1)C(S^d-1), if μ and μ′μ agree on their moments (and therefore on [p(x)]E [p(x) ] for all polynomials), then μ[f(x)]=μ′[f(x)]E_μ [f(x) ]=E_μ [f(x) ] for all continuous f and so this representation theorem applies. ∎ C.3 Proof of Theorem 3.9 To prove Theorem 3.9, we need the following lemma. For a fixed voter direction θ∈d−1θ ^d-1, consider its contribution Ik,τ(θ)=∫d−1θ⊤q≥τq⊗kσ¯(q).I_k,τ(θ)= _S^d-1 1\θ q≥τ\\,q k\,d σ(q). Lemma C.1. Let d≥2d≥ 2, k≥1k≥ 1, for any θ∈d−1θ ^d-1, it holds that Ik,τ(θ)=∑j=0⌊k/2⌋λk,jSym(θ⊗(k−2j)⊗I⊗j),I_k,τ(θ)= _j=0 k/2 _k,j\,Sym (θ (k-2j) I j ), where the constants λk,0,…,λk,⌊k/2⌋ _k,0,…, _k, k/2 depend on τ,d,kτ,d,k, I is the rank-2 identity tensor (i.e. matrix) on ℝdR^d, and SymSym denotes full symmetrization over all indices. Proof. Let x∈ℝdx ^d be an arbitrary vector. We define the scalar polynomial p(x)p(x) by contracting Ik,τ(θ)I_k,τ(θ) with k copies of x: p(x)≔⟨Ik(θ),x⊗k⟩=⟨∫d−1θ⊤q≥τq⊗kσ(q),x⊗k⟩.p(x) I_k(θ),x k = _S^d-1 1\θ q≥τ\\,q k\,dσ(q),\;x k . As ⟨q⊗k,x⊗k⟩=(⟨q,x⟩)k q k,x k =( q,x )^k, we have: p(x)=∫d−1θ⊤q≥τ(q⊤x)kσ(q).p(x)= _S^d-1 1\θ q≥τ\\,\,(q x)^k\,dσ(q). Let O(d)O(d) denote the orthogonal group acting on ℝdR^d. Consider the stabilizer subgroup of θ, denoted ℛθR_θ. For R∈ℛθR _θ: p(Rx)=∫d−1θ⊤q≥τ(q⊤Rx)kσ(q).p(Rx)= _S^d-1 1\θ q≥τ\\,\,(q Rx)^k\,dσ(q). Now let u=R⊤qu=R q. Since R is orthogonal, the measure is invariant, so dσ(q)=dσ(u)dσ(q)=dσ(u). Furthermore, θ⊤q=θ⊤(Ru)=(R⊤θ)⊤u=θ⊤u.θ q=θ (Ru)=(R θ) u=θ u. Substituting these back into the integral: p(Rx)=∫d−1θ⊤u≥τ(u⊤Rx)kσ(u)=p(x).p(Rx)= _S^d-1 1\θ u≥τ\\,\,(u Rx)^k\,dσ(u)=p(x). Thus, P(x)P(x) is a polynomial in x that is invariant under all rotations about the axis θ. Therefore, p(x)p(x) must be of the form: p(x)=F(⟨x,θ⟩,|x|2).p(x)=F( x,θ ,|x|^2). Since p(x)p(x) is defined by an integral of (q⊤x)k(q x)^k, p(x)p(x) is a homogeneous polynomial of degree k in x. Consequently, F must be a linear combination of terms of the form (⟨x,θ⟩)a(|x|2)b( x,θ )^a(|x|^2)^b such that the total degree matches k: a+2b=k.a+2b=k. Since a,ba,b must be non-negative integers, let b=jb=j. Then a=k−2ja=k-2j. The possible values for j are integers satisfying 0≤2j≤k0≤ 2j≤ k, i.e., 0≤j≤⌊k/2⌋0≤ j≤ k/2 . Thus, there exist scalar constants λk,j _k,j such that: p(x)=∑j=0⌊k/2⌋λk,j(⟨x,θ⟩)k−2j(|x|2)j.p(x)= _j=0 k/2 _k,j\,( x,θ )^k-2j(|x|^2)^j. (7) We now map the scalar terms back to their tensor equivalents. • The term (⟨x,θ⟩)k−2j( x,θ )^k-2j corresponds to the contraction of the rank-(k−2j)(k-2j) tensor θ⊗(k−2j)θ (k-2j) with x⊗(k−2j)x (k-2j). • The term |x|2j=(⟨x,Ix⟩)j|x|^2j=( x,Ix )^j corresponds to the contraction of j copies of the identity matrix, I⊗jI j, with x⊗2jx 2j. The product corresponds to the tensor product θ⊗(k−2j)⊗I⊗jθ (k-2j) I j contracted with x⊗kx k. However, the original tensor Ik,τ(θ)I_k,τ(θ) is fully symmetric, while the tensor product θ⊗(k−2j)⊗I⊗jθ (k-2j) I j is not. Since the equality holds for all x, the symmetric tensors associated with the polynomials must be equal. Finally, we apply the symmetrization operator SymSym to the basis tensors: Ik,τ(θ)=∑j=0⌊k/2⌋λk,jSym(θ⊗(k−2j)⊗I⊗j).I_k,τ(θ)= _j=0 k/2 _k,j\,Sym (θ (k-2j) I j ). ∎ Proof of Theorem 3.9. We first show that all moments are identifiable through induction on k. Let k≥1k≥ 1 be fixed and assume that all moments θ∼Θ[θ⊗ℓ]E_θ [θ ] for ℓ<k <k are known. Now by Lemma C.1 and Fubini’s swap, Tk,τ≔ T_k,τ ∫d−1Gτ(q)q⊗kσ¯(q) _S^d-1G_τ(q)\,q k\,d σ(q) = = ∫d−1(∫d−1(θ⊤q≥τ)q⊗kσ¯(q))Θ(θ) _S^d-1 ( _S^d-11(θ q≥τ)\,q k\,d σ(q) )d (θ) = = θ∼Θ[Ik,τ(θ)] _θ [I_k,τ(θ)] = = λk,0(τ)[θ⊗k]+∑j=1⌊k/2⌋λk,j(τ)Sym(θ∼Θ[θ⊗(k−2j)]⊗I⊗j), _k,0(τ)\,E[θ k]+ _j=1 k/2 _k,j(τ)\,Sym (E_θ [θ (k-2j)] I j ), The summation term involves only moments of order k−2,k−4,…k-2,k-4,…, which are known by the inductive hypothesis. Therefore, the kkth moment tensor [θ⊗k]E[θ k] is uniquely determined if and only if the coefficient λk,0(τ) _k,0(τ) is non-zero. To rigorously determine λk,0(τ) _k,0(τ), we utilize spherical harmonics again. First, for a fixed x, the homogeneous polynomial f(q)=(qTx)kf(q)=(q^Tx)^k can be decomposed as a sum of spherical harmonics of degree k,k−2,…k,k-2,…: f(q)=∑j=0⌊k/2⌋|x|2jYk−2j(q)f(q)= _j=0 k/2 |x|^2jY_k-2j(q). Now applying the linearity of the integral and the Funk-Hecke Theorem (see Theorem B.1 in Appendix C), we have that p(x)=∑j=0⌊k/2⌋μk−2j|x|2jYk−2j(θ).p(x)= _j=0 k/2 _k-2j\,|x|^2jY_k-2j(θ). Comparing this with Equation (7), we see that μk=λk,0. _k= _k,0. Thus λk,0(τ)=Γ(d2)πΓ(d−12)∫τ1Pk(t)(1−t2)d−32t, _k,0(τ)= ( d2) π ( d-12) _τ^1P_k(t)(1-t^2) d-32dt, (8) where PkP_k is the Gegenbauer polynomial with parameter d−22 d-22. Note that the derivative of λk,0(τ) _k,0(τ) (specifically, Pk(t)P_k(t)) has k distinct roots on (−1,1)(-1,1), and ⌊k/2⌋ k/2 on (0,1)(0,1) by symmetry. So λk,0(τ) _k,0(τ) has ⌊k/2⌋ k/2 stationary points. Now consider the boundary points for λk,0(τ) _k,0(τ). Clearly, λk,0(1)=0 _k,0(1)=0 .When τ=0τ=0 and k is even, both Pk,d(t)P_k,d(t) and (1−t2)(d−3)/2(1-t^2)^(d-3)/2 are even and due to the orthogonality of Gegenbauer polynomials with parameter d−22 d-22, ∫01Pk(t)(1−t2)(d−3)/2=12∫−11Pk(t)⋅1⋅(1−t2)(d−3)/2=0 _0^1P_k(t)(1-t^2)^(d-3)/2= 12 _-1^1P_k(t)· 1·(1-t^2)^(d-3)/2=0, so λk,0(τ)=0 _k,0(τ)=0 and the function has one less interior zero. Hence the number of roots of the function λk,0(τ) _k,0(τ) is ⌊k−12⌋ k-12 . And Zk≔τ∈(0,1):λk,0(τ)=0Z_k \τ∈(0,1): _k,0(τ)=0\ must be discrete. Thus, for any τ∉Zkτ∉ Z_k, we can solve for the kkth moment: [θ⊗k]=1λk,0(τ)(Tk,τ−∑j=1⌊k/2⌋λk,j(τ)Sym([θ⊗(k−2j)]⊗I⊗j))E[θ k]= 1 _k,0(τ) (T_k,τ- _j=1 k/2 _k,j(τ)\,Sym (E[θ (k-2j)] I j ) ) Now since the set ⋃k≥1Zk _k≥ 1Z_k is countable, and has measure zero on (0,1)(0,1), for almost every τ∈(0,1)τ∈(0,1), all moments are identifiable with GτG_τ. Lemma 3.7 then implies that distributions are identifiable. ∎ C.4 Proof of Theorem 4.6 Proof. Fix odd ℓ and let i1…,iℓi_1…,i_ be a sequence of indices. Let p(θ)=θi1⋅⋯⋅θiℓp(θ)= _i_1·s· _i_ . Recall, from the proof of Theorem 3.8, there are spherical harmonics fjf_j for odd j≤ℓj≤ such that p(θ)=∑j≤ℓ:j is oddfj(θ)p(θ)= _j≤ :j is oddf_j(θ). However, we did not give an explicit construction of them. It turns out, that finding them is possible. The primary property we need is that in our case, |fj(θ)|≤dj/2|f_j(θ)|≤ d^j/2 for all θ∈d−1θ ^d-1. We encapsulate this into the following lemma, whose proof we differ until later: Lemma C.2. Let p(x)=xi1xi2…xiℓp(x)=x_i_1x_i_2… x_i_ be a monomial of degree ℓ in ℝdR^d. Let fj∈jdf_j _j^d denote the j-th spherical harmonic component of the restriction of p(x)p(x) to the unit sphere d−1S^d-1. Then, |fj(x)|≤dj/2|f_j(x)|≤ d^j/2 for all x∈d−1x ^d-1. Proof of Lemma C.2. The key tool we will need is the projection operator as a way to determine the j’th spherical harmonic in the decomposition. Atkinson and Han [2012, Definition 2.11] call this function j,df)P_j,df). The only property we will need is Equation (2.49) which shows that ‖j,df‖C(d−1)≤Nj,d1/2‖f‖C(d−1).\|P_j,df\|_C(S^d-1)≤ N^1/2_j,d\|f\|_C(S^d-1). where, by Equation (2.10), Nj,d=(j+d−1j)−(j+d−3j−2)N_j,d= j+d-1j- j+d-3j-2 and, ∥g∥C(d−1)=sup|g(ξ)|:ξ∈d−1\|g\|_C(S^d-1)= \|g(ξ)|:ξ ^d-1\ (see Section 1.3). Note that trivially Nj,d≤(j+d−1j)=j+d−1j⋅⋯⋅d+1−11≤dj.N_j,d≤ j+d-1j= j+d-1j·s· d+1-11≤ d^j. Plugging in our monomial, note that on d−1S^d-1, each coordinate |θi|≤1| _i|≤ 1, therefore, |p(θ)|≤1|p(θ)|≤ 1. Combining these yields the lemma statement. ∎ Next, we also need an explicit construction of λj _j. From Groemer [1996, Lemma 3.4.6], using our normalized measure dσ¯d σ, this is given by λj=(−1)(d−1)/21d⋅1⋅3⋅⋯⋅(j−2)(d+1)(d+3)⋯(d+j−2). _j=(-1)^(d-1)/2 1d· 1· 3·s·(j-2)(d+1)(d+3)·s(d+j-2). For our purposes, we will lower bound |λj|≥(d+1)−(j+1)/2| _j|≥(d+1)^-(j+1)/2. Combining these, we see that |∑j≤ℓ:j is odd1λjfj(θ)|≤∑j≤ℓ:j is odd(d+1)j+1/2≤2(d+1)ℓ+1/2. | _j≤ :j is odd 1 _jf_j(θ) |≤ _j≤ :j is odd(d+1)^j+1/2≤ 2(d+1) +1/2. (9) Now we will apply this to our concentration inequalities. We start with odd k. We will work with the matricized form where the entire [k][k] is on one side, so this is essentially a dk×1d^k× 1 sized vector. Define Ψk(q) ^k(q) as the matricized vector where for a each index sequence α=i1…ikα=i_1… i_k, Ψk(q,b)α=b⋅∑j≤k:j is odd1λjfjα(q) ^k(q,b)_α=b· _j≤ k:j is odd 1 _jf^α_j(q) where fjαf^α_j is the spherical harmonic of degree j in the decomposition of the monomial corresponding to α. As we showed, q∼σ¯,θ∼Θ[Ψk(q,respθ(q))α]E_q σ,θ [ ^k(q,resp_θ(q))_α ] is the α entry of MkM_k. Thus, we will set our estimator M^k M_k to be the unmatricized version of 1T∑i=1TΨk(qi,respθi(qi)) 1T _i=1^T ^k(q^i,resp_ _i(q^i)) where qiq^i is the i’th sampled query and respθi(qi)resp_ _i(q^i) is the response of the sampled voter θi _i. We would like to apply Matrix Bernstein to this. By Inequality (9), each entry of Ψk(qi,respθi(qi)) ^k(q_i,resp_ _i(q_i)) is bounded by 2(d+1)k+1/22(d+1)^k+1/2. The expected value must also lie in [−2(d+1)k+1/2,2(d+1)k+1/2][-2(d+1)^k+1/2,2(d+1)^k+1/2], and thus the maximum distance from the expected value is at most 4(d+1)k+1/24(d+1)^k+1/2. As there are dkd^k entries, the L2L_2 norm (equivalent to the operator norm for vectors) is upper bounded by dk/2⋅4(d+1)k+1/2≤4(d+1)(3k+1)/2d^k/2· 4(d+1)^k+1/2≤ 4(d+1)^(3k+1)/2. As for the variance bound, note that for a vector v, both ‖v⊤v‖\|v v\| and ‖vv⊤‖\|v \| are bounded by ‖v‖22\|v\|_2^2. Thus, we can upperbound this by 16(d+1)3k+116(d+1)^3k+1. Plugging this into matrix Bernstein, we get T≥2ε2(16(d+1)3k+1+4(d+1)(3k+1)/2ε3)log(dk+1δ)=O((d+1)3k+1ε2log(dkδ)).T≥ 2 ^2 (16(d+1)^3k+1+ 4(d+1)^(3k+1)/2 3 ) ( d^k+1δ )=O ( (d+1)^3k+1 ^2 ( d^kδ ) ). Next, consider even k. Let s=k/2−1s=k/2-1. We will matricize such that |I|=s|I|=s and |J|=k−s|J|=k-s. In particular, we will set our estimator M^k M_k to be the unmatricized version of 1T∑i=1TΨs(q1i,respθi(q1i))⊤Ψk−s(q2i,respθi(q2i). 1T _i=1^T ^s(q^i_1,resp_ _i(q^i_1)) ^k-s(q^i_2,resp_ _i(q^i_2). Let α be a sequence of indices and let αsα^s and αk−sα^k-s be its first s and last k−sk-s indices collectively. The (αs,αk−s)(α^s,α^k-s) entry of this outer product (which corresponds to α) will have expectation (by linearity) exactly the moment corresponding to α. We now apply matrix Berstein on these. Note that the individual Φs ^s and Φk−s ^k-s have terms bounded by (d+1)s+1/2(d+1)^s+1/2 and (d+1)(k−s)+1/2(d+1)^(k-s)+1/2 respectively. Thus, the distance each term is from the expectation is at most 2(d+1)s+1/22(d+1)^s+1/2 and 2(d+1)(k−s)+1/22(d+1)^(k-s)+1/2, respectively. Hence, their L2L_2 norms are at most 2(d+1)2s+1/22(d+1)^2s+1/2 and 2(d+1)2(k−s)+1/22(d+1)^2(k-s)+1/2, respectively. Therefore, the spectral norm of their outer product is at most 2(d+1)2k+12(d+1)^2k+1. Next, we consider the variance. In general, we have two vectors u and v of dimensions n and n′n and entries bounded by L and L′L , respectively, then ‖(u⊤v)⊤(u⊤v)‖\|(u v) (u v)\| and ‖(u⊤v)(u⊤v)⊤‖\|(u v)(u v) \| are bounded by n⋅n′⋅L2⋅(L′)2n· n · L^2·(L )^2. Plugging this in for use, we have a bound of ds⋅dk−s⋅(2(d+1)s+1/2)2(2(d+1)k−s+1/2)2≤16(d+1)3k+2d^s· d^k-s·(2(d+1)^s+1/2)^2(2(d+1)^k-s+1/2)^2≤ 16(d+1)^3k+2. Plugging this into matrix Berstein, we get T≥2ε2(16(d+1)3k+2+4(d+1)(3k+2)/2ε3)log(dk/2+1+dk/2−1δ)=O((d+1)3k+2ε2log(dkδ)).∎T≥ 2 ^2 (16(d+1)^3k+2+ 4(d+1)^(3k+2)/2 3 ) ( d^k/2+1+d^k/2-1δ )=O ( (d+1)^3k+2 ^2 ( d^kδ ) ). C.5 Proof of Proposition 5.1 . By Theorem 4.2, T samples suffice to estimate the first moment M1M_1 such that ‖M^1−M1‖op≤ε\| M_1-M_1\|_op≤ . The estimated welfare for any candidate ϕφ is ⟨M^1,ϕ⟩ M_1,φ . The estimation error is |⟨M^1−M1,ϕ⟩|≤‖M^1−M1‖op‖ϕ‖≤εB| M_1-M_1,φ |≤\| M_1-M_1\|_op\|φ\|≤ B. If we select the candidate maximizing the estimated welfare, the true welfare of the selected candidate is at most 2εB2 B suboptimal. ∎ C.6 Proof of Proposition 5.2 Proof. It is without loss of generality to assume ε≤1 ≤ 1, as the 0-tensor is a trivial 1-approximation since ‖Mk‖≤1\|M_k\|≤ 1. Using Theorem 4.3 with k=2k=2, we obtain estimates M^1 M_1 and M^2 M_2 such that ‖M^1−M1‖≤ε\| M_1-M_1\|≤ and ‖M^2−M2‖≤ε\| M_2-M_2\|≤ . Recall that rawα(ϕ)=M1⊤ϕ−αϕ⊤M2ϕ−(M1⊤ϕ)2 raw_α(φ)=M_1 φ-α φ M_2φ-(M_1 φ)^2. Let μ=M1⊤ϕμ=M_1 φ and μ^=M^1⊤ϕ μ= M_1 φ. Similarly, let σ2=ϕ⊤M2ϕ−μ2σ^2=φ M_2φ-μ^2 and σ^2=ϕ⊤M^2ϕ−μ^2 σ^2=φ M_2φ- μ^2. We have |μ^−μ|≤εB| μ-μ|≤ B and |ϕ⊤(M^2−M2)ϕ|≤εB2|φ ( M_2-M_2)φ|≤ B^2. The error in the variance term is bounded by: |σ^2−σ2|≤εB2+|μ^2−μ2|≤εB2+2B(εB)≤3εB2.| σ^2-σ^2|≤ B^2+| μ^2-μ^2|≤ B^2+2B( B)≤ 3 B^2. Using the fact that |x−y|≤|x−y|| x- y|≤ |x-y|, the error in the standard deviation is bounded by 3εB 3 B. Thus, the total estimation error is bounded by εB+α3εB≤3⋅(α+1)Bε B+α 3 B≤ 3·(α+1)B because ε≤1 ≤ 1. If we select the candidate maximizing estimated risk-adjusted welfare, the true risk-adjusted welfare of the selected candidate is at most double. ∎ C.7 Missing Portion of Proof of Theorem 5.3 Here we derive (5). Recall that we will make use of the identity [Gradshteyn and Ryzhik, 2014, Equation 1.514] log(1−2αcos(φ)+α2)=−2∑j=1∞cos(jφ)j⋅αj, (1-2α ( )+α^2)=-2 _j=1^∞ (j )j·α^j, for α2≤1α^2≤ 1 and αcos(φ)≠1α ( )≠ 1. Our goal is to show that log(1+δt)=−2∑j=1∞αj⋅Tj(t), (1+δ t)=-2 _j=1^∞ α^jj· T_j(t), where δ=r−1r+1δ= r-1r+1. As long as |α|<1|α|<1, for real φ , αcos(φ)≠1α ( )≠ 1. By our definition of Chebyshev polynomials, this implies that for t∈[−1,1]t∈[-1,1], log(1−2αt+α2)=−2∑j=1∞αj⋅Tj(t). (1-2α t+α^2)=-2 _j=1^∞ α^jj· T_j(t). To get it in our form, we can normalize by 1+α21+α^2 to get log(1+−2α1+α2t)=−log(1+α2)−2∑j=1∞αj⋅Tj(t). (1+ -2α1+α^2t )=- (1+α^2)-2 _j=1^∞ α^jj· T_j(t). We will set α=−r−1r+1α=- r-1 r+1, which clearly has |α|<1|α|<1 and yields −2α1+α2=2⋅r−1r+11+(r−1r+1)2=2⋅r−1r+12(r+1)(r+1)2=(r−1)(r+1)r+1=r−1r+1=δ. -2α1+α^2= 2· r-1 r+11+ ( r-1 r+1 )^2= 2· r-1 r+1 2(r+1)( r+1)^2= ( r-1)( r+1)r+1= r-1r+1=δ. First, observe that α2<1α^2<1. This also implies that αcos(φ)≠1α ( )≠ 1 for real φ . Thus, for t∈[−1,1]t∈[-1,1], log(1+δ)=log(1−2αx+α2)=−2∑j=1∞αj⋅Tj(x).∎ (1+δ)= (1-2α x+α^2)=-2 _j=1^∞ α^jj· T_j(x). C.8 Proof of Theorem 5.4 We now prove a key general result which shows that any (welfare) function that is Lipschitz continuous can be approximated using the first k moments. This result relies on the following lemma, which can be understood as a counterpart to Observation 3.5. It quantifies the extent to which two measures that agree on their first k moments can substantively differ. Here the difference between distributions μ and ν is measured according to the 1-Wasserstein distance, or earth-mover’s distance, given by W1(μ,ν)≔infγ∈Γ∬d−1×d−1‖θ−θ′‖2μ(θ)ν(θ′),W_1(μ,ν) _γ∈ _S^d-1×S^d-1 \|θ-θ \|_2\>dμ(θ)\>dν(θ ), where Γ=Γ(μ,ν) = (μ,ν) is the set of all statistical couplings of μ and ν. Lemma C.3 (Wasserstein Bound via Moment Matching). Let μ and ν be two probability measures on d−1⊂ℝdS^d-1 ^d. Suppose the first k moments of μ and ν are equal. Then the 1-Wasserstein distance satisfies W1(μ,ν)≤C⋅dk,W_1(μ,ν)≤ C· dk, where C>0C>0 is an absolute constant independent of the dimension d, the degree k, and the measures. Proof. We will use the fact that the 1-Wasserstein distance admits the following alternative definition via Kantorovich-Rubinstein duality: W1(μ,ν)=supf∈Lip(d−1)|∫d−1fμ−∫d−1fν|,W_1(μ,ν)= _f (S^d-1) | _S^d-1f\,dμ- _S^d-1f\,dν |, (10) where Lip(d−1)Lip(S^d-1) is the set of functions on d−1S^d-1 that are 1-Lipschitz with respect to L2L_2. For the purposes of this proof it will be more convenient to work with the geodesic distance, given by dg(θ,θ′)=arccos(⟨θ,θ′⟩)d_g(θ,θ )= ( θ,θ ) between θ,θ′∈d−1θ,θ ^d-1. They are equivalent for our purposes because ∥θ,θ′∥2≤dg(θ,θ′)≤π2∥θ,θ′∥2 \|θ,θ \|_2≤ d_g(θ,θ )≤ π2 \|θ,θ \|_2 on the unit sphere. To begin, fix f∈Lip(d−1)f (S^d-1). Our goal is to approximate f using a spherical polynomial Pk∈ΠkdP_k∈ _k^d, where Πkd _k^d denotes the space of all spherical polynomials of degree at most k. By the triangle inequality, |μ[f]−ν[f]| _μ [f ]-E_ν [f ] =|μ[f−Pk+Pk]−ν[f−Pk+Pk]| = _μ [f-P_k+P_k ]-E_ν [f-P_k+P_k ] ≤|μ[f−Pk]|+|ν[Pk]−μ[Pk]|+|ν[f−Pk]| ≤ _μ [f-P_k ] + _ν [P_k ]-E_μ [P_k ] + _ν [f-P_k ] ≤|μ[f−Pk]|+|ν[f−Pk]|. ≤ _μ [f-P_k ] + _ν [f-P_k ] . (11) This last step follows since [Pk]E [P_k ] can be written as a function of the at-most-k’th moments, which are equal for μ and ν by assumption. We will bound the remaining two terms by the uniform norm over d−1S^d-1. To this end, let Ek(f)≔minP∈Πkd‖f−P‖∞E_k(f) _P∈ _k^d \|f-P \|_∞ be the best possible uniform approximation to f achievable using degree-k polynomials. Choosing PkP_k to be the polynomial approximation of f witnessing this value, we have |μ[f−Pk]|≤∫d−1‖f−Pk‖∞μ=Ek(f), |E_μ [f-P_k ] |≤ _S^d-1\|f-P_k\|_∞\;dμ=E_k(f), (12) and likewise for ν. Therefore from (11) we have |μ[f]−ν[f]|≤2⋅Ek(f). _μ [f ]-E_ν [f ] ≤ 2· E_k(f). To bound Ek(f)E_k(f) we invoke the so-called Jackson theorem for the sphere, which relates the approximability of a function by polynomials to its smoothness. As established by Newman and Shapiro [1964] (see also [Chen et al., 2025, Lemma 41]), for any continuous function f, the approximation error is bounded by the modulus of continuity, which on d−1S^d-1 is given by ω(f,δ)∞≔supx,y:dg(x,y)≤δ|f(x)−f(y)|ω(f,δ)_∞ _x,y:\>d_g(x,y)≤δ f(x)-f(y) . In particular, it holds that Ek(f)≤CNS⋅ω(f,dk)∞E_k(f)≤ C_NS·ω (f, dk )_∞ (13) for some absolute constant CNSC_NS independent of the dimension d. Since f is 1-Lipschitz, its modulus of continuity satisfies ω(f,t)∞≤tω(f,t)_∞≤ t. Applying this to (13) and substituting it into (12) yields |μ[f−Pk]|≤2⋅CNS⋅dk. |E_μ [f-P_k ] |≤ 2· C_NS· dk. Taking the supremum over all 11-Lipschitz f, from (10) we finally have W1(μ,ν)≤2⋅CNS⋅dk.∎W_1(μ,ν)≤ 2· C_NS· dk. Now, we are ready to present the general result. We do not claim that the resulting dependence of the required number of moments on ε is optimal, opting instead for a readily generalizable approach. Lemma C.4. Let μ and ν be probability measures on the unit sphere d−1⊂ℝdS^d-1 ^d such that their first k moments match. For any L-Lipschitz function f:d−1→ℝf:S^d-1 , the integration error is bounded by |∫d−1fμ−∫d−1fν|≤C⋅L⋅dk, | _S^d-1f\,dμ- _S^d-1f\,dν |≤ C· L· dk, where C>0C>0 is an absolute constant independent of the dimension d. Proof. This follows directly from Lemma C.3. Given some L-Lipschitz f, observe that g≔f/Lg f/L is 1-Lipschitz. By the dual description of W1(μ,ν)W_1(μ,ν) (10), we therefore have |μ[g]−ν[g]|≤W1(μ,ν)≤2C⋅dk. |E_μ[g]-E_ν[g] |≤ W_1(μ,ν)≤ 2C· dk. Multiplying both sides by L, by linearity of expectation we obtain |μ[f]−ν[f]|≤2C⋅L⋅dk.∎ |E_μ[f]-E_ν[f] |≤ 2C· L· dk. We now use these lemmas to prove our main result on top-choice welfare. Proof of Theorem 5.4. This proof proceeds from Lemma C.4. We will apply it to the functions tcW(θ)≔maxϕ∈Wuθ(ϕ) tc_W(θ) _φ∈ Wu_θ(φ). Observe that in our model all such tcW(θ) tc_W(θ) are B-Lipschitz in θ, where B is an upper bound on ‖ϕ‖ \|φ \| for all ϕ∈Wφ∈ W. Given the moments M1,…,MkM_1,…,M_k of Θ , construct Θ to be an arbitrary distribution over d−1S^d-1 consistent with these moments and choose W^≔argmaxW∈ℓtcwΘ^(W) W _W _ tcw_ (W). Let W∗W^* be the (unknown) ℓ -tcw tcw optimum for Θ . Then letting ε′=C⋅B⋅dk =C· B· dk, by the optimality of Θ and applying Lemma C.4 twice we have tcwΘ(W^) tcw_ ( W) ≥tcwΘ^(W^)−ε′ ≥ tcw_ ( W)- ≥tcwΘ^(W∗)−ε′ ≥ tcw_ (W^*)- ≥tcwΘ(W∗)−2ε′ ≥ tcw_ (W^*)-2 Setting ε=2ε′ =2 and solving for k, we have k=2Bd/εk=2Bd/ , as claimed. ∎ Appendix D Extending to Stochastic Responses Instead of assuming voters respond deterministically with respθ(q)=θ⋅q≥0resp_θ(q)= 1\θ· q≥ 0\, we now allow responses to be stochastic. We consider the random utility model (RUM) Azari et al. [2012], which is a standard model in both social choice and alignment. Concretely, we can capture the stochasticity by introducing a generic function relating each single voter’s utility difference to their probability of response ψ:ℝ→[0,1]withψ(t)+ψ(−t)=1for all t∈ℝ.ψ:R→[0,1] ψ(t)+ψ(-t)=1 all t . Then, when presented with a comparison (x,y1,y2)(x,y_1,y_2), a voter responds 11 with probability ψ(uθ(x,y1)−uθ(x,y2))=ψ(θ⋅q)ψ(u_θ(x,y_1)-u_θ(x,y_2))=ψ(θ· q) for q=Ψ(x,y1)−Ψ(x,y2)q= (x,y_1)- (x,y_2). More formally, given a voter type θ, Pr[respθ(q)=1|θ]=ψ(θ⊤q). [resp_θ(q)=1|\ θ]=ψ(θ q). A common choice of the model is Bradley-Terry: ψBT(t)=11+exp(−t) _BT(t)= 11+ (-t). In general, we can now generalize multi-query responses for independent q1,…,qtq_1,…,q_t as Q~t()=Prθ∼Θ[[respθ(q1)=1]∧…∧[respθ(qt)=1]]=θ∼Θ[∏i=1tPr[respθ(qi)=1|θ]] Q_t( q)= _θ [[resp_θ(q_1)=1] … [resp_θ(q_t)=1] ]=E_θ [ _i=1^t [resp_θ(q_i)=1|\ θ] ] First, consider the problem of selecting a social-welfare–maximizing candidate. The first step of Lemma 3.2 requires rotational equivariance of inner-product–based responses. This argument continues to hold for the stochastic model, since for any rotation R we have ψ((Rθ)⊤q)=ψ(θ⊤(R−1q)).ψ((Rθ) q)=ψ(θ (R^-1q)). Lemma D.1. Let ψ:[−1,1]→[0,1]ψ:[-1,1]→[0,1], and θ∈d−1θ ^d-1 be fixed. Then Iψ(θ)≔∫d−1ψ(θ⊤q)qσ¯(q)=cd(ψ)θ,I_ψ(θ) _S^d-1ψ(θ q)\,q\,d σ(q)=c_d(ψ)\ θ, where the scalar cd(ψ)c_d(ψ) is given by cd(ψ)=Γ(d2)πΓ(d−12)∫−11ψ(t)t(1−t2)d−32tc_d(ψ)= \! ( d2 ) π\, \! ( d-12 ) _-1^1ψ(t)\,t\,(1-t^2) d-32\,dt Proof. Let R be any rotation in ℝdR^d. Because ⟨Rθ,Rq⟩=⟨θ,q⟩ Rθ,Rq = θ,q and dσ¯d σ is rotation equivariant, Iψ(Rθ)=∫ψ(⟨Rθ,q⟩)qσ¯(q)=∫ψ(⟨θ,R−1q⟩)qσ¯(q)=R∫ψ(⟨θ,u⟩)uσ¯(u)=RIψ(θ).I_ψ(Rθ)= ψ( Rθ,q )\,q\,d σ(q)= ψ( θ,R^-1q )\,q\,d σ(q)=R ψ( θ,u )\,u\,d σ(u)=R\,I_ψ(θ). Let ℛθR_θ be the group of rotations that keep θ fixed. For any R∈ℛθR _θ, we have Rθ=θRθ=θ, and therefore by the equivariance established above, RIψ(θ)=Iψ(Rθ)=Iψ(θ).R\,I_ψ(θ)=Iψ(Rθ)=I_ψ(θ). Hence Iψ(θ)I_ψ(θ) is the fixed point of the linear action of the group ℛθR_θ. However, as ℛθR_θ is acting as the full rotation group on the orthogonal complement of θ, the only fixed point in θ⟂θ is the zero vector, and the only dimension left is for the span of the vector itself: Iψ(θ)=cd(ψ)θ+0, for some scalar cd(ψ).I_ψ(θ)=c_d(ψ)\,θ+0, for some scalar c_d(ψ). Now to calculate the constant, we set θ=edθ=e_d. Then cd(ψ) c_d(ψ) =∫d−1ψ(qd)qdσ¯(q) = _S^d-1ψ(q_d)\,q_d\,d σ(q) =Γ(d2)πΓ(d−12)∫−11ψ(t)t(1−t2)d−32t. = \! ( d2 ) π\, \! ( d-12 ) _-1^1ψ(t)\,t\,(1-t^2) d-32\,dt. ∎ Observation D.2. To improve the signal-to-noise ratio in our moment estimators, we would like cd(ψ)c_d(ψ) to be as big as possible. Given that ψ(x)+ψ(−x)=1ψ(x)+ψ(-x)=1, ∫−11ψ(t)t(1−t2)d−32t _-1^1ψ(t)\,t\,(1-t^2) d-32\,dt =∫01ψ(t)t(1−t2)d−32t+∫−10ψ(t)t(1−t2)d−32t = _0^1ψ(t)\,t\,(1-t^2) d-32\,dt+ _-1^0ψ(t)\,t\,(1-t^2) d-32\,dt =∫01ψ(t)t(1−t2)d−32t+∫−10(1−ψ(−t))t(1−t2)d−32t = _0^1ψ(t)\,t\,(1-t^2) d-32\,dt+ _-1^0(1-ψ(-t))\,t\,(1-t^2) d-32\,dt =∫01[2ψ(t)−1]t(1−t2)d−32t = _0^1[2ψ(t)-1]\,t\,(1-t^2) d-32dt Since t(1−t2)d−32t\,(1-t^2) d-32 is always nonnegative on [0,1][0,1], maximizing cdc_d is the same as maximizing ψ(t)ψ(t) point-wise on t∈(0,1],t∈(0,1], which indicates that the more deterministic the preference is, the stronger is the signal. The remainders of the proofs for Lemma 3.3 and Theorem 3.4 carry over without modification. Theorem D.3. The welfare-maximizing candidate is identifiable from Q~1 Q_1. And since we can draw i.i.d. voters from the distribution Θ , Q~1 Q_1 can be estimated as before. Next, consider the task of estimating higher moments. Theorem 3.6 can be extended due to Lemma D.1. Theorem D.4. The kkth moment MkM_k is identifiable with Q~k Q_k. And due to the properties of spherical harmonics including Funk-Hecke (Theorem B.1), Theorem D.5. Distributions are identifiable with Q~2 Q_2.