Metric Distortion Under Probabilistic Voting

Thank you very much for your detailed and constructive feedback.

Clarification on the proof of Lemma 3

Indeed, as you note, just using the constraint $|d_i - b_i| \leq d_i + b_i$ will not be sufficient to obtain the required constraint in problem (7). However, we additionally have that $|d_i - b_i| \leq d(W,B)$ for all voters $i \in \mathcal{N}$ and $d_i + b_i \geq d(W,B)$ for all voters $i \in \mathcal{N}$. Here $d(W, B)$ is the distance between candidates W and B. We use this in Line 217 of the paper. This now implies that $\max_{i \in \mathcal{N}} |d_i - b_i| \leq d(W,B)$ and $\min_{i \in \mathcal{N}} (d_i + b_i) \geq d(W,B)$, leading to the conclusion that $\max_i |d_i - b_i| \leq \min_i (d_i + b_i)$. This is what we use in the optimization problem (7). Now, the problem in (7) is finding the minimum over a bigger set than that implied by using all voter-wise constraints $|d_i - b_i| \leq d(W,B)$ and $d_i + b_i \geq d(W,B)$. Therefore, the result holds. Hope this addresses your concerns in the proof of Lemma 3. We acknowledge that the proof in the paper is a bit too brief; we will add further explanation for clarity.

Intuition for why the Copeland bound is not tight

In the deterministic case, we first provide a straightforward analysis establishing a distortion bound of 3×3=9 for the Copeland Rule. Consider any Copeland winner W; it must belong to an uncovered set [1,Theorem 15]. Let X be the socially optimal candidate. Here, either (a) W defeats X in a pairwise contest, or (b) there exists a candidate Y such that W defeats Y in a pairwise contest, and Y defeats X in their pairwise contest.

According to [1], for any two candidates, A and B, where A defeats B in a pairwise contest, the ratio of their social costs is bounded by 3. Consequently, the distortion of the Copeland winner is bounded by 3×3=9, which comes from case (b) above. Our analysis of the Copeland Rule in the context of probabilistic voting follows a similar approach by multiplying the ratios of social costs, as outlined in Line 240.

In the deterministic case, a more nuanced analysis of the Copeland Rule, which considers more details of the problem's geometric structure, can achieve a distortion of 5. The proof is in [1]. However, we lack a comparable technique that works within our probabilistic voting framework, so we have a looser analysis. Enhancing this analysis for the Copeland Rule is an intriguing direction for future research.

Regarding using the distortion framework beyond ranking-based voting rules

Thank you for mentioning this exciting idea. Indeed, distortion is a domain-specific name for the classic worst-case analysis in theoretical CS. The study of ranking-based rules is motivated by the fact that real-world elections often use ordinal preferences as opposed to eliciting cardinal utilities. Given noisy or adversarial votes, studying the worst-case performance of the geometric median rule would be a very interesting question.

References

[1] Elliot Anshelevich, Onkar Bhardwaj, and John Postl. Approximating optimal social choice under metric preferences. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pages 777–783, 2015.

Thank you for your review. We have tried to address your concern regarding the relevance of our paper to the NeurIPS community in the overall response, we will mention that again here.

As Reviewer 2kBY observed, the increasing significance of social choice in machine learning, and the importance of handling noisy inputs within embedded vector spaces, underscores the timeliness and relevance of our work to the machine-learning community. Preference models, such as the Plackett-Luce model [1] , have been instrumental in AI alignment, especially through techniques like Reinforcement Learning from Human Feedback (RLHF) [2,3,4,5] and the more recent Direct Preference Optimization (DPO) [6]. These methods incorporate user preferences into AI models, where voting rules are critical in aggregating these preferences. Investigating how these rules perform in the distortion framework under probabilistic voting scenarios can provide valuable insights into refining AI alignment processes.

Moreover, the relevance of our work is further supported by prior NeurIPS publications that have explored related topics, such as random utility models [7] and the smoothed analysis of social choice rules [8]. These connections affirm the alignment of our research with the themes and interests of the NeurIPS community.

References

[1] Robin L Plackett. The analysis of permutations. Journal of the Royal Statistical Society Series C: Applied Statistics, 24(2):193–202, 1975.

[2] Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems, volume 30, 2017.

[3] Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. arXiv preprint arXiv:2203.02155, 2022.

[4] Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, and Paul F Christiano. Fine-tuning language models from human preferences. arXiv preprint arXiv:1909.08593, 2019.

[5] Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel M Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul Christiano. Learning to summarize with human feedback. In Advances in Neural Information Processing Systems, volume 33, pages 3008–3021, 2020.

[6] P. W. Koh, K. Zhuang, and S. Lee. Direct preference optimization. arXiv preprint arXiv:2205.01659, 2022.

[7] Hossein Azari, David Parks, and Lirong Xia. Random utility theory for social choice. Advances in Neural Information Processing Systems, 25, 2012.

[8] Lirong Xia. The semi-random satisfaction of voting axioms. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34,

Thank you for your feedback. We agree that the presentation could be improved, and we are happy to incorporate the suggestions in the final version.

Regarding the motivation behind Axiom 2

We acknowledge that Axiom 2 (Independence of Other Candidates) may not always hold in certain real-life scenarios, where the presence of additional candidates could indeed influence a voter's probability of ranking one candidate over another. However, this assumption is well-established and widely accepted in the field of social choice theory [4,5,6,7,8]. Additionally, models such as Bradley-Terry and Plackett-Luce [9] also adhere to this axiom and have demonstrated significant applicability in machine learning and AI alignment contexts [10,11,1,2,3]. This widespread acceptance and practical utility underscore the relevance of Axiom 2 in our work.

Regarding the number of voting rules analyzed

While we understand the reviewers' concern about the limited number of rules presented, the core contribution of our paper is the introduction of a novel model that combines the distortion framework with the concept of probabilistic voting. The three rules we analyze are sufficiently distinct and incorporate innovative mathematical techniques, making them valuable contributions in their own right.

Extending our analysis to other rules, such as Borda and Plurality Veto, would require the development of new techniques that are likely to differ significantly from those presented here. Therefore, we have chosen to leave this as an area for future research.

References

[1] Paul F. Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems, volume 30, 2017.

[2] Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. arXiv preprint arXiv:2203.02155, 2022.

[3] P. W. Koh, K. Zhuang, and S. Lee. Direct preference optimization. arXiv preprint arXiv:2205.01659, 2022.

[4] Kenneth J. Arrow. Social Choice and Individual Values. John Wiley and Sons, New York, 1951.

[5] Amartya Sen. Collective Choice and Social Welfare. Holden-Day, San Francisco, 1970.

[6] Allan Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41(4):587–601, 1973.

[7] Mark Allen Satterthwaite. Strategy-proofness and arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10(2):187–217, 1975.

[8] Donald G. Saari. The symmetry and complexity of the voting problem. Journal of Economic Perspectives, 9(1):93–105, 1995.

[9] Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: I. The method of paired comparisons. Biometrika, 39(3/4):324–345, 1952.

[10] David R. Hunter. Mm algorithms for generalized bradley–terry models. The Annals of Statistics, 32(1):384–406, 2004.

[11] Tzu-Kuo Huang, Ruby C. Weng, and Chih-Jen Lin. Generalized bradley–terry models and multi-class probability estimates. In Proceedings of the 23rd international conference on Machine learning, pages 425–432. ACM, 2006.

Thank you for your feedback on our paper. We acknowledge that there is scope for improvement in the presentation of the paper and rearrange the order in which some concepts are introduced. We also agree with the reviewer that our explanations of the probabilistic models could have been more detailed. We are happy to take these suggestions into account while creating the final version.

We want to clarify that all our results apply to the entire class $\mathbf{G}$. Plackett-Luce (PL) and Pairwise Quantal Voting (PQV) are highlighted in our paper because they are well-known in the social choice and machine learning (AI alignment) literature, which is why we provided precise numerical values for these specific cases. However, the structural results on the upper and lower bounds are general and applicable to any member of the class $\mathbf{G}$.