The Surprising Effectiveness of SP Voting with Partial Preferences

We thank the reviewer for the valuable feedback. They are very helpful and we will incorporate them in the next version of the paper.

“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? ...”

The right way to think about Partial-SP is the following: for each subset (not voter), we compute a set of pairwise comparisons a>b after collecting votes from the voters. Then SP unbiases non-expertise to give us unbiased ranking over the subsets (each of size $k$). Then the resulting partial rankings are aggregated through a voting rule to generate a ranking over the $m$ alternatives.

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

Corollary 1 uses theorem 1 for the sample complexity results which derives bounds for a naive version of the SP algorithm. Theorem 1 treats each of the k! permutations as possible ground truths and picks the ranking with largest prediction-normalized score. The sample complexity is approximately $O(G \sqrt{\log G})$ where G is the number of possible ground truths. For $G=k!$ we get the sample complexity bound of $\tilde{O}(k! \sqrt{k})$. It is straightforward to consider a version that applies SP-voting to each pairwise preference and then aggregates them. For a pairwise preference, $G = 2$ and as long as $n \ge O(\sqrt{\log(k/\delta)}$ SP-voting can recover the pairwise preference with prob at least $1-\delta/k^2$. Therefore, by a union bound, the total number of samples required to recover the ground truth over a subset of size k is $\tilde{O}(k^2)$.

“More generally, I am surprised that, in the proposed Mallows models, k! inputs are needed...”

As mentioned above, the bound of $\tilde{O}(k!)$ is needed only when one applies a naive version of the SP algorithm. The reviewer is right that the total sample complexity can be reduced to $O(|S| \cdot k^2 \log (|S| k / \delta) )$ when one applies SP-voting to each pair within a subset. However, even with the naive version of the SP algorithm the total sample complexity $\tilde{O}(|S| \cdot k!)$ can be better than $m^2$ when $|S| = O(m)$ and $k = o(\log m)$. This is precisely our setting since the subset size $k$ is $5$ or $6$ and the total number of alternatives in the ground truth is $m = 35$, and hence $k! < m^2$.

“First, what value s is chosen? … Why would this be preferable to random subsets? ...”

We chose stepsize $s$ to be $6$. Through simulation, we observed that increasing subset size ($k$) and step size ($s$) results get better but step size $6$ was a fair number to balance cognitive load and also create overlaps between subsets. The main idea is to choose subsets that have alternatives in common. Then we can estimate the partial rankings of each subsets and use transitivity of rankings to infer a global ranking over the $m$ alternatives. If we choose subsets uniformly at random then we will need a lot of subsets (and hence a lot of voters) before we have high overlap among different subsets. This is the reason we fixed the choice of the subsets and then determined assignments to voters through an integer programming which guarantees that all the voters report approximately an equal number of comparisons.

“One limitation that failed to be highlighted is the dependency of the new algorithms on hyperparameters $\alpha$ and $\beta$ ...”

We have highlighted the dependency of the new algorithms on hyperparameters $\alpha$ and $\beta$ in the appendix (line 662). Using grid search, we observed that as long as $\alpha > 0.5$ and $\beta < 0.5$, the new algorithms recover similar results. This means that the algorithms are robust to the choices of the hyperparameters $\alpha$ and $\beta$.

“I am disturbed by the conclusion on "political polling or collective moderation of online content"...”

Thank you for raising the issue of extending SP to social science/philosophy questions! We would like to point out that SP is already being used in a couple of applications.

• Polling opinions in political elections e.g. by CBC in Canadian elections.
• Some conferences have been experimenting with SP type methods for ranking papers by asking reviewers to score a paper and also provide a prediction of what they think scores of others will be (EC and ICML this year).

The main difficulty is that most of the questions in these domains are inherently subjective with no ground truth. Therefore, it is difficult to determine the expertise of a voter and more research is needed to determine what should be the right framework for differentiating voters.

“The simulations given concentric mixtures of Mallows models also yields good insight. However, I am not sure they are convincing…”

• Yes, the non-expert’s rankings are statistically centered around the ground truth, however, note that their distance from the ground truth ranking is around 0.7 in terms of average Kendall-Tau distance. There was a minor bug in our code and the new plots are attached with the rebuttal, see figures 1 and 2. An alternative would be a mixture model with two centers where experts and non-experts report close to their own centers (respectively $\pi^\star_E$, and $\pi^\star_{\textrm{NE}}$). However, we believe this is not the right model for our setting as there is already an objectively correct ranking over all the alternatives.

• Furthermore, to demonstrate that the second type of mixture model is unsuitable for our setting, we conducted a comparative analysis. We selected ground-truth as centers for experts, while for non-experts, we chose random centers within a [0,1] range of Kendall's tau distance from the ground truth. Figure 3 in our NeurIPS Rebuttal plot illustrates the resulting poor fit, highlighting a significant lack of overlap between the non-expert distributions in synthetic data compared to real data.

We thank the reviewer for insightful feedback. Below we provide detailed responses to the questions.

“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.”

• We would like to highlight that our work is significantly different than [25] and not a natural extension of prior work. [25] is interested in recovering a ground truth over (m=4) alternatives by presenting these same alternatives to all voters and asking for various reports. We, on the other hand, are interested in recovering ground truth over a large number of alternatives ($m\sim 30$) by asking reports on smaller subsets ($k=5,6$). This introduces two new challenges – design of new elicitation formats for partial preferences (e.g. Approval(t)-Rank as mentioned in line 151), and figuring out how to extend SP-voting for handling partial preferences.

• Although we adopt a randomized experimentation framework similar to [25], there are two differences. First, we need to determine which subsets (of size $k\ll m$) we should use to elicit partial information. Having too many subsets will blow up the sample complexity, and having too few (or non-overlapping) subsets will render the problem impossible. Besides, as mentioned above, we also consider the design of new elicitation formats suitable for partial reports.

• We don’t use the dataset used by [25], and in fact, the dataset is not even applicable for our setting. This is because, in their experiment, the voters provide reports (vote or prediction) under the instruction that the considered set of 4 alternatives are the only alternatives in the ground truth. Moreover, the subsets in the datasets are non-overlapping and cannot help us recover a ground truth over the $m$ alternatives.

“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.”

For handling partial preferences, we propose two methods – Partial-SP and Aggregated-SP. The first method, Partial-SP goes beyond just eliciting pairwise comparisons and aggregating them. The main idea is to first determine the correct partial rank for each subset (by eliciting any type of information be it approval, rank, etc.) and then aggregating them through a voting rule. As discussed in the introduction, applying the basic version of SP-voting requires eliciting $O(m^2)$ pairwise information which can be large. Hence the generalization of $k > 2$ is important and non-trivial. Besides, partial-SP applies SP-voting at each subset level and then aggregates them through a voting rule, and in that sense, it is significantly different than the prior work [25]. Furthermore, the second algorithm, Aggregated-SP, offers a different perspective on handling partial preferences in the SP voting framework. In lines 161-176 we only provide an outline of the two algorithms because of limited space, but we can definitely move some details from the appendix.

“Also, it doesn’t seem the method in [25] is considered as a baseline. Why not?”

It's important to note that SP-voting [25] requires pairwise preference data for all $O(m^2)$ pairs as it builds a tournament over the m alternatives by applying SP-voting on each pair. When m is large (e.g. $m\sim 30$ for our setting) and it is impossible to collect human preferences (vote and report) for all pairs. Therefore, because of the missing data, SP-voting algorithm cannot be evaluated. Our novelty lies in generalizing SP-voting with partial preferences, eliciting O(mk) amounts of information and yet recovering the ground truth over m alternatives.

“ 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?”

• Thank you for your observation. Upon re-evaluating our parameter inference approach, we identified that the scipy.stats.kendalltau function we used computes Kendall's tau correlation, and not Kendall's tau distance. This distinction led to discrepancies in the non-expert distributions between real and synthetic data. We have addressed this by implementing the correct Kendall's tau distance metric. Figures 1 and 2 in our NeurIPS Rebuttal plots file show the updated plots with a perfect fit, particularly for the Movie domain (figure 1).

• When combining all datasets, we observe significant overlap in individual expert and non-expert distributions, as well as a prominent distinction between expert and non-expert groups in terms of Kendall's tau distance. Although there is some mismatch between the original data and synthetic data for the non-experts, we believe this is because of a limited number of samples, and heterogeneity of different domains.

“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? “

Yes, we used the whole dataset to fit the model, sampled from the posterior of the fitted model, and then checked the overlap. The practice of splitting the dataset into test and training sets is common in supervised learning setting. We work in a Bayesian setting where different types of checks (e.g. posterior predictive checks) are used to determine the fitness of a model. Additionally, we have a limited number of samples, and that's another reason we used the whole dataset to fit the model.

We thank the reviewer for the feedback and insightful questions. Below we provide answers to the 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.”

Theorem 3 of Prelec et al. [36] guarantees that the Surprisingly Popular Voting (SP-Voting) can recover the ground-truth ranking with a probability of 1 as the number of voters approaches infinity (As written in line 46 in our paper). Note that this guarantee holds only with infinite data, and to the best of our knowledge, theorem 1 in our paper is one of the first results providing finite-sample guarantees for SP-type algorithms.

“Have you compared different aggregation algorithms for other elicitation formats besides Rank-Rank as shown in Figure 4?”

Yes, we have compared different aggregation algorithms for all the elicitation formats used in our study and have shown the results in Figure 9 and Figure 10 of Appendix G.3.

“Is it possible to show that recovering the true partial ranking is impossible if Assumption 1 is not true?”

• If Assumption 1 is not true, then either $p$ (fraction of experts) is very small or the dispersion parameter of the non-experts ($\phi_\textrm{NE}$) is very large. First, suppose $\phi_{\textrm{NE}}$ is large (e.g. arbitrarily close to $1$) then the distribution $Pr_s(\pi | \pi^\star, \phi_{\textrm{NE} })$ is almost a uniform distribution and has no information about the true rank $\pi^\star$. In such a scenario if $p$ is also very small ($\approx 0$), then the signal distribution $Pr_s(\pi_i | \pi^\star)$ is almost a uniform distribution, and, the prediction distribution of both the experts and the non-experts are similar. Both will predict approximate uniform distribution, and it is impossible to recover the true ranking. Once either $p$ increases or $\phi_{\textrm{NE}}$ decreases, then either the prediction distribution of the experts will change ($p$ bounded away from $0$) or the signal distribution will be concentrated around $\pi^\star$ (when $\phi_{\textrm{NE}} \ll 1$), making identification possible.

• We would like to point out that for applying the SP algorithm to more than two alternatives, Prelec et. al. [36] also required a condition on the underlying data generating process ($P(v_i|s_i) > P(v_i|s_j)$). Our condition is adapted for the specific case of concentric Mallows model, and implies their condition. We believe it might be possible to obtain a better trade-off between the parameters $p$ and $\phi_{\textrm{NE}}$ through a more sophisticated analysis, but a condition specifying the trade-off between the two parameters is necessary for identifying the true rank.

Dear reviewer, thank you for your feedback and insightful comments. If you have additional questions, do let us know and we will be happy to answer them.