Abstract
Classical voting rules assume that ballots are complete preference orders over candidates. However, when the number of candidates is large enough, it is too costly to ask the voters to rank all candidates. We suggest to fix a rank k, to ask all voters to specify their best k candidates, and then to consider “top-k approximations” of rules, which take only into account the top-k candidates of each ballot. We consider two measures of the quality of the approximation: the probability of selecting the same winner as the original rule, and the score ratio. We do a worst-case study (for the latter measure only), and for both measures, an average-case study and a study from real data sets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
Interestingly, [3] give another optimal rule (thus with same worst-case ratio), which is much more complex, and which is not a top-k PSR. Comparing the average ratio of both rules is left for further study.
- 3.
Moreover, there are several ways of defining the Copeland score, all leading to the same rule. However, this has no impact on the negative result below, as long as a Condorcet loser has score 0.
- 4.
As Ranked Pairs is not based on scores, it was not studied here.
References
Ayadi, M., Ben Amor, N., Lang, J., Peters, D.: Single transferable vote: incomplete knowledge and communication issues. In: Proceedings of the 18th International Conference on Autonomous Agents and Multi-Agent Systems, pp. 1288–1296. International Foundation for Autonomous Agents and Multi-agent Systems (2019)
Baumeister, D., Faliszewski, P., Lang, J., Rothe, J.: Campaigns for lazy voters: truncated ballots. In: Proceedings of the 11th International Conference on Autonomous Agents and Multi-agent Systems-Vol. 2, pp. 577–584. International Foundation for Autonomous Agents and Multi-agent Systems (2012)
Bentert, M., Skowron, P.: Comparing election methods where each voter ranks only few candidates. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 02, pp. 2218–2225 (2020). https://doi.org/10.1609/aaai.v34i02.5598
Boutilier, C., Caragiannis, I., Haber, S., Lu, T., Procaccia, A.D., Sheffet, O.: Optimal social choice functions: a utilitarian view. Artif. Intell. 227, 190–213 (2015)
Boutilier, C., Rosenschein, J.S.: Incomplete information and communication in voting. In: Handbook of Computational Social Choice, pp. 223–258 (2016)
Brânzei, S., Caragiannis, I., Morgenstern, J., Procaccia, A.D.: How bad is selfish voting? AAAI. 13, 138–144 (2013)
Caragiannis, I., Kaklamanis, C., Karanikolas, N., Procaccia, A.D.: Socially desirable approximations for Dodgson’s voting rule. ACM Trans. Algorithms (TALG) 10(2), 6 (2014)
Cullinan, J., Hsiao, S.K., Polett, D.: A borda count for partially ordered ballots. Soc. Choice Welf. 42(4), 913–926 (2014)
d’Aspremont, C., Gevers, L.: Chapter 10 social welfare functional and interpersonal comparability. In: Handbook of Social Choice and Welfare, vol. 1, pp. 459–541. Elsevier (2002). https://doi.org/10.1016/S1574-0110(02)80014-5
Dery, L.N., Kalech, M., Rokach, L., Shapira, B.: Reaching a joint decision with minimal elicitation of voter preferences. Inform. Sci. 278, 466–487 (2014). Elsevier
Emerson, P.J.: The Politics of Consensus: For The Resolution of Conflict and Reform of Majority Rule. De Borda Institute, Belfast (1994)
Filmus, Y., Oren, J.: Efficient voting via the top-k elicitation scheme: a probabilistic approach. In: Proceedings of the Fifteenth ACM Conference on Economics and Computation, pp. 295–312. ACM (2014)
Grandi, U., Loreggia, A., Rossi, F., Saraswat, V.: A Borda count for collective sentiment analysis. Ann. Math. Artif. Intell. 77(3–4), 281–302 (2016). https://doi.org/10.1007/s10472-015-9488-0
Kalech, M., Kraus, S., Kaminka, G.A., Goldman, C.V.: Practical voting rules with partial information. Autonom. Agents Multi-Agent Syst. 22, 151–182 (2011). Springer
Lackner, M.: Incomplete preferences in single-peaked electorates. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27–31, 2014, Québec City, Québec, Canada, pp. 742–748 (2014)
Lu, T., Boutilier, C.: Robust approximation and incremental elicitation in voting protocols. Proceedings of IJCAI International Joint Conference on Artificial Intelligence. 22, 287–293 (2011)
Lu, T., Boutilier, C.: Vote elicitation with probabilistic preference models: empirical estimation and cost tradeoffs. In: Brafman, R.I., Roberts, F.S., Tsoukiàs, A. (eds.) ADT 2011. LNCS (LNAI), vol. 6992, pp. 135–149. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24873-3_11
Mallows, C.L.: Non-null ranking models. I. Biometrika, pp. 114–130 (1957)
Mattei, N., Walsh, T.: PrefLib: a library for preferences http://www.preflib.org. In: Perny, P., Pirlot, M., Tsoukiàs, A. (eds.) ADT 2013. LNCS (LNAI), vol. 8176, pp. 259–270. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-41575-3_20
Narodytska, N., Walsh, T.: The computational impact of partial votes on strategic voting. In: ECAI 2014–21st European Conference on Artificial Intelligence, 18–22 August 2014, Prague, Czech Republic - Including Prestigious Applications of Intelligent Systems (PAIS 2014), pp. 657–662 (2014)
Oren, J., Filmus, Y., Boutilier, C.: Efficient vote elicitation under candidate uncertainty. In: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, pp. 309–316. AAAI Press (2013)
Service, T.C., Adams, J.A.: Communication complexity of approximating voting rules. Int. Conf. Autonom. Agents Multi-agent Syst. AAMAS 2012, 593–602 (2012)
Skowron, P., Faliszewski, P., Slinko, A.: Achieving fully proportional representation: approximability results. Artif. Intell. 222, 67–103 (2015)
Young, H.P.: Social choice scoring functions. SIAM J. Appl. Math. 28(4), 824–838 (1975)
Zhao, Z., et al.: A cost-effective framework for preference elicitation and aggregation. In: Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6–10, 2018, pp. 446–456 (2018)
Acknowledgement
This work was supported by Agence Nationale de la Recherche under the “Programme d’Investissements d’Avenir” ANR-19-P3IA-0001 (PRAIRIE).
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Ayadi, M., Amor, N.B., Lang, J. (2020). Approximating Voting Rules from Truncated Ballots. In: Bassiliades, N., Chalkiadakis, G., de Jonge, D. (eds) Multi-Agent Systems and Agreement Technologies. EUMAS AT 2020 2020. Lecture Notes in Computer Science(), vol 12520. Springer, Cham. https://doi.org/10.1007/978-3-030-66412-1_18
Download citation
DOI: https://doi.org/10.1007/978-3-030-66412-1_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-66411-4
Online ISBN: 978-3-030-66412-1
eBook Packages: Computer ScienceComputer Science (R0)