The Surprising Effectiveness of SP Voting with Partial Preferences

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.

Strengths

The paper provides original solutions to generalize surprisingly popular (SP) voting to sparse elicitation, which is strongly needed in many practical applications. As such, they address an important problem, with effective results. Interestingly, the paper actually provides two solutions, and empirically show that one clearly outperforms the other (and classical voting). This is a valuable insight for this research question.

Weaknesses

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

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.

Rating

5

Confidence

3

Soundness

2

Presentation

1

Contribution

3

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.

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.

Strengths

* Generalizing existing methods for broader real-world applications is very necessary. The paper, overall, is making non-trivial progress in this direction. * The paper proposes a theoretically trackable model to capture agents’ behaviors while reporting ranking information. If calibrated (I think we should be careful to claim calibration here, see weakness), the model can be useful for future research on ananlyzing crowdsourcing of ranking data. * The experiments are robust: tested on three datasets, measured using various methods, and compared with multiple baselines.

Weaknesses

* 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

See weakness

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

2

Limitations

Limitations are fairly discussed

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.

Strengths

This paper extends previous work on the SP algorithms to only require the voters to report predictions on a subset of alternatives instead of for all the alternatives. Human generated datasets are used to evaluate the proposed algorithms. The experiments are well designed and clearly described. The results are sufficiently analyzed and discussed. Finally, sample complexity is analyzed under a Mallows model distribution assumption.

Weaknesses

The theoretical assumptions in Section 6 are somehow constrained, especially Assumption 1.

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?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

2

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.

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.

Strengths

The paper tackles an intriguing problem and addresses a significant flaw in previous approaches: the impracticality of eliciting full rankings and making predictions about those rankings in real-world scenarios. The authors develop simple methods to mitigate this issue by eliciting and aggregating partial rankings. They test the effectiveness of their approach through real-world experiments and introduce a novel explanation of voters' behavior based on the data. I see the experimental results as the primary contribution of the work, given that previous literature on the topic has been largely theoretical. It is particularly nice that the authors apply their method in practical settings and prove its effectiveness. Additionally, their analysis of sample complexity offers a valuable theoretical contribution.

Weaknesses

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

None.

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

4

Limitations

Yes.

Post-rebuttal

I appreciate the author's rebuttal. I have raised my score.