Proceedings

Correlated Voting

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 366-371.

© 2016 International Joint Conferences on Artificial Intelligence

Abstract

We study the social choice problem where a group of n voters report their preferences over alternatives and a voting rule is used to select an alternative. We show that when the preferences of voters are positively correlated according to the Kendall-Tau distance, the probability that any scoring rule is not ex post incentive compatible (EPIC) goes to zero exponentially fast with the number of voters, improving over the previously known rate of 1/√n for independent preferences. Motivated by rank-order models from machine learning, we introduce two examples of positively-correlated models, namely Conditional Mallows and Conditional Plackett-Luce. Conditional Mallows satisfies Kendall-Tau correlation and fits our positive result. We also prove that Conditional Plackett-Luce becomes EPIC exponentially quickly.

  1. [Altman and Tennenholtz, 2010] Alon Altman and Moshe Tennenholtz. An Axiomatic Approach to Personalized Ranking Systems. J. ACM, 57(4), 2010. IJCAI
  2. [Baharad and Neeman, 2002] Eyal Baharad and Zvika Nee- man. The Asymptotic Strategyproofness of Scoring and Condorcet Consistent Rules. Review of Economic Design, 7(3):331-340, 2002.
  3. [Barberà, 2011] Salvador Barberà. Strategyproof Social Choice. Handbook of social Choice and Welfare, 2:731- 831, 2011.
  4. [Bhargava et al., 2011] Mohit Bhargava, Dipjyoti Majum- dar, and Arunava Sen. Incentive-Compatible Voting Rules with Positively Correlated Beliefs. Available at http:// www.isid.ac.in/ ⇠ asen/ papers/ ms.pdf/ , version : April 10, 2011. Link
  5. [Conitzer and Walsh, 2016] Vincent Conitzer and Toby Walsh. Barriers to Manipulation in Voting. Handbook of Computational Social Choice, Forthcoming, 2016.
  6. [Durrett, 2010] Rick Durrett. Probability: Theory and Ex- amples. Cambridge university press, 2010.
  7. [Faliszewski and Procaccia, 2010] Piotr Faliszewski and Ariel D Procaccia. AI's War on Manipulation: Are We Winning? AI Magazine, 31(4):53-64, 2010.
  8. [Gibbard, 1973] Allan Gibbard. Manipulation of Voting Schemes: A General Result. Econometrica, pages 587- 601, 1973.
  9. [Hoeffding, 1963] Wassily Hoeffding. Probability Inequali- ties for Sums of Bounded Random Variables. Journal of the American statistical association, 58(301):13-30, 1963.
  10. [Hunter, 2004] David R Hunter. MM Algorithms for Gener- alized Bradley-Terry Models. Annals of Statistics, pages 384-406, 2004.
  11. [Lang and Xia, 2009] Jérôme Lang and Lirong Xia. Sequen- tial Composition of Voting Rules in Multi-Issue Domains. Mathematical Social Sciences, 57(3):304-324, 2009.
  12. [Luce, 1959] R.. Ducan Luce. Individual Choice Behavior : A Theoretical Analysis. John Wiley and sons, 1959.
  13. [Majumdar and Sen, 2004] Dipjyoti Majumdar and Arunava Sen. Ordinally Bayesian Incentive Compatible Voting Rules. Econometrica, 72(2):523-540, 2004.
  14. [Mallows, 1957] Colin L Mallows. Non-Null Ranking Mod- els. Biometrika, pages 114-130, 1957.
  15. [Mao et al., 2013] Andrew Mao, Ariel D. Procaccia, and Yil- ing Chen. Better Human Computation Through Principled Voting. In Proceedings of the Twenty-Seventh AAAI Con- ference on Artificial Intelligence, July 14-18, 2013, Belle- vue, Washington, USA., 2013.
  16. [Marden, 1996] John I Marden. Analyzing and Modeling Rank Data. CRC Press, 1996.
  17. [Parkes et al., 2015] David C. Parkes, Ariel D. Procaccia, and Nisarg Shah. Beyond Dominant Resource Fairness: Extensions, Limitations, and Indivisibilities. ACM Trans- actions on Economics and Computation, 3(1):3, 2015.
  18. [Pennock et al., 2000] David M. Pennock, Eric Horvitz, and C. Lee Giles. Social Choice Theory and Recommender systems: Analysis of the Axiomatic Foundations of Col- laborative Filtering. In Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intel- ligence, pages 729-734. AAAI Press, 2000.
  19. [Plackett, 1975] Robin L Plackett. The Analysis of Permuta- tions. Applied Statistics, pages 193-202, 1975.
  20. [Satterthwaite, 1975] Mark Allen Satterthwaite. Strategy- Proofness and Arrow's Conditions: Existence and Cor- respondence Theorems for Voting Procedures and So- cial Welfare Functions. Journal of Economic Theory, 10(2):187-217, 1975.
  21. [Sen et al., 2015] Arunava Sen, Mohit Bhargava, and Dipjy- oti Majumdar. Incentive-Compatible Voting Rules with Positively Correlated Beliefs. Theoretical Economics, 10(3):867-885, 2015.
  22. [Slinko, 2002] Arkadii Slinko. On Asymptotic Strategy- Proofness of Classical Social Choice Rules. Theory and Decision, 52(4):389-398, 2002.
  23. [Young, 1975] H Peyton Young. Social Choice Scoring Functions. SIAM Journal on Applied Mathematics, 28(4):824-838, 1975.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards