The Surprising Effectiveness of SP Voting with Partial Preferences

Authors: hadi  hosseini
debmalya  mandal
amrit  puhan
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 17:24:16

Abstract: We consider the problem of recovering the ground truth ordering (ranking, top-$k$, or others) over a large number of alternatives. 
The wisdom of crowd is a heuristic approach based on Condorcet's Jury theorem to address this problem through collective opinions.
This approach fails to recover the ground truth when the majority of the crowd is misinformed. The \emph{surprisingly popular} (SP) algorithm~\citep{prelec2017solution} is an alternative approach that is able to recover the ground truth even when experts are in minority. The SP algorithm requires the voters to predict other voters' report in the form of a full probability distribution over all rankings of alternatives. However, when the number of alternatives, $m$, is large, eliciting the prediction report or even the vote over $m$ alternatives might be too costly. 
In this paper, we design a scalable alternative of the SP algorithm which only requires eliciting partial preferences from the voters, and propose new variants of the SP algorithm. In particular, we propose two versions---\emph{Aggregated-SP} and \emph{Partial-SP}---that ask voters to report vote and prediction on a subset of size $k$ ($\ll m$) in terms of top alternative, partial rank, or an approval set. Through a large-scale crowdsourcing experiment on MTurk, we show that both of our approaches outperform conventional preference aggregation algorithms for the recovery of ground truth rankings, when measured in terms of Kendall-Tau distance and Spearman's $\rho$. We further analyze the collected data and demonstrate that voters' behavior in the experiment, including the minority of the experts, and the SP phenomenon, can be correctly simulated by a  concentric mixtures of Mallows model. Finally, we provide theoretical bounds on the sample complexity of SP algorithms with partial rankings to demonstrate the theoretical guarantees of the proposed methods.

Main paper: 
 introduction: 
 The wisdom of the crowds is a systematic approach to statistically combine the opinions of a diverse group of (non-expert) individuals to achieve a final collective truth. It dates back to Sir Francis Galton's observation-based on Aristotle's hypothesis-that the point estimation of a continuous value using the noisy individual opinions can recover its true value with high accuracy [22] . In the modern era, the wisdom of the crowd has been the foundation of legal, political, and social systems with the premise that one can recover the truth by collecting the opinion of a large number of diverse individuals (e.g. trial by jury, election polling, and Q&A platforms such as Reddit/Quora).The formal arguments of this phenomenon-rooted in social choice theory-is provided by Condorcet's Jury Theorem [20] , which states that under the condition of independent opinions and each individual having more than a 50% chance of selecting the correct answer, the probability of the majority decision being correct increases as the size of the crowd increases. However, this approach may fail when the majority of the crowd are misinformed (less than 50% chance of selecting the correct answer) [19] or are systematically biased [46] . In other words, when the experts are in minority, simply aggregating individuals' opinions (regardless of the aggregation method) cannot recover the truth.To overcome this challenge, Prelec et al. [36] proposed a simple, yet effective, method called the Surprisingly Popular (SP) algorithm, which is able to uncover the ground truth even when the majority opinion is wrong. The approach works by asking each individual about their opinion (the vote) along with an additional meta-question to predict the majority opinion of other individuals (the prediction). The surprisingly popular algorithm then selects an answer whose actual frequency in the votes is greater than its average predicted frequency, and it will provably recover the correct answer with probability 1, as the number of individuals grows in the limit, even when experts are in minority.While the SP algorithm is effective in estimating a continuous value (e.g. the value of a painting) or a binary vote (e.g. "Is São Paulo the capital of Brazil?"), it cannot be directly applied to recover true ordinal rankings over a set of m alternatives due to the large number of votes (m!), and more importantly, eliciting predictions over a complete rankings. Hosseini et al. [25] extended this approach to rankings by proposing an algorithm, called Surprisingly Popular Voting, that can accurately recover the ground-truth ranking over multiple alternatives by eliciting a complete ranking as a vote and only a single majority prediction (as opposed to full probability distributions over m! rankings). 1Despite its success in finding the ground-truth ranking over a small number of alternatives, it remains unclear how to adapt it to settings with large number of alternatives where only partial preferences (e.g. pairwise comparisons or partial ranks) can be elicited. Thus, it raises the following questions:How can we design scalable algorithms based on the surprisingly popular method that recovers the ground truth only by eliciting partial preferences from voters? What elicitation formats and aggregation algorithms are more effective in recovering the full ranking over all alternatives?Our Contributions. We focus on developing methods, based on the surprisingly popular approach, that only elicit partial vote and prediction information to find the full ranking. Given a set of m alternatives, we ask individuals to provide their rank-ordered vote and predictions on a subset of size k (≪ m) of alternatives. Informally, we ask them to identify the most preferred alternative among the k choices (Top), select the t < k most preferred alternatives with no order (Approval(t)), or provide a rank-ordered list of all k alternatives (Rank). The precise formulation is provided in Section 2.1.Given that the SP algorithm [36] and its extension to rankings [25] do not generalize to partial preferences with large number of alternatives, we design two novel aggregation methods, namely Partial-SP and Aggregated-SP algorithms. On a high level, these algorithms use a carefully crafted method to select subsets of size k ≪ m for vote and prediction elicitation, and apply the SP method either independently on each subset (Partial-SP) or on the aggregated (potentially partial) votes and ranks (Aggregated-SP).We conduct a human-subject study with 432 participants recruited from Amazon's Mechanical Turk (MTurk) to empirically evaluate the performance of our SP algorithms using metrics such as the Kendall-Tau distance from the full ground truth ranking and Spearman's rank correlation coefficient. We consider several classical vote aggregation methods (e.g. Borda, Copeland, Maximin, Schulze) as benchmarks-rooted in the computational social choice theory-that operate solely on votes (and not prediction information). Our results show that the SP voting algorithms perform significantly better than the classical methods when the vote and prediction information only contain partial rankings. We also observe that SP voting algorithms are effective even when restricted to approval votes. Moreover, we demonstrate that voters' behavior in the experiment, including the minority of the experts can be correctly simulated by a concentric mixtures of Mallows model [33, 10] . Finally, we provide theoretical bounds on the sample complexity of the SP algorithms with partial preferences to further demonstrate the theoretical guarantees of the proposed methods. We show that the sample complexity only depends on the size of the subset k which is significantly smaller than m.Our work is related to information elicitation, and partial aggregation which we discuss briefly.Information Elicitation. Various information elicitation schemes [35, 36, 48, 17] attempt to incentivize voters to reveal useful information, often through the investment of efforts. Our work is primarily related to the surprisingly popular algorithm [36] which is a a novel second-order information based elicitation scheme. This framework has since been used to incentivize truthful behaviour in agents [35, 42, 43] , mitigate biases in academic peer review [32] , elicit expert knowledge [27] , and aggregate information [9] . Our study builds upon this literature, specifically addressing the challenges in rank recovery. Originally, the SP algorithm by Prelec et al. [36] required data on all m! potential rankings for m alternatives , a requirement that becomes impractical as m increases. Hosseini et al. [25] addressed this by developing a Surprisingly Popular Voting algorithm that leverages pairwise preference data across m 2 alternatives. This approach doesn't scale when m is large, and our contribution lies in advancing this methodology by proposing a scalable generalization of the Surprisingly Popular Voting method with partial preferences. Partial Aggregation. In situations where it is difficult or not necessary to elicit complete rankings from voters, partial preferences are used. Partial vote aggregation has different solution concepts [6] . Partial preferences can be used to conclude which alternatives are necessary and possible winners based on the preference profiles [26, 14, 47, 2, 3, 49] . The primary goal of partial aggregation methods is to either minimize the amount of information communicated by the voters [12, 45, 40] or to reduce the number of queries that each voter needs to answer [37, 14] . Our work attempts to reduce such communication from the voters by eliciting partial preferences.More broadly, our work is also related to information aggregation, and probabilistic rank-order models which we discuss further in Appendix A. 
model: 
 In this section, we formally define the model for Surprisingly Popular Voting in the context of partial preferences. Let A = {a 1 , a 2 , ..., a m } denote the set of m possible alternatives. The set L(A) represents all possible complete rankings over the alternatives. Let σ ∈ L(A) represent a complete ranking of the m possible alternatives. We denote the ground truth ranking by π ⋆ ∈ L(A); which is assumed to be drawn from a prior P (•) over L(A). Voter i observes a ranking π i that is assumed to be a noisy version of the ground truth ranking π ⋆ . We will write Pr s (π i | π ⋆ ) to denote the probability that the voter i observes her ranking π i given the ground truth π ⋆ .Given voter i's ranking π i and the prior P (•), voter i can compute the posterior distribution over the ground truth using the Bayes rule.Pr g (π ⋆ | π i ) = Prs(πi|π ⋆ )•P (π ⋆ ) π ′ ∈L(A) Prs(πi|π ′ )•P (π ′ ) (1)Using the posterior over the ground truth, voter i can also compute a distribution over the rankings observed by another voter.EQUATIONThe surprisingly popular algorithm [36] asks voters to report their votes, and posterior over others' votes. For each ranking π ′ , it then computes the frequency f(π ′ ) = 1 n i 1[π = π ′ ], and posterior g(π | π ′ ) = 1 |{i:πi=π ′ }| i:πi=π ′ Pr o (π | π i ),and finally picks the ranking with highest prediction normalized votes. 2πEQUATIONAs observed by Hosseini et al. [25] , eliciting full posterior and even the vote might be prohibitive if the number of alternatives m is huge. In this work, we are concerned about eliciting partial rankings over subsets of size k ≪ m. Let us fix a subset T ⊆ A of size k. Then the probability of a partial ranking σ i is given asEQUATIONHere we use the notation π ▷ σ i to indicate that the ranking π when restricted to the set T is σ i .We can also naturally extend definition 1 to define the posterior distribution over partial preferences given a partial preference σ i . In order to do so, let us first define the posterior over full ground truth π ⋆ given σ i as,Pr g (π ⋆ | σ i ) = Prs(σi|π ⋆ )P (π ⋆ ) π Prs(σi|π)P (π)where one can use definition (4) to compute Pr s (σ | π ⋆ ). Now we can write down the posterior probability over the partial ground truth σ as follows.EQUATIONFinally, we can write the posterior over another partial ranking σ ′ over the subset T .EQUATIONIn this work, our aim is to propose several versions of surprising popular algorithm that work with partial preferences. As shown in definition 3, it requires eliciting information regarding voters partial preferences, and posterior over others' partial preferences (as defined in eq. ( 6)). Next, we discuss various ways of eliciting such information from the voters.Given a subset of size k ≪ m alternatives, voter i's prediction Pr o (• | σ i ) is a distribution over k! rankings.In practice, this renders elicitation of full prediction information difficult, if not impossible, due to its cognitive overload. Thus, we focus on simple, and more explainable, elicitation methods that rely on ordinal information either by identifying the most preferred alternative (Top), selecting the most preferred t alternatives (Approval(t)), or a complete ranking of the partial set (Rank). The formal definitions can be found in Appendix B.Given these elicitation methods, we study different combinations of formats for votes and predictions where the first component indicates the vote format and the second component denotes the prediction format. These give rise to nine formats: Top-None, Top-Top, Top-Approval(t), Top-Rank, Approval(t)-Rank, Approval(t)-Approval(t), Rank-None, Rank-Top, and Rank-Rank. For Approval(t), the approval set of size t ∈ {1, 2, 3} is selected. Note that Approval(1) ≡ Top. 
aggregation algorithms for partial preferences: 
 The surprisingly popular method (as we discussed in section 1) cannot be applied directly to find a full ranking using only partial preferences. Thus, we develop two vote aggregation algorithms that only rely on partial ordinal preferences both for votes and predictions. On the high level, the two algorithms differ on how and when they implement the SP method, whether independently on each subset (Partial-SP) or on the aggregated (potentially partial) votes and ranks (Aggregated-SP).Here we provide a high-level description for each of the algorithms; additional details and exact pseudo-codes are relegated to Appendix D.The key element of this algorithm is utilizing SP voting on the partial rankings obtained at each step. It takes a set of potentially overlapping subsets of alternatives and a voting rule as input and proceeds as follows: For each subset S j of alternatives, collect votes and predictions from voters on this subset according to one of the elicitation formats detailed in Section 2.1. Compute the ground truth partial ranking on the subset S j using the SP algorithm. Aggregate all partial rankings using a voting rule (e.g. Condorcet) to find a full ranking over all alternatives (breaking ties at random).Aggregated-SP. This variation utilizes SP voting on the final rankings over votes and predictions. It takes a set of potentially overlapping subsets of alternatives and a voting rule as input and proceeds as follows: For each subset S j of alternatives, collect votes and predictions from voters on this subset according to one of the elicitation formats detailed in Section 2.1. Aggregate all votes (partial rankings) using a voting rule (e.g., Condorcet) to find the aggregated vote over all alternatives, breaking ties at random. Predictions are not aggregated to preserve conditional prediction information crucial for SP voting. Apply SP algorithm pairwise across all alternatives where for each pair (a, b), the vote information is derived from the scores of a and b based on the aggregation rule used, and the prediction information is used to find the conditional probabilities, P (a|b) and P (b|a). Breaking ties at random throughout this process results in a full ranking over all alternatives.Subset Selection. The algorithms described in this section rely on partial rankings on the subset of alternatives. Given m alternatives, we carefully select subsets of size k with an inter-alternative pairwise distance of s between elements from the ground-truth ranking. Formally, a subset S j of size k is generated as follows:EQUATIONwhere j ≥ 0 and j + (k -1)s < m, ensuring elements are within the range of m alternatives. We get a total of m -(k -1)s subsets. Note that we use overlapping subsets so as to introduce transitivity among different subsets enabling us to compare alternatives across different subsets. This leads to an improvement in the accuracy of our algorithms as we discuss in Section 5.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Justification:Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
experimental design: 
 This section describes the experimental design of the Amazon Mechanical Turk (MTurk) study to assess the comparative efficacy of Partial-SP and Aggregated-SP against other voting rules for partial preferences. Participants in this study were asked to answer a series of questions, wherein they were required to express their preferences by voting on a range of alternatives. In addition to casting their own votes, participants were asked to predict the collective preference of others for the same set of alternatives. Data was collected from 432 respondents. Each participant was given a 20-minute window to complete a series of 18 questions (see details below). 3 Datasets. The survey encompassed three distinct domains: (i) The geography dataset contains 36 countries with their population estimates, according to the United Nations, (ii) The movies dataset contains 36 movies with their lifetime box-office gross earnings, and (iii) The paintings dataset contains 36 paintings with their latest auction prices. Questions. We explored 36 alternatives per domain, aiming to gather partial preferences from voters. Each question featured a subset of alternatives, with the size of each subset maintained uniformly throughout the experiment.Each participant was presented with a subset of 5 alternatives, selected based on an interalternative gap of 6 positions within the ground-truth ranking. This strategy was designed to balance the cognitive load against the quality of the responses. We tested subset sizes of 4 to 6 and interalternative gaps of 3 to 8, finding that larger sizes and wider gaps generally enhanced ground-truth recovery. However, larger subset sizes increase cognitive load for participants, and wider gaps reduce overlap between subsets when limited to 36 alternatives. For each combination of 12 subsets, 9 elicitation formats, and 3 domains, each question received 16 responses.The survey was structured for each participant to answer two questions from each of the three domains and two elicitation formats, totaling 12 questions per participant. Figure 1 shows the workflow for each participant; each participant was assigned 18 questions to answer. Refer to Appendix E for details on the tutorials, participant qualifications for the MTurk study, and review questions regarding the perceived difficulty and expressiveness of the study.Elicitation Formats. We use various elicitation formats (as described in section 2.1). For example, consider a question that requires participants to rank five movies: a) Rogue One: A Star Wars Story, b) Titanic, c) Toy Story 3, d) The Dark Knight Rises, and e) Jumanji: Welcome to the Jungle-based on their lifetime gross earnings. Under the Approval(3)-Rank elicitation format, the structure of the vote and prediction questions would be framed as follows:• Part A (vote): "Which among the following movies are the top three in terms of highest grossing income of all time?" • Part B (prediction): "Considering that other participants will also respond to Part A, in what order do you predict the following movies will be ranked, from the most common response (top) to the least common (bottom)?"Refer to Appendix I for further details about formulations of all nine elicitation formats, the consent form, the tutorial for each domain, screenshots, and other details.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification:Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
results and analysis: 
 In this section, we present the results of this study averaged across all three domains. We measure the accuracy of the proposed SP algorithms (Partial-SP and Aggregated-SP) in predicting the full ground-truth ranking, in comparison with common vote aggregation methods (e.g. Borda, Copeland, Maximin, Schulze). The details of these aggregation methods is provided in Appendix C.Additionally, we compare the elicitation formats (described in Section 2.1) with respect to cognitive effort (measured by response time and difficulty) and expressiveness (measured directly by survey questions). They are provided in Appendix G.2To capture the error in predicting the full ground-truth ranking, we use three different metrics: (i) the Kendall-Tau correlation, which measures the distance between ordinal rankings, (ii) Spearman's ρ correlation, which measures the statistical dependence between ordinal rankings, (iii) Pairwise hit rate, which measures the fraction of pairs at distance d that are correctly ranked with respect to the ground-truth ranking, and (iv) Top-t hit rate, which measures the fraction of alternatives that are predicted correctly (in no order) in most preferred t compared to the ground-truth ranking. The formal definitions can be found in Appendix G.1.For example, consider the ground-truth ranking a ≻ b ≻ c ≻ d. The predicted ranking b ≻ a ≻ d ≻ c has a pairwise hit rate of 1/3 at distance 1, 1 at distances 2 and 3. Its Top-1 hit rate is 0, Top-2 is 1, Top-3 is 2/3, and Top-4 is 1.Figure 2 illustrates the performance of SP algorithms measured by Kendall-Tau and Spearman's correlations. We fix Copeland as the aggregation rule used in both variations of SP voting and compare the accuracy with applying Copeland on votes alone (without the use of prediction information).Statistical correlations and elicitation. SP voting produces rankings with a significantly higher correlation with the ground truth ranking, and this effect improves as the information provided as votes and prediction becomes more expressive. In particular, Rank-Rank and Approval(3)-Rank outperform all other elicitation formats. We note that Aggregated-SP seem to be more reliant on the vote information, compared to the predictions, as it can seen in Top-Rank vs. Rank-Top. In contrast, Partial-SP does not exhibit any significant favor for vote vs. prediction information as both Top-Rank and Rank-Top improve by additional information. However, the difference between them is not statistically significant.Interestingly, eliciting unordered information for both noisy votes and predictions (e.g. Approval(2)-Approval(2)) seem to be sufficient in recovering the ground truth-raising the question of whether pairwise comparisons are necessary in designing SP algorithms.Hit rates. With respect to pairwise hit rate and the Top-t hit rate, the noisy prediction information significantly improves the performance of the Partial-SP algorithm (with lower variance) as shown in Figure 3 . The results for Aggregated-SP are qualitatively similar and are presented in Appendix G.5. The slight dip in pairwise hit rate, can be explained by the survey's design choice of an inter-alternative distance of 6, leading to fewer comparisons being available for these pairs.Partial-SP vs. Aggregated-SP. While both variants of the SP algorithm significantly outperform common voting rules by utilizing (noisy) prediction information, the Partial-SP algorithm significantly outperforms the Aggregated-SP algorithm (see Figure 2 and Figure 4 ). This could be explained by the importance of 'correcting' noisy votes on the subsets of alternatives because the prediction information of the Partial-SP algorithm helps identify experts early on in predicting partial rankings of these alternatives.For Partial-SP, the plots indicate no statistical significance between Approval(2)-Approval(2), Approval(3)-Rank, and Rank-Rank elicitation formats, suggesting they perform as well as Rank-Rank. An interesting ramification here is demonstrating that approval sets not only perform well in predicting the ground truth, but also pose less cognitive burden on voters compared to those elicitation formats that ask for rankings (see appendix G.2).Performance of Partial-SP and Aggregated-SP is robust across domains. They outperform common voting rules with the sole exception of the Schulze method, which matches the performance of Aggregated-SP (see Figure 4 ). The difference in performance is notably high for Paintings domain, where specialized expertise is required to predict painting prices. Here, Partial-SP significantly outperforms common aggregation rules, showcasing its effectiveness in leveraging expert knowledge and correcting misinformation. For further details see Appendix G.3.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification:Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
simulated model of voter behavior: 
 In this section, we investigate whether there is any underlying probabilistic model that can explain the voters' behaviours when measured in terms of the vote and predictions. If successful, such a model will also enable us to theoretically analyze the sample complexity of SP algorithms (as we present in Section 7). In particular, we posit that a concentric mixtures of Mallows model can explain the users' reports (both vote and prediction) in the dataset. The concentric mixtures of Mallows model is a type of mixture models where there is one ground truth, but different groups of users have different dispersion parameters, and hence different distribution over observed preferences. Concentric mixtures of Mallows model. We assume that each voter is likely to be an expert with probability p(≪ 1) and a non-expert with probability 1 -p. Given a ground truth ranking π ⋆ , an expert voter observes a ranking that is distributed according to a Mallows model with center π ⋆ and dispersion parameter ϕ E . On the other hand, a non-expert voter observes a ranking that is again distributed according to a Mallows model with center π ⋆ , but with a larger dispersion parameter ϕ N E . In particular, the ranking observed by voter i is distributed asEQUATIONwherePr s (π | π ⋆ , ϕ) is the standard Mallows model with dispersion ϕ i.e. Pr s (π | π ⋆ , ϕ) = ϕ d(π,π ⋆ ) Z(ϕ,m) . The term Z(ϕ, m) is the normalization constant, and is defined as Z(ϕ, m) = π ϕ d(π,π ⋆ ). With a slight abuse of notation, we will write Z(ϕ) as Z(ϕ, m) since the number of alternatives in the ground truth is assumed to be fixed. Note that, Equation (8) defines a distribution over complete preferences, but given a subset of size k we can naturally extend this definition to define a distribution over partial preferences e.g. Pr s (σ i | π ⋆ ) (eq. ( 4)), and posterior over partial preferences of other voters e.g. Pr o (σ | σ i ) (eq. ( 6)). We fit the mixture model eq. ( 8) on the real datasets and estimate the following parameters -proportion of experts (p), dispersion parameters of experts' votes (ϕ E-votes ) and predictions (ϕ E-predictions ), as well as the dispersion parameters of non-experts' votes (ϕ N E-votes ) and predictions (ϕ N E-predictions ). The parameters were inferred using Bayesian inference [24] . We also generated synthetic data using the concentric mixtures of Mallows model, and again used Bayesian inference to estimate the parameters. The details of estimation and data generation are provided in the appendix F. Figure 5 shows the posterior distributions for the dispersion parameters when the datasets of all the three domains are combined. We see that the synthetic data generation process accurately replicates real data characteristics, and highlights that the concentric mixtures of Mallows accurately model voters' behaviours on MTurk. Furthermore, Figure 6 the Movies domain. Now we see almost perfect fit between the synthetic data and the original data.Further similarity in results between real and simulated data is described in Appendix G.6.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification:Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
analysis of sample complexity: 
 In this section, we use a concentric mixture of Mallows models, and provide upper bound on the sample complexity of the surprisingly popular voting method with partial preferences. We start with a simple problem. Given a subset T of size k, suppose our goal is to recover the true partial ranking over the alternatives in T , then how many samples does SP algorithm require?We will analyze the following simplified version of the SP algorithm: Voter i reports vote σ i over the subset T , which is used to build an estimate of f (σ) for all σ ∈ Π s . For each σ, the posterior report by the voter is a partial ranking drawn from the distribution g(• | σ). These reports are used to build an estimate g(σ′ | σ) for all σ ′ , σ. Select partial ranking σ ∈ argmax σ V (σ) = f (σ) • σ∈Πs g(σ ′ |σ) g(σ|σ ′) . It is impossible to recover the partial ground truth ranking if the fraction of the experts p can be very small, or the dispersion parameter of the non-experts ϕ N E can be very large. In order to ensure recovery of the true partial ranking we will make the following assumption. Assumption 1. The dispersion parameters ϕ E , ϕ N E , and the fraction of experts p satisfy the following inequality,p 1-p 2 ≥ 2 • Z(ϕ N E ) Z(ϕ E ) 2 Z(ϕ N E , k)ϕ k(k-1)/2 E where Z(ϕ, k) = σ:[k]→[k] ϕ d(σ,σ ⋆ ) .The next theorem states that sample complexity under the above assumption.Theorem 1. Suppose Assumption 1 holds, and the total number of samples n ≥ k! 10k log(2k/δ)µ where µ = p • Z(ϕ E ,m-k) Z(ϕ E ) • ϕ k(k-1)/2 E + (1 -p) • Z(ϕ N E ,m-k) Z(ϕ N E ) • ϕ k(k-1)/2 N E. Then the surprisingly popular algorithm recovers true ranking over the subset T of size k with probability at least 1 -δ.Suppose ϕ E ≪ ϕ N E < 1. Then Assumption 1 requires p 1-p ≥ Ω ϕ k 2 /4+1 N E ϕ k 2 /4-1 E, and it implies that if ϕ N E is very large compared to ϕ E (i.e. noisy non-experts) then we need a larger value of p (i.e. more experts).We provide the full proof of the theorem in Appendix I. The main ingredient of the proof is Lemma 2 which shows that under Assumption 1 there is a strict separation between the true predictionnormalized score of the true partial ranking and any other ranking. In fact, we show that V (σ ⋆ ) ≥ 2V (τ ) for any τ with d(τ, σ ⋆ ) ≥ 1. Given this result, we can apply standard concentration inequality to show that V (σ) is close to V (σ) for all σ when the number of samples is large, and V (σ ⋆ ) will be larger than V (τ ) for any τ ̸ = σ ⋆ . Therefore, picking the ranking with the largest empirical prediction-normalized score returns the correct ranking.Note that the sample complexity grows proportional to k! only because we compute predictionnormalized votes over all k! partial rankings. If we are interested in recovering top t-alternatives then it will grow proportional to k t . Moreover, the subset size k is assumed to be very small compared to the number of alternatives m, and Theorem 1 shows the benefit of applying SP algorithm to partial preferences. We can immediately apply Theorem 1 to a collection of subsets S through a union bound, and extend our analysis to the Partial-SP algorithm. Let us assume that in the second stage of Partial-SP, we apply a t-consistent voting rule f that recovers top-t alternatives as long as each partial ranking in S is correct. Corollary 1. Under the same setting as Theorem 1, suppose the number of samples from each subset in S is n ≥ k! 10k log(2|S|k/δ) µ . Then the Partial-SP algorithm with a t-consistent voting rule, recovers the top t alternatives of the ground truth π ⋆ with probability at least 1 -δ.Finally note that, the total sample complexity ofÕ(|S| • k! √ k)is needed only because we adopt a naive version of the SP algorithm for proving theoretical guarantees. For the experiments, we adopt a pairwise version of the SP algorithm which applies SP-voting to each pair within a subset. We believe that under further assumptions, the total sample complexity can be reduced to Õ(|S| • k 2 ) with such a pairwise variant of the partial-SP algorithm, and we leave this analysis for the future.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification:Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
discussion and future work: 
 We conclude by discussing some limitations and future directions. When dealing with partial preferences, even when majority have the correct information, effective preference elicitation or finding a necessary winner in most vote aggregation rules are often computationally intractable [11, 39, 18] . These challenges, together with the minority of experts, further highlight the efficacy of the SP approach in balancing information elicitation and accuracy, by employing additional prediction information. Future research can explore the setting of SP beyond the majority-minority dichotomy (e.g. informed, but not expert voters) or when malicious voters are present (e.g. in detecting misinformation). Theoretically, the sample complexity can be explored beyond Mallows model under other probabilistic models to enhance our understanding of this approach, particularly in notable applications such as political polling or collective moderation of online content. [20] , Borda [5] ,Copeland [16] , Young [51] , and many others focus on information aggregation by eliciting votes. These rules can be adapted to elicit ranked information from voters and then aggregate them into a single ranking representing the collective opinion of the crowd. [4] . Information Aggregation has also been examined from a statistical perspective, where the aggregated ranking is viewed as the maximum likelihood estimate of the population's rankings [20, 15, 50, 13] . Within this framework, individual votes are considered outcomes of probabilistic models such as the Thurstonian model, Bradley-Terry model, Mallows' model, or Plackett-Luce model [34] .Partial Aggregation. In situations where it is difficult or not necessary to elicit complete rankings from voters, partial preferences are used. Partial vote aggregation has different solution concepts [6] . Partial preferences can be used to conclude which alternatives are necessary and possible winners based on the preference profiles [26, 14, 47, 2, 3, 49] . Alternatively, a regret based approach can be used to assess the quality of a winning alternative where the optimal alternative is the one that minimizes regret [30] . Apart from these epistemic notions, a lot of work has been done on probabilistic analysis of winners from partial profiles [1, 23, 29, 31] . To minimize the information elicited from a population, it is crucial to understand the methods used for eliciting partial preferences. It can either be by minimizing the amount of information communicated by each voter in their answer [12, 45, 40] or by reducing the number of queries that each voter needs to answer [37, 14] . In either of these cases, the objective is still to determine the winner accurately. Cognitive complexity also plays an important part in this, as all these notions are highly correlated. Finally, the recovery of complete rankings from partial preferences is another solution concept that is studied [21, 41] .Due to the combinatorial nature of the rankings, winner determination, communication complexity, query complexity, and cognitive complexity are all relevant here. This is where our research work contributes.Surprisingly Popular Framework. In their seminal work, Prelec [35] , Prelec et al. [36] introduced the Surprisingly Popular (SP) algorithm, a novel second-order information based method that recovers truthful subjective data in scenarios where objective truth remains unknown. This framework has since been used to incentivize truthful behaviour in agents [35, 42, 43] , mitigate biases in academic peer review [32] , elicit expert knowledge [27] , model thinking hierarchy of people without any prior [28] , aggregate information [9] and recover ground-truth ranking [36, 25] . Our study builds upon this literature, specifically addressing the challenges in rank recovery. Originally, the SP algorithm by Prelec et al. [36] required data on all m! potential rankings for m alternatives , a requirement that becomes impractical as m increases. Hosseini et al. [25] addressed this by developing a Surprisingly Popular Voting algorithm that leverages pairwise preference data across m 2 alternatives. However, this approach encountered scalability limitations when dealing with more than four alternatives in partial preference profiles. Our contribution lies in advancing this methodology by proposing a scalable generalization of the Surprisingly Popular Voting method for partial preferences, thus broadening its applicability and effectiveness.In this section, we formally define the elicitation formats used in our study. Let v i and p i denote the vote and prediction submitted by voter i. Let T = {a 1 , a 2 , . . . , a k } denote the subset of alternatives of size k that voters will report on and L(T ) denote the set of all possible rankings of alternatives in T . Let σ denote a ranking of the alternatives in T and σ(j) denote the alternative at the j th position in σ. The elicitation formats are defined as follows:Top-None: Voter i reports the top alternative in her observed noisy ranking, i.e., v i = σ(1), and does not provide any inference about other's aggregated votes.Top-Top: Voter i reports the top alternative in her observed noisy ranking, i.e., v i = σ(1), and provides the estimate of the most frequent alternative among the other voters, i.e., p i = arg max a∈T σ∈L(T ):σ(1)=a Pr o (σ|σ i ).Top-Approval(3): Voter i reports the top alternative in her observed noisy ranking, i.e., v i = σ(1), and provides the estimate of the top three most frequent alternatives, in no specific order, among the other voters., i.e., p i = arg max a,b,c∈T σ:{a,b,c}⊆{σ(1),σ(2),σ(3)} Pr o (σ|σ i ).Top-Rank: Voter i reports the top alternative in her observed noisy ranking, i.e., v i = σ(1), and provides the estimate of other's rankings i.e, p i ∈ L(T ) such that σ∈L(A):σ(1)=qi(x) Pr o (σ|σ i ) ≥ σ∈L(T ):σ(1)=qi(y) Pr o (σ|σ i ) for all x > y. Approval(2)-Approval(2): Voter i reports the top two alternatives, in no specific order, in her observed noisy ranking, i.e., v i = {σ(1), σ(2)} = {a, b} with a, b ∈ T in no particular order and provides the estimate of the top two most frequent alternatives, in no specific order, among the other voters., i.e., p i = arg max a,b∈T σ:{a,b}⊆{σ(1),σ(2)} Pr o (σ|σ i ).Approval(3)-Rank: Voter i reports the top three alternatives, in no specific order, in her observed noisy ranking, i.e., v i = {σ(1), σ(2), σ(3)} = {a, b, c} with a, b, c ∈ T in no particular order, and provides the estimate of other's rankings i.e, p i ∈ L(T ) such that σ∈L(A):σ(1)=qi(x) Pr o (σ|σ i ) ≥ σ∈L(T ):σ(1)=qi(y) Pr o (σ|σ i ) for all x > y. Rank-None: Voter i reports her entire observed noisy ranking, i.e., v i = σ i , and does not provide any inference about other's aggregated votes.Rank-Top: Voter i reports her entire observed noisy ranking, i.e., v i = σ i , and provides the estimate of the most frequent alternative among the other voters, i.e., p i = arg max a∈T σ∈L(T ):σ(1)=a Pr o (σ|σ i ).Rank-Rank: Voter i reports her entire observed noisy ranking, i.e., v i = σ i , and provides the estimate of other's rankings i.e, p i ∈ L(T ) such that σ∈L(A):σ(1)=qi(x) Pr o (σ|σ i ) ≥ σ∈L(T ):σ(1)=qi(y) Pr o (σ|σ i ) for all x > y.Vote aggregation rules are social choice functions that are used to aggregate individual votes to make conclusions about the collective opinion of a multi-candidate voting system [6] . Given below are the vote aggregation rules used in our study. We will only focus on aggregating ranked preferences.Profile 44 A ≻ B ≻ C ≻ D 24 B ≻ C ≻ D ≻ A 18 C ≻ D ≻ B ≻ A 14 D ≻ C ≻ B ≻ A Table 1: Voter Preferences C.1 BordaThe Borda rule [5] is a voting rule in which voters order candidates by ranked preference, and candidates are awarded points based on their position in each voter's ranking. The winner is the candidate with the highest total score after all votes are counted. It can be mathematically represented as:Borda Score(a) = n i=1 (m -1 -σ -1 i (a))where σ -1 i (a) represents the position at which alternative a is present. The aggregated ranking is derived by sorting the Borda scores of the alternatives in descending order.Example 1. Apply Borda Rule to the preference profile given in Table 1 Table 1 provides the preference profiles of voters. Applying Borda Rule, we find that Borda Scores of A, B, C, D are 132, 192, 174, and 102 respectively. Thus arranging the scores in descending order results in the aggregated ranking of B ≻ C ≻ A ≻ D.The Copeland rule [16] is a voting method used to select a single winner from a set of candidates based on pairwise comparisons between each pair of candidates. In the Copeland method, each candidate receives a score based on the number of head-to-head contests they win against other candidates, with ties potentially receiving a half point for each candidate involved in the tie. It can be mathematically represented as:Copeland Score(a) = a,b∈A, b̸ =a    1 if V (a, b) > V (b, a) 0.5 if V (a, b) = V (b, a) 0 if V (a, b) < V (b, a)where V (a, b) represents all the voters who preferred a over b. The Maximin rule [51] , also known as the Simpson-Kramer method , selects a winner from a set of candidates by considering the strength of a candidate's worst-case pairwise comparison against all other candidates. It identifies the candidate whose least favorable comparison is superior to those of the others, aiming to find the most robust candidate against the strongest opponent. This can be mathematically expressed as:Maximin Score(a) = min b∈A,b̸ =a V (a, b)where V (a, b) represents all the voters who preferred a over b. The aggregated ranking is derived by sorting the Maximin scores of the alternatives in descending order. Example 3. Apply Maximin Rule to the preference profile given in Table 1 In order to apply Maximin Rule to the preference profiles given in Table 1 we first analyze the worst pairwise defeat and its margin by the following The alternative that has a higher score of worst pairwise defeat or that loses by a higher margin is considered worse off. Thus, arranging in ascending order of the scores of any of the column results in the aggregated ranking of B ≻ A ≻ C ≻ D.The Schulze rule [44] selects a ranking of a set of candidates based on the strength of preferences expressed by voters. The strength of a preference is considered to be the number of voters who prefer one candidate over another. For every pair of candidates, a directed graph is constructed where the edges represent the strength of preference. The method then calculates the strongest path (defined as the weakest link in the path being as strong as possible) between every pair of candidates. A candidate wins if, for every other candidate, there exists a stronger (or equal strength) path to that candidate than from that candidate. It can be mathematically expressed as:Initially, for all pairs of candidates a, b: For each candidate a, calculate a comprehensive score that may involve the sum of all positive differences P (a, b) -P (b, a) against other candidates b. The aggregated ranking is obtained by sorting these scores in descending order. Example 4. Apply Schulze Rule to the preference profile given in Table 1 In order to apply Schulze Rule to the preference profile given in Table 1 , we first generate a Directed Graph where the vertices denote the alternatives and the weight of the edges denote the score by which one alternative defeats the other. For the preferences in Table 1 , we get the following graph: The Table 4 finds the strongest path for each pair of vertices: P (a, b) = V (a, b) if V (a, b) > V (b,A B C D A X 0 0 0 B B → 68 → C → 86 → D → 56 → A X B → 68 → C B → 68 → C → 86 → D C C → 86 → D → 56 → A 0 X C → 86 → D D D → 56 → A 0 0 XAppendix D.1 details the approach used to extract information from various elicitation formats. Explanation and pseudocode for Partial-SP and Aggregated-SP is provided in Appendix D.2 and Appendix D.3, respectively.Algorithm 1 describes how information is extracted from different elicitation formats. The algorithm takes as input the votes ({v i } i∈[n] ) and predictions ({p i } i∈[n] ) of n voters, pair (a, b) of alternatives, and parameters α and β. Using grid search on the datasets from the three domains, it was observed that any α > 0.5 and β < 0.5 can be used. In our experiments we use α = 0.55 and β = 0.1. For votes and predictions expressed as top choices or approvals, if a is the preferred alternative, v for i = 1, . . . , n do /* Extract Vote Information */ if vi is elicited as rank then Set v (a,b) i = 1 if a ≻v i b 0 o.w. else if vi is elicited as top or approval then Set v (a,b) i = 1 if vi = a 0 if vi = b else Ignore (vi, qi) /* Extract Prediction Information */ if pi is elicited as rank then Set p (a,b) i =        α if a ≻p i b and v (a,b) i = 1 1 -α if b ≻p i a and v (a,b) i = 1 1 -β if a ≻p i b and v (a,b) i = 0 β o.w. else if pi is elicited as top or approval then Set p (a,b) i =        α if pi = a and v (a,b) i = 1 1 -α if pi = b and v (a,b) i = 1 1 -β if pi = a and v (a,b) i = 0 β o.w. else Set p a,b i = 1 2 return {v (a,b) i , p (a,b) i } i∈[n]Algorithm 2 describes the proposed Partial-SP aggregation approach. The algorithm takes as input the number of voters (n), number of alternatives (m), set of all subsets that voters voted on (S), voters' votes ({v i,j } i∈[n],j∈S ), voters' predictions ({p i,j } i∈[n],j∈S ), parameters α and β representing the conditional probabilities that would be returned for the predictions, and Vote Aggregation Rule (V). For n voters and m alternatives, depending on the elicitation format, the voters will be providing votes (v i,j ) and predictions (p i,j ) as Top choices, Approvals(t), or Rankings over a subset S j ∈ S. Additionally, we use Borda, Copeland, and Maximin aggregation rule for V.For every pair of alternatives (a, b) within a subset S j , we extract information about the number of people that voted for a ≻ b and b ≻ a represented by f (a ≻ b) and f (b ≻ a) respectively, and the conditional probability of their predictions (g(0|0), g(0|1), g(1|0), g(1|1)). Refer to Appendix D.1 for a detailed explanation of how information is extracted for different elicitation formats. With this, the prediction normalized score V (a ≻ b) and V (b ≻ a) is calculated and a higher prediction normalized score decides the correct ordering for each pair (a, b) within a subset S j . This results in a partial ground-truth ranking representing the correct relative ordering for the alternatives within that subset. Q represents the set of partial ground-truth ranking for all subsets. Finally, Vote-Aggregation rule V is applied on Q to find the complete ground-truth ordering of the m alternatives. = 1Nb≻a = c : v (a,b) c = 0 f (a ≻ b) = i 1 v (a,b) i = 1 /(|Na≻b| + |Nb≻a|) f (b ≻ a) = 1 -f (a ≻ b) g(1 | 1) = 1 |Na≻b| i∈N a≻b pi and P (0 | 1) = 1 -P (1 | 1) g(1 | 0) = 1 |Nb≻a| i∈N b≻a pi and P (0 | 0) = 1 -P (1 | 0) /* Compute prediction-normalized vote */ V (a ≻ b) = f (a ≻ b) i g v (a,b) i |1 g 1|v (a,b) i V (b ≻ a) = f (b ≻ a) i g v (a,b) i |0 g 0|v (a,b) i /* Ties are broken uniformly at random */ if V (a ≻ b) < V (b ≻ a) then G ← G ∪ a ≻ b else G ← G ∪ b ≻ a Qj ← Qj ∪ G GT ← V(Q) return GTAlgorithm 3 describes the proposed Aggregated-SP aggregation approach. The algorithm takes as input the number of voters (n), number of alternatives (m), set of all subsets that voters voted on (S), voters' votes ({v i,j } i∈[n],j∈S ), voters' predictions ({p i,j } i∈[n],j∈S ), parameters α and β representing the conditional probabilities that would be returned for the predictions, and Vote Aggregation Rule (V). For n voters and m alternatives, depending on the elicitation format, the voters will be providing votes (v i,j ) and predictions (p i,j ) as Top choices, Approvals(t), or Rankings over a subset S j ∈ S. Additionally, we use Borda, Copeland, and Maximin aggregation rule for V.For every subset S j , we aggregate the votes using V, resulting in the set of partial aggregated subsets represented by Q. Q is a dictionary containing the alternative and its corresponding score according to the aggregation rule V. We now apply SP-Algorithm on Q. For every pair of alternatives (a, b) within a partial aggregated subset Q j , we extract information about the conditional probability of their predictions (g(0|0), g(0|1), g(1|0), g(1|1)). Refer to Appendix D.1 for a detailed explanation of how information is extracted for different elicitation formats. With this, the prediction normalized score V (a ≻ b) and V (b ≻ a) is calculated where we use the scores of the alternatives represented by Q(a) and Q(b). A higher prediction normalized score decides the correct ordering for each pair (a, b). Parsing all pairs, results in the complete ground-truth ordering of the m alternatives. = 1Nb≻a = c : v (a,b) c = 0 g(1 | 1) = 1 |Na≻b| i∈N a≻b pi and P (0 | 1) = 1 -P (1 | 1) g(1 | 0) = 1 |Nb≻a| i∈N b≻a pi and P (0 | 0) = 1 -P (1 | 0) /* Compute prediction-normalized vote */ V (a ≻ b) = Q(a) i g v (a,b) i |1 g 1|v (a,b) i V (b ≻ a) = Q(b) i g v (a,b) i |0 g 0|v (a,b) i /* Ties are broken uniformly at random */ if V (a ≻ b) < V (b ≻ a) then GT ← GT ∪ a ≻ b else GT ← GT ∪ b ≻ a return GTThis section provides additional details about the MTurk study Tutorial. Prior to engaging with each set of 6 questions within a specific elicitation format, participants completed a tutorial designed to evaluate their understanding of the voting process and prediction tasks. To proceed, participants had to accurately apply these beliefs within the voting and prediction framework, ensuring they were adequately prepared.Reviews. Following the completion of each set of 6 questions, participants were asked to evaluate the preceding questions' elicitation format in terms of difficulty (ranging from "Very Easy" to "Very Difficult") and expressiveness (from "Very Little" to "Very Significant"). Although question complexity was standardized within each domain, the domains themselves varied considerably in difficulty. To mitigate potential bias from implicit comparisons between the two elicitation formats assigned to each participant, the sequence of domains in the first set of questions was mirrored in the subsequent set. This methodological approach ensured consistency and fairness in the evaluation of the elicitation formats, thereby enhancing the reliability of participants' feedback Response qualifications & payment. To ensure reliable responses, we established several qualification criteria for participants in our study on MTurk. Participants were required to have: (a) a minimum approval rate of 90% for their previous tasks, (b) completed at least 100 tasks on the platform, and (c) specified the region as US and Canada (to ensure language proficiency). To check attentiveness of the participants, we included an additional quiz that repeated one of the previous questions. The compensation structure included a base payment of 50 cents for completing the survey, which encompassed tutorials, questions, and evaluations. Additionally, a 50-cent bonus was offered for accurately completing the attentiveness quiz.To assess the accuracy of the simulations, we fit the concentric mixtures of Mallows model to both the real and simulated data to infer the model parameters. This process allows us to compare the inferred parameters, thereby evaluating how effectively the model captures the underlying patterns in the data. Specifically, we infer the proportion of experts (p), dispersion parameters of experts' votes (ϕ E-votes ) and predictions (ϕ E-predictions ), as well as the dispersion parameters of non-experts' votes (ϕ N E-votes ) and predictions (ϕ N E-predictions ). For the real data, the distribution of these parameters can help us in understanding the voting behavior of experts and non-experts. For the synthetic data, generated based on known parameters, we can check if the model accurately recovers these parameters.The parameters are inferred using Bayesian inference, implemented through the No-U-Turn Sampler (NUTS) [24] , an extension of Hamiltonian Monte Carlo (HMC) available in Stan [8] . Before sampling, we calculate the Kendall-Tau distance between the ground-truth ranking and the votes (τ votes ) and predictions (τ predictions ) of all the voters. We then define the priors for our parameters as follows:p ∼ β(1, 2.5) ϕ E-votes ∼ N (0.15, 0.075) ϕ E-predictions ∼ N (0.7, 0.3) ϕ N E-votes ∼ N (0.7, 0.3) ϕ N E-predictions ∼ N (0.7, 0.3)We then combine the likelihood of the parameters of our mixture model and perform inference over the following target function:target+ = log mix (p, N (τ votes [n] | 0, ϕ E-votes ) + N (τ predictions [n] | 0, ϕ E-predictions ), N (τ votes [n] | 0, ϕ N E-votes ) + N (τ predictions [n] | 0, ϕ N E-predictions ))The log-likelihood function incorporates the observed τ votes and τ predictions using the mixture model to account for the possibility that each voter could be an expert or a non-expert. We run four chains, each for 4000 iterations with 1000 iterations of warm-up for the NUTS algorithm. The algorithm explores the parameter space and updates the parameter estimates iteratively based on the input data and priors.The synthetic data was generated by simulating voter behavior using the concentric mixtures of Mallows model to construct preference rankings. This approach allows for the simulation of both expert and non-expert voters, with experts' votes closely aligning with a ground truth ranking and non-experts showing a broader dispersion in their preferences. The subsets to be voted on were generated as described in Section 4.Voter Classification. To simulate the voting process effectively, voters are initially classified into experts and non-experts. Since we need the experts to be in the minority, we determine the probability of a voter being an expert by sampling the proportion parameter as p ∼ β(1, 2.5).Voting Simulation: The voting behavior is simulated by the concentric mixtures of Mallows model.EQUATIONwhere ϕ E ∼ N (0.15, 0.075) and ϕ NE ∼ N (0.9, 0.4). Kendall-Tau distance is used as the distance metric between the rankings π i and π ⋆ .To quantitatively assess the alignment between the rankings derived from the voting rule, denoted as σ ′ , and the ground truth ranking, σ * , we use metrics described in the following subsections.This metric evaluates the accuracy of the voting rule in identifying the correct relative order between pairs of alternatives, focusing on pairs with an increasing distance in their positions in the ground truth ranking:Pairwise hit rate = 1 |P | (i,j)∈P 1((σ ′ (i) < σ ′ (j)) = (σ * (i) < σ * (j)))where P represents the set of pairs determined by the difference in their positions in σ * , and 1 is the indicator function.The Top-t hit rate metric quantitatively assesses the accuracy of a ranking algorithm by measuring the presence of the top-t elements from the ground truth ranking within the top-t elements of the predicted ranking. The formula for calculating the Top-t hit rate for rankings up to a given t is given by: Top-t hit rate = |Top-t elements in ground truth ∩ Top-t elements in predicted ranking| tThe Kendall-Tau correlation coefficient is a measure of the ordinal association between two rankings:τ (σ ′ , σ * ) = 2 n(n -1) i<j 1((σ ′ (i) -σ ′ (j))(σ * (i) -σ * (j)) > 0) -1where n is the number of elements in the ranking.The Spearman's ρ or Spearman correlation coefficient between σ ′ and σ * quantifies the rank correlation:ρ(σ ′ , σ * ) = 1 - 6 n i=1 d 2 i n(n 2 -1)with d i = σ ′ (i) -σ * (i)representing the rank difference of each element i between σ ′ and σ * .Bootstrapping. To ensure the robustness of our estimates, we used bootstrapping to approximate the sampling distribution of various statistics. This method offers insights into the variance and bias of our estimates without relying on the stringent assumptions required by traditional parametric methods.Bootstrapping is particularly advantageous when the distribution of metric values is unknown or does not conform to common distributional assumptions. After generating the bootstrapped distribution of metric values, we calculated the 95% confidence interval for each metric. Reporting these intervals alongside the metric values serves two purposes: it quantifies the uncertainty of our estimates, providing a transparent measure of their statistical precision, and it enhances the credibility of our findings by acknowledging the variability and potential error margins associated with our estimates.Here, we measure the response time, difficulty, and expressiveness of the elicitation formats we used in our study.• Response Time: We measure the average response time spent by the participants on each question for each elicitation format in our survey. This measure gives us an idea of the cognitive load perceived for each elicitation format [38] . • Perceived Difficulty: In the review phase of our MTurk survey, we asked participants to select from 'Very Easy', 'Easy', 'Neutral', 'Difficult', and 'Very Difficult' to subjectively indicate the ease of answering questions within each elicitation format. This approach provides a measure of the perceived difficulty associated with different elicitation formats. • Perceived Expressiveness: In the review phase of our MTurk survey, we prompted participants to select from the options 'Very Little', 'Little', 'Adequate', 'Significant', and 'Very Significant' to indicate the amount of information they could convey using each elicitation format. As expected, the participants spent similar or more time on the tutorial than on the questions. Additionally, the only elicitation format that has a statistical significance for the Questions is Approval(3)-Rank, where more time is spent by the participants. Thus, for all other elicitation formats, the participants face a similar cognitive complexity while responding to the questions. The figure shows the difficulty (easier is better) and expressiveness (higher is better) of different elicitation formats as reported by the participants. A higher percentage of participants found the tasks to be relatively easy, indicating that they could answer questions effortlessly across all elicitation formats. Conversely, they demonstrated similar expressiveness not strongly leaning to either side of the scale. The usage of different aggregation rules for Partial-SP and Aggregated-SP has similar impact on the outcome. However, the performance improves with an increase in information elicited as seen by the high correlation and increases statistical difference between the conventional methods and proposed methods. For example, Approval(2)-Approval(2) recovers ground-truth ranking more accurately than Top-Top. Note: We see Schulze method in Rank-Top as it only works for preference data. A high Spearman's ρ Correlation implies higher alignment between the ground-truth ranking and the aggregated ranking. The usage of Maximin aggregation rule for Partial-SP and Aggregated-SP has a better impact on the outcome as compared to other common aggregation rules. Additionally, the performance improves with an increase in information elicited as seen by the high correlation and increases statistical difference between the conventional methods and proposed methods. For example, Approval(3)-Rank recovers ground-truth ranking more accurately than Top-Approval(3). Note: We see Schulze method in Rank-Top as it only works for preference data. A p p r o v a l T o p -R a n k A p p ( 2 ) -A p p ( 2 ) A p p ( 3 ) -R a n k R a n k _ N o n e R a n k _ T o p R a n k _ R a n kT o p -N o n e T o p -T o p T o p -A p p r o v a l T o p -R a n k A p p ( 2 ) -A p p ( 2 ) A p p ( 3 ) -R a n k R a n k _ N o n e R a n k _ T o p R a n k _ R a n kFigure 16 shows the performance of Partial-SP with Copeland Aggregation on Real Data and Simulated Data using metrics described in Section G.1.1 and G.1.2. In both of the metrics, we observe similar trends across various pairwise distances, and top-t metrics. Proof. We first establish a lower bound on g(σ | σ ′ ) for any σ, σ ′ .g(σ | σ ′ ) = σ Pr g (σ | σ ′ )Pr s (σ | σ) ≥ min σ Pr s (σ | σ) σ Pr g (σ | σ ′ ) = min σ Pr s (σ | σ)Under the assumption of uniform prior we have,Pr s (σ | σ) = π:π▷σ Pr(π) Pr(σ) Pr s (σ | π) = 1 (m -k)! π:π▷σ Pr s (σ ⋆ | π) = 1 (m -k)! π:π▷σ π ′ :π ′ ▷σ Pr s (π ′ | π) = 1 (m -k)! π:π▷σ π ′ :π ′ ▷σ p • ϕ d(π ′ ,π) E Z(ϕ E ) + (1 -p) • ϕ d(π ′ ,π) N E Z(ϕ N E ) = 1 (m -k)! π:π▷σ p • Z(ϕ E , m -k) Z(ϕ E ) • ϕ d(σ,σ) E + (1 -p) • Z(ϕ N E , m -k) Z(ϕ N E ) • ϕ d(σ,σ) N E = p • Z(ϕ E , m -k) Z(ϕ E ) • ϕ d(σ,σ) E + (1 -p) • Z(ϕ N E , m -k) Z(ϕ N E ) • ϕ d(σ,σ) N E :=µ Here Z(ϕ, m -k) = τ :[m-k]→[m-k] ϕ d(τ,τ ⋆ ). Therefore, g(σ | σ ′ ) ≥ κ for any σ, σ ′ .We will first prove a multiplicative concentration inequality on the estimates g(• | σ) for any σ. Now fix any σ. By using lemma (1) we obtain that with probability at least 1 -δ 1 max σ ′ |g(σ ′ | σ) -g(σ ′ | σ)| ≤ log(1/δ1) n 2. This implies that g(σ′ | σ) ≥ g(σ ′ | σ) -log(1/δ1) n 2. Sinceg(σ ′ | σ) ≥ µ, in order to have g(σ ′ | σ) ≥ (1 -ε)g(σ ′ | σ) it is sufficient to have n ≥ log(1/δ1) ε•µ. Moreover, because of the fact that µ < 1, we also have g(σ ′ | σ) ≤ (1 + ε)g(σ ′ | σ). Finally, we can use union bound over all k! permutations σ and substituting δ 1 = δ/(2 • k!) we obtain that as long as the number of samples from each permutation σ is at least k log(2k/δ)EQUATIONWe now apply a similar concentration inequality for the frequency terms f (•). Since Pr s (σ | σ ⋆ ) ≥ µ for any σ we have f (σ) ≥ κ. By an argument very similar to the previous paragraph we have that aslong as n ≥ log(2/δ) ε•µ , we are guaranteed that (1 -ε)f (σ) ≤ f (σ) ≤ (1 + ε)f (σ) with probability at least 1 -δ/2.V (σ ⋆ ). V (σ ⋆ ) = f (σ ⋆ ) σ ′ g(σ ′ | σ ⋆ ) g(σ ⋆ | σ ′ ) ≥ (1 -ε) 2 (1 + ε) f (σ ⋆ ) σ ′ g(σ ′ | σ ⋆ ) g(σ ⋆ | σ ′ ) = (1 -ε) 2 (1 + ε) V (σ ⋆ )We now provide an upper bound on V (τ ) for any τ ̸ = σ ⋆ .V (τ ) = f (τ ) σ ′ g(σ ′ | τ ) g(τ | σ ′ ) ≤ (1 + ε) 2 (1 -ε) f (τ ) σ ′ g(σ ′ | τ ) g(τ | σ ′ ) = (1 + ε) 2 (1 -ε) V (τ )We now use lemma (2) i.e. V (σ ⋆ ) ≥ 2V (τ ).V (σ ⋆ ) ≥ (1 -ε) 2 (1 + ε) V (σ ⋆ ) ≥ 2(1 -ε) 2 (1 + ε) V (τ ) ≥ 2(1 -ε) 3 (1 + ε) 3 V (τ ) > V (τ ) as long as ε ≤ 3 √ 2-1 3 √ 2+1 ≈ 0.115. We substitute ε = 0.1. Finally, observe that we pick the outcome with highest empirical prediction normalized vote V (σ) and with probability at least 1 -δ, the empirical prediction normalized vote of σ ⋆ will be the highest, and will be picked as the outcome.Lemma 1 (Theorem 9 of [7] ). Let X 1 , . . . , X n be n be i.i.d. drawn from a discrete distribution p = (p 1 , . . . , p k ) and let p j = 1 Proof. Using the definition of g(• | •) we can establish the following lower and upper bounds.g(σ | σ ′ ) = σ Pr g (σ | σ ′ )Pr s (σ | σ) ≥ min σ Pr s (σ | σ) σ Pr g (σ | σ ′ ) = min σ Pr s (σ | σ) g(σ | σ ′ ) = σ Pr g (σ | σ ′ )Pr s (σ | σ) ≤ σ Pr s (σ | σ) σ Pr g (σ | σ ′ ) = σ Pr s (σ | σ)Now we can establish the following lower and upper bounds on the prediction-normalized vote.V (σ) = f (σ) σ ′ g(σ ′ | σ) g(σ | σ ′ ) ≤ f (σ) min σ Pr s (σ | σ) σ ′ g(σ ′ | σ) = f (σ) min σ Pr s (σ | σ) V (σ) = f (σ) σ ′ g(σ ′ | σ) g(σ | σ ′ ) ≥ f (σ) σ Pr s (σ | σ) σ ′ g(σ ′ | σ) = f (σ) σ Pr s (σ | σ)Now consider a partial ranking τ such that d(τ, σ ⋆ ) = 1. Then we have,V (σ ⋆ ) ≥ f (σ ⋆ ) σ Pr s (σ ⋆ | σ) = Pr s (σ ⋆ | σ ⋆ ) σ Pr s (σ ⋆ | σ) and V (τ ) ≤ f (τ ) min σ Pr s (τ | σ) = Pr s (τ | σ ⋆ ) min σ Pr s (τ | σ)Under the assumption of uniform prior we have,Pr s (σ ⋆ | σ) = π:π▷σ Pr(π) Pr(σ) Pr s (σ ⋆ | π) = 1 (m -k)! π:π▷σ Pr s (σ ⋆ | π) = 1 (m -k)! π:π▷σ π ′ :π ′ ▷σ ⋆ Pr s (π ′ | π) = 1 (m -k)! π:π▷σ π ′ :π ′ ▷σ ⋆ p • ϕ d(π ′ ,π) E Z(ϕ E ) + (1 -p) • ϕ d(π ′ ,π) N E Z(ϕ N E ) = c(T ) (m -k)! p • ϕ d(σ,σ ⋆ ) E Z(ϕ E ) + (1 -p) • ϕ d(σ,σ ⋆ ) N E Z(ϕ N E )Here c(T ) is a constant depending only on the subset T . Using the above identity we obtain the following lower bound on V (σ ⋆ ).V (σ ⋆ ) ≥ p • 1 Z(ϕ E ) + (1 -p) • 1 Z(ϕ N E ) σ p • ϕ d(σ,σ ⋆ ) E Z(ϕ E ) + (1 -p) • ϕ d(σ,σ ⋆ ) N E Z(ϕ N E )We can also obtain the following upper bound on V (τ ).V (τ ) ≤ p • ϕ E Z(ϕ E ) + (1 -p) • ϕ N E Z(ϕ N E ) min σ p • ϕ d(σ,τ ) E Z(ϕ E ) + (1 -p) • ϕ d(σ,τ ) N E Z(ϕ N E )We now use the relationship p < (1 -p) and ϕ E < ϕ N E to improve the bounds. We will also writeZ(ϕ, k) = σ ϕ d(σ,τ ). V (σ ⋆ ) ≥ 2p Z(ϕ N E ) 2(1-p)Z(ϕ N E ,k) Z(ϕ E ) = p 1 -p Z(ϕ E ) Z(ϕ N E ) 1 Z(ϕ N E , k) V (τ ) ≤ 2 • (1-p)ϕ N E Z(ϕ E ) 2p • ϕ k(k-1)/2 E Z(ϕ N E ) = 1 -p p Z(ϕ N E ) Z(ϕ E ) ϕ k(k-1)/2 ETherefore, in order to have V (σ ⋆ ) ≥ 2V (τ ) we need the following inequality to hold.p 1 -p Z(ϕ E ) Z(ϕ N E ) 1 Z(ϕ N E , k) ≥ 2 • 1 -p p Z(ϕ N E ) Z(ϕ E ) ϕ k(k-1)/2 EHere, we provide screenshots of different phases of our MTurk survey. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [No] Justification: The experiments can be run on any computer.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.This paper also explored various elicitation techniques combining vote and prediction questions based on only top choice and complete rankings.This is the direct application of SP algorithm[36] by considering m! possible ground truths.This study received IRB approval from the ethics board, which is available upon request.The dataset can be found here -https://github.com/amrit19/Surprisingly-Popular-Voting-Partial 
 
 Appendix:  


Decision: The reviewers were initially mixed on this paper, but throughout the rebuttal process they were raised significantly. The paper is overall well-motivated and has compelling empirical results. I had some concerns about writing quality, but the authors were responsive throughout the review process and the typos identified by reviewers are all easily fixable. The authors also concerningly had an error in one of their evaluation methods, but they claim to have fixed it. Lastly, they responded to (extremely minor) ethical considerations raised by ethics review for their use of MTurk. 

Personally, I found the paper compelling. The authors' main theoretical result for sample complexity isn't the most technically complex, but the paper's main contribution is on the empirical side. The main weakness identified by reviewers was a very related paper ([25]) that only differed in the size of the partial rankings elicited (pairwise vs. k). However, the authors did a good job explaining why this paper made a meaningful contribution past [25], and they will add it to the final draft.

Reviews: review: paper_summary: paper_summary: The paper extends the previous work of (Hosseini et al. 25) by overcoming a major weakness: eliciting a full ranking and a prediction about the ranking is too costly. The paper designed a method that elicit partial preferences and recover the full ranking by aggregating partial rankings. They empirically test the method through a large-scale crowdsourcing experiment on MTurk and show their approaches outperform conventional preference aggregation algorithms for the recovery of ground truth rankings. They analyze the collected data and demonstrate that voters' behavior in the experiment, including the minority of the experts, and the SP phenomenon, can be correctly simulated by a concentric mixtures of Mallows model. Finally, they provide theoretical bounds on the sample complexity of the proposed methods.
strength_weakness: strength_weakness: The primary technique follows the methodology of Hosseini et al. (25), with a relatively simple extension. Nonetheless, I do not see the technical contribution as the most important contribution of the work.
questions: questions: None.
limitations: limitations: Yes.
paper_summary: paper_summary: This paper studies the problem to recover the ground truth ordering over a large number of alternatives. The assumption is that the ground truth ranking is drawn from a prior, and each voter observes a noisy version of the ground truth. It was previously shown that the surprisingly popular (SP) algorithm could recover the ground truth even when experts are in minority. In this paper, the authors propose Aggregated-SP and Partial-SP, that ask voters to report vote and predictions on a subset of alternatives in terms of top alternative, partial rank, or an approval set. Experimental results show that the proposed algorithms outperform conventional preference aggregation algorithms for the recovery of ground truth rankings. The authors also provide theoretical bounds on the sample complexity of SP algorithms with partial rankings.
strength_weakness: strength_weakness: The theoretical assumptions in Section 6 are somehow constrained, especially Assumption 1.
questions: questions: * In the introduction, the authors mention that the Surprisingly Popular Voting algorithm can recover the ground-truth ranking. I wonder if this is a theoretical guarantee or empirical / experimental.
* Have you compared different aggregation algorithms for other elicitation formats besides Rank-Rank as shown in Figure 4?
* Is it possible to show that recovering the true partial ranking is impossible if Assumption 1 is not true?
limitations: limitations: The authors discuss limitations and future directions in the paper, including exploring the setting of SP beyond the majority-minority dichotomy, or with malicious voters.
paper_summary: paper_summary: The paper generalizes the surprisingly popular algorithm to the partial ranking setting. The prior method that considers this generalization only works when every agent provides her signal over the full ranking. The current paper considers how to elicit only partial information from agents and aggregate them using SP. The proposed method can scale with the number of items. Furthermore, the paper proposes a model to capture the responses from human agents, which can be used for theoretical analysis.
strength_weakness: strength_weakness: * First of all, the prior paper [25] seems to greatly discount the contribution (and effort) of this work. In particular, they use the same datasets, very similar experimental designs, and the same model. However, the current paper only speaks about the high-level differences between these two papers. In particular, as stated in line 98, [25] seems to elicit pairwise comparison from agents and then aggregate them, which is pretty much the proposed method Partial-SP. The only difference I can see is that Partial-SP allows k partial rankings while [25] only uses 2. I could be wrong about [25], but the authors should have a more detailed comparison. Also, it doesn’t seem the method in [25] is considered as a baseline. Why not?
* In line 310, “As seen 310 from the posterior distributions for the dispersion parameters in Figure 5 synthetic data generation 311 process accurately replicates real data characteristics”. I’m not sure how “accurate this is as the distributions for non-expert seem to be way off. How confident can we trust the considered model for downstream theoretical analysis?
* In line with the previous comment, is the same dataset used to fit the model, then compared with the simulated data as shown in Figure 5? Or was the dataset separated into a training set and a test set? If it’s the former, how do we know if Figure 5 is not overfitting the data? A lot of the content is left in the Appendix, but some of it is necessary to understand the results, so it might be better to have it back.
questions: questions: See weakness
limitations: limitations: Limitations are fairly discussed
paper_summary: paper_summary: Surprisingly popular voting allows to value expertise by eliciting both judgments and predictions over others' judgments. Its application to ranking is however challenged by the combinatorial size of reporting predictions over others' judgments. This paper provides practical solutions to adapt surprisingly popular voting to sparser elicitations. In particular, the authors apply this to MTurk's inputs, and show that their solutions outperform classical voting solutions. Theoretical guarantees of ground-truth recovery are also provided.
strength_weakness: strength_weakness: I found the paper quite hard to read. Key comprehension elements, such as how sparse elicitations are turned into pairwise voting inputs, or the principles of the new algorithms, are poorly explained in the main text. Even Appendix D is hard to parse (what if $a$ and $b$ are both approved? What if none is selected? Do we consider $v_i^{(a,b)}$ undefined?), with many typos (in Algorithm 2 and Algorithm 3, I don't understand what $Q$, $Q_j$, $G$ and $GT$ stand for, and how they differ).

The simulations given concentric mixtures of Mallows models also yields good insight. However, I am not sure they are convincing, because of the fact that non-expert's rankings are statistically centered around the ground truth as well. If so, this greatly undermines the story-telling of the paper, which is about valuing expertise (through SP).

The theoretical guarantees seem far from tight.

I am not quite convinced by the subset selection (line 177). 

There are many imprecisions in the text:
- Line 46: "will provably recover" => it should be stressed that this depends on many assumptions. Typically, SP requires Bayesian agents, with a common prior, which update correctly based on their signals, report truthfully their vote and are numerous to avoid statistical fluctuations.
- Line 307: "using Bayesian inference" => As I understand, what was used was a MCMC sampling of the posterior, which only has statistical asymptotical properties. This is a far cry from Bayesian inference.
- Line 131: "definition 1" => Not sure what this refers to. Do you mean "equation (1)" ?
- Line 138: "definition 3" => Not sure what this refers to. Do you mean "equation (3)" ?
questions: questions: Do I understand correctly that, in Partial-SP, we compute for each voter a set of pairwise comparisons $a \succ b$, each of which unbiases non-expertise with SP? And that the resulting voter-wise sets of unbiased comparisons are aggregated through a voting rule?

Corollary 1 says $n \geq \Omega(k!)$ inputs are needed *for all subsets of $S$*. Does this imply that the total number of inputs must be exponential in $S$?

More generally, I am surprised that, in the proposed Mallows models, $k!$ inputs are needed. I would have guessed that $k^2$ are sufficient, as it suffices to be correct on all comparisons of pairs of alternatives. I even feel that this insight should hold for SP with a non-expert ranking distribution that is not centered on $\pi^\star$. Would the authors agree?

First, what value $s$ is chosen? More importantly, it feels that two human subjects will either likely have zero or many (around k/2) alternatives to compare in common. Why would this be preferable to random subsets? What about minimizing the number of pairs of subjects that have $< 2$ alternatives in common?

I am quite open to increasing my rating, depending on the authors' response.
limitations: limitations: One limitation that failed to be highlighted is the dependency of the new algorithms on hyperparameters $\alpha$ and $\beta$. Not mentioning this is misleading as it suggests that the new algorithms are less arbitrary than they actually are.

I am disturbed by the conclusion on "political polling or collective moderation of online content". While expertise is clearly lacking and not uniformly distributed, it is questionable the extent to which SP (and variants) should be applied to such issues, where there is arguably no ground truth (formally, there is no "common prior" of the SP model). I would have appreciated adding caveats, and perhaps a mention of the (exciting) social science / philosophy questions that generalizing SP to such topics would raise.

Comments: title: Post-rebuttal
comment: Thank you very much. This is very interesting.
We could not find the source for the CBC's article but a similar and relevant article titled - "Election Polls Are More Accurate if They Ask Participants How Others Will Vote", can be found online where they talk about using the surprisingly popular method in Polling. Due to guidelines, we cannot directly share the link here but we'd be happy to furnish more details about this source if needed.
We thank the reviewer for their comments and have provided the answers to their questions below:

## (1) Provide more information on the informed consent process and measures to ensure participant privacy and data security.

Before starting the survey, participants must agree to, and accept a consent form that outlines the benefits, risks, privacy measures, confidentiality assurances, and consequences of withdrawal. The form also provided contact information for both the researchers and the human research protection program in case participants have additional concerns.
The only benefit detailed is monetary compensation for survey completion, and there are no identified risks. The privacy and confidentiality section assures that personally identifiable information will be kept confidential and never used or shared. Only the answers to research-related questions and the time taken to complete the survey are used for analysis.
Data provided by participants are stored on protected servers. The only identifiable data that was collected to maintain data uniqueness was the MTurk worker ID but it will not be made public. All identifiable information has been removed from the data before analysis. Participation is entirely voluntary, and participants may withdraw at any time by closing their browser. However, monetary compensation is only provided upon survey completion. 
The study has gone through a thorough IRB approval process by the IRB and Ethics office at a major university.

## (2) Discuss the potential biases introduced by using MTurk.

Data collected on MTurk could be biased and could have issues. We identify potential biases in conducting experiments on MTurk and will include these in the final version of the paper. These biases include:

Sampling bias - Sample of people responding in MTurk might not represent the opinion of a larger demographic.

Geographic bias - Limiting responses to a Geographic location (US and Canada) in our case might also introduce locational bias in the data. If the requirement is to focus on a certain geographic location due to research objectives,  Turkers could use VPNs and thus, the sample collected may not be a true representation of that geographical population.

Socioeconomic bias - MTurk workers are often motivated by financial incentives, which may overrepresent individuals from lower socioeconomic backgrounds.

Technological bias - MTurk requires internet access and basic technological literacy, potentially excluding certain populations.
I thank the authors for their response. I have raised my score.
Out of personal curiosity, the authors wrote that CBC in Canadian elections used the surprisingly popular vote. I would be very interested to have the source of the information (or of similar political uses of the vote).
I appreciate the author's rebuttal. I have raised my score.
I thank the authors for their helpful rebuttal. While I believe that the paper has still a lot of room for improvements in terms of writing, proofs (by replacing $k!$ by $k^2$) and synthetic experiments (by a more careful analysis of non-centered non-experts), I have upgraded my rating to 5.