Optimization and Learning in Voting

voting theory, optimization, machine learning

The modern computational approach to social choice theory has greatly expanded our knowledge of the power and limitations of voting rules. Today, a large variety of collective decision making processes with vastly different objectives are treated as voting applications. Beyond the classical setting of political elections, voting rules are used for the allocation of public funds, for rating tasks, and for selecting representative citizen assemblies, to name only a few modern applications.

A common approach is to view voting rules as simple optimization algorithms that seek to aggregate individual preferences in a way that maximizes the collective welfare. We, as computer scientists, may then aim to leverage our insights from the study of approximation algorithms and computational complexity in the context of social choice. However, the voting setting comes with its own set of challenges which arise from an inherent lack of information. The voters may be unable to express their preferences exactly, for example, in numerical terms. Instead, a voter typically only provides a rough sketch of her preferences in the form of a ranking of the alternatives or by reporting those alternatives which she approves of. On the other hand, it may not always be clear to the designer of voting rules which combination of desirable properties the outcomes must satisfy in order to be considered optimal.

A central aspect of our work is to study the benefits that a limited amount of additional information can provide in the design of voting rules. This information could consist of an exact numerical quantification of the utility (or cost) that a voter has for a small subset of the alternatives. We explore whether such enhancements to the capabilities of voting rules can significantly improve their performance (measured in terms of their distortion). In combination with this targeted access to the voters' exact preferences, we also consider stochastic preferences which provide aggregate information to a voting rule such as a voter's average utility for the alternatives.

Another type of information that we consider is data about ideal outcomes of a voting application. How much data in the form of sampled preference profiles labeled by the desired outcomes is necessary and sufficient to learn a voting rule that is consistent with these samples and---hopefully---performs well outside of this training set? In the so-called probably approximately correct (PAC) learning model, we study this notion of sample complexity as well as the computational complexity of a related learning task for certain classes of multiwinner voting rules.

Ben Abramowitz and Elliot Anshelevich. Utilitarians without utilities: Maximizing social welfare for graph problems using only ordinal preferences. In Proceedings of the 32nd AAAI Conference on Artifcial Intelligence (AAAI), pages 894-901, 2018. https://doi.org/10.1609/aaai.v32i1.11453

Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and euclidean k-median by primal-dual algorithms. SIAM Journal on Computing, 49(4), 2020. https://doi.org/10.1137/18M1171321

Noga Alon. Tools from higher algebra. In Handbook of Combinatorics (Vol. 2), pages 1749-1783. MIT Press, 1996.

Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A. Voudouris. Peeking behind the ordinal curtain: Improving distortion via cardinal queries. Artifcial Intelligence, 296:103488, 2021. https://doi.org/10.1016/j.artint.2021.103488

Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A. Voudouris. Don't roll the dice, ask twice: The two-query distortion of matching problems and beyond. In Proceedings of the 36th Annual Conference on Neural Information Processing Systems (NeurIPS), 2022. https://doi.org/10.52202/068431-2223

Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A. Voudouris. A few queries go a long way: Information-distortion tradeoffs in matching. Journal of Artifcial Intelligence Research, 74:227-261, 2022. https://doi.org/10.1613/jair.1.12690

Haris Angelidakis, Konstantin Makarychev, and Yury Makarychev. Algorithms for stable and perturbation-resilient problems. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), pages 438-451, 2017.

Elliot Anshelevich and Wennan Zhu. Tradeoffs between information and ordinal approximation for bipartite matching. In Proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT), pages 267- 279, 2017. https://doi.org/10.1007/978-3-319-66700-3_21

Elliot Anshelevich and Wennan Zhu. Ordinal approximation for social choice, matching, and facility location problems given candidate positions. ACM Transactions on Economics and Computation, 9(2):art. 9, 2021. https://doi.org/10.1145/3434417

Elliot Anshelevich, Onkar Bhardwaj, Edith Elkind, John Postl, and Piotr Skowron. Approximating optimal social choice under metric preferences. Artifcial Intelligence, 264:27-51, 2018. https://doi.org/10.1016/j.artint.2018.07.006

Elliot Anshelevich, Aris Filos-Ratsikas, Nisarg Shah, and Alexandros A. Voudouris. Distortion in social choice problems: The frst 15 years and beyond. In Proceedings of the 30th International Joint Conference on Artifcial Intelligence (IJCAI), pages 4294-4301, 2021. https://doi.org/10.24963/ijcai.2021/589

Elliot Anshelevich, Aris Filos-Ratsikas, and Alexandros A. Voudouris. The distortion of distributed metric social choice. Artifcial Intelligence, 308: 103713, 2022. https://doi.org/10.1016/j.artint.2022.103713

Jose Apesteguia, Miguel A Ballester, and Rosa Ferrer. On the justice of decision rules. The Review of Economic Studies, 78(1):1-16, 2011. https://doi.org/10.1093/restud/rdq023

Kenneth J. Arrow. A diffculty in the concept of social welfare. Journal of Political Economy, 58(4):328-346, 1950. https://doi.org/10.1086/256963

Kenneth J. Arrow. Social Choice and Individual Values. Wiley, 1951.

Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM Journal on Computing, 33(3):544-562, 2004. https://doi.org/10.1137/S0097539702416402

Pranjal Awasthi, Avrim Blum, and Or Sheffet. Stability yields a PTAS for k-median and k-means clustering. In Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 309-318, 2010. https://doi.org/10.1109/FOCS.2010.36

Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, and Toby Walsh. Computational aspects of multi-winner approval voting. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems, page 107-115, 2015. https://doi.org/10.65109/NHTY2001

Dorothea Baumeister and Tobias Hogrebe. How hard is the manipulative design of scoring systems? In Proceedings of the 28th International Joint Conference on Artifcial Intelligence (IJCAI), pages 74-80, 2019. https://doi.org/10.24963/ijcai.2019/11

Gerdus Benadè, Swaprava Nath, Ariel D. Procaccia, and Nisarg Shah. Preference elicitation for participatory budgeting. Management Science, 67(5): 2813-2827, 2021. https://doi.org/10.1287/mnsc.2020.3666

Jeremy Bentham. An introduction to the principles of morals and legislation. Clarendon Press, 1907.

Nadja Betzler, Arkadii Slinko, and Johannes Uhlmann. On the computation of fully proportional representation. Journal of Artifcial Intelligence Research, 47:475-519, 2013.

Niclas Boehmer, Markus Brill, Alfonso Cevallos, Jonas Gehrlein, Luis Sánchez-Fernández, and Ulrike Schmidt-Kraepelin. Approval-based committee voting in practice: A case study of (over-)representation in the polkadot blockchain. In Proceedings of the 38th AAAI Conference on Artifcial Intelligence (AAAI), 9, pages 9519-9527, 2024.

Allan Borodin, Omer Lev, Nisarg Shah, and Tyrone Strangway. Primarily about primaries. In Proceedings of the 33rd AAAI Conference on Artifcial Intelligence (AAAI), pages 1804-1811, 2019. https://doi.org/10.1609/aaai.v33i01.33011804

Craig Boutilier, Ioannis Caragiannis, Simi Haber, Tyler Lu, Ariel D. Procaccia, and Or Sheffet. Optimal social choice functions: A utilitarian view. Artifcial Intelligence, 227:190-213, 2015. https://doi.org/10.1016/j.artint.2015.06.003

Steven J. Brams and Peter C. Fishburn. Going from theory to practice: The mixed success of approval voting. Social Choice and Welfare, 25:457-474, 2005. https://doi.org/10.1007/s00355-005-0013-y

Felix Brandt, Vincent Conitzer, Ulle Endress, Jérôme Lang, and Ariel D. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016. https://doi.org/10.1017/CBO9781107446984.002

Jakob Burkhardt, Ioannis Caragiannis, Karl Fehrs, Matteo Russo, Chris Schwiegelshohn, and Sudarshan Shyam. Low-distortion clustering with ordinal and limited cardinal information. In Proceedings of the 38th AAAI Conference on Artifcial Intelligence (AAAI), 9, pages 9555-9563, 2024. https://doi.org/10.1609/aaai.v38i9.28811

Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Trans. Algorithms, 13(2):23:1-23:31, 2017. https://doi.org/10.1145/2981561

Jaroslaw Byrka, Krzysztof Sornat, and Joachim Spoerhase. Constant-factor approximation for ordered k-median. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), pages 620-631, 2018. https://doi.org/10.1145/3188745.3188930

Ioannis Caragiannis and Karl Fehrs. The complexity of learning approvalbased multiwinner voting rules. In Proceedings of the 36th AAAI Conference on Artifcial Intelligence (AAAI), 5, pages 4925-4932, 2022. https://doi.org/10.1609/aaai.v36i5.20422

Ioannis Caragiannis and Karl Fehrs. Beyond the worst case: Distortion in impartial culture electorates. In Proceedings of the 20th Conference on Web and Internet Economics (WINE), 2024. Forthcoming.

Ioannis Caragiannis and Ariel D. Procaccia. Voting almost maximizes social welfare despite limited communication. Artifcial Intelligence, 175(9-10): 1655-1671, 2011. https://doi.org/10.1016/j.artint.2011.03.005

Ioannis Caragiannis, George A. Krimpas, and Alexandros A. Voudouris. Aggregating partial rankings with applications to peer grading in massive online open courses. In Proceedings of the 14th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 675-683, 2015. https://doi.org/10.65109/BASW6410

Ioannis Caragiannis, Swaprava Nath, Ariel D. Procaccia, and Nisarg Shah. Subset selection via implicit utilitarian voting. Journal of Artifcial Intelligence Research, 58:123-152, 2017. https://doi.org/10.1613/jair.5282

Ioannis Caragiannis, Xenophon Chatzigeorgiou, George A. Krimpas, and Alexandros A. Voudouris. Optimizing positional scoring rules for rank aggregation. Artifcial Intelligence, 267:58-77, 2019. https://doi.org/10.1016/j.artint.2018.11.001

Ioannis Caragiannis, George A. Krimpas, and Alexandros A. Voudouris. How effective can simple ordinal peer grading be? ACM Transactions on Economics and Computation, 8(3), 2020. https://doi.org/10.1145/3412347

Ioannis Caragiannis, Nisarg Shah, and Alexandros A. Voudouris. The metric distortion of multiwinner voting. Artifcial Intelligence, 313:103802, 2022. https://doi.org/10.1016/j.artint.2022.103802

Ioannis Caragiannis, Evi Micha, and Jannik Peters. Can a few decide for many? The metric distortion of sortition. In Proceedings of the 41st International Conference on Machine Learning (ICML), 2025.

Deeparnab Chakrabarty and Chaitanya Swamy. Interpolating between k-median and k-center: Approximation algorithms for ordered k-median. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), pages 29:1-29:14, 2018.

John R. Chamberlin and Paul N. Courant. Representative deliberations and representative decisions: Proportional representation and the Borda rule. American Political Science Review, 77(3):718-733, 1983. https://doi.org/10.2307/1957270

Moses Charikar and Prasanna Ramakrishnan. Metric distortion bounds for randomized social choice. In Proceedings of the 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2986-3004, 2022. https://doi.org/10.1137/1.9781611977073.116

Moses Charikar, Prasanna Ramakrishnan, Kangning Wang, and Hongxun Wu. Breaking the metric voting distortion barrier. Journal of the ACM, 71(6), 2024. https://doi.org/10.1145/3689625

Ning Chen, Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, and Atri Rudra. Approximating matches made in heaven. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), Part I, volume 5555 of Lecture Notes in Computer Science, pages 266-278. Springer, 2009. https://doi.org/10.1007/978-3-642-02927-1_23

Yu Cheng, Shaddin Dughmi, and David Kempe. Of the people: Voting is more effective with representative candidates. In Proceedings of the 2017 ACM Conference on Economics and Computation (EC), pages 305-322, 2017. https://doi.org/10.1145/3033274.3085155

Yu Cheng, Shaddin Dughmi, and David Kempe. On the distortion of voting with multiple representative candidates. Proceedings of the AAAI Conference on Artifcial Intelligence (AAAI), 2018.

Vincent Cohen-Addad and Chris Schwiegelshohn. On the local structure of stable clustering instances. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 49-60, 2017.

Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu. Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics. SIAM Journal on Computing, 48(2):644-667, 2019. https://doi.org/10.1137/17M112717X

Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee. On approximability of clustering problems without candidate centers. In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2635-2648, 2021. https://doi.org/10.1137/1.9781611976465.156

Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic. Nearlinear time approximation schemes for clustering in doubling metrics. Journal of the ACM, 68(6):44:1-44:34, 2021. https://doi.org/10.1145/3477541

Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. Improved coresets and sublinear algorithms for power means in euclidean spaces. In Proceedings of the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 21085-21098, 2021.

Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, and David Saulpic. An improved local search algorithm for k-median. In Proceedings of the 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1556-1612, 2022. https://doi.org/10.1137/1.9781611977073.65

Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, and Chris Schwiegelshohn. Breaching the 2 LMP approximation barrier for facility location with applications to k-median. In Proceedings of the 34th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 940-986, 2023. https://doi.org/10.1137/1.9781611977554.ch37

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. https://doi.org/10.1007/978-3-319-21275-3

Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In Proceedings of The 27th Conference on Learning Theory, volume 35, pages 287-316, 2014.

Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the ERM principle. Journal of Machine Learning Research, 16:2377-2404, 2015.

Soroush Ebadian and Evi Micha. Boosting sortition via proportional representation. In Proceedings of 24th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2025. Forthcoming. https://doi.org/10.65109/QSMK9882

Soroush Ebadian and Nisarg Shah. Every bit helps: Achieving the optimal distortion with a few queries. In Proceedings of the 39th AAAI Conference on Artifcial Intelligence (AAAI), 2025. Forthcoming. https://doi.org/10.1609/aaai.v39i13.33507

Soroush Ebadian, Anson Kahng, Dominik Peters, and Nisarg Shah. Optimized distortion and proportional fairness in voting. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC), pages 563-600, 2022. https://doi.org/10.1145/3490486.3538339

Soroush Ebadian, Gregory Kehne, Evi Micha, Ariel D Procaccia, and Nisarg Shah. Is sortition both representative and fair? In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 3431-3443, 2022. https://doi.org/10.52202/068431-0248

Roy Fairstein, Dan Vilenchik, and Kobi Gal. Learning aggregation rules in participatory budgeting: A data-driven approach, 2024. URL https://arxiv. org/abs/2412.01864.

Piotr Faliszewski and Nimrod Talmon. Between proportionality and diversity: Balancing district sizes under the Chamberlin-Courant rule. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pages 14-22, 2018. https://doi.org/10.65109/VFIX4205

Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. Multiwinner rules on paths from k-Borda to Chamberlin-Courant. In Proceedings of the 26th International Joint Conference on Artifcial Intelligence (IJCAI), pages 192-198, 2017. https://doi.org/10.24963/ijcai.2017/28

Piotr Faliszewski, Piotr Skowron, Arkadii M. Slinko, and Nimrod Talmon. Multiwinner voting: A new challenge for social choice theory. In Ulle Endriss, editor, Trends in Computational Social Choice, pages 27-47. AI Access, 2017.

Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. Committee scoring rules: Axiomatic characterization and hierarchy. ACM Transactions on Economics and Computation, 7(1):3:1-3:39, 2019. https://doi.org/10.1145/3296672

Piotr Faliszewski, Stanislaw Szufa, and Nimrod Talmon. Optimization-Based Voting Rule Design: The Closer to Utopia the Better, pages 17-51. Springer International Publishing, 2022. https://doi.org/10.1007/978-3-030-84997-9_2

Michal Feldman, Amos Fiat, and Iddan Golomb. On voting and facility location. In Proceedings of the 17th ACM Conference on Economics and Computation (EC), pages 269-286, 2016. https://doi.org/10.1145/2940716.2940725

Aris Filos-Ratsikas, Evi Micha, and Alexandros A. Voudouris. The distortion of distributed voting. Artifcial Intelligence, 286:103343, 2020. https://doi.org/10.1016/j.artint.2020.103343

Bailey Flanigan, Paul Gölz, Anupam Gupta, Brett Hennig, and Ariel Procaccia. Fair algorithms for selecting citizens' assemblies. Nature, 596:548-552, 2021. https://doi.org/10.1038/s41586-021-03788-6

Dimitris Fotakis. On the competitive ratio for online facility location. Algorithmica, 50(1):1-57, 2008. https://doi.org/10.1007/s00453-007-9049-y

Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Local search yields a PTAS for k-means in doubling metrics. SIAM Journal on Computing, 48(2):452-480, 2019. https://doi.org/10.1137/17M1127181

Mohammad Ghodsi, Mohamad Latifan, and Masoud Seddighin. On the distortion value of the elections with abstention. In Proceedings of the 33rd AAAI Conference on Artifcial Intelligence (AAAI), pages 1981-1988, 2019. https://doi.org/10.1609/aaai.v33i01.33011981

Allan Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41(4):587-601, 1973. https://doi.org/10.2307/1914083

Vasilis Gkatzelis, Daniel Halpern, and Nisarg Shah. Resolving the optimal metric distortion conjecture. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 1427-1438, 2020. https://doi.org/10.1109/FOCS46700.2020.00134

Ashish Goel, Anilesh Kollagunta Krishnaswamy, and Kamesh Munagala. Metric distortion of social choice rules: Lower bounds and fairness properties. In Proceedings of the 18th ACM Conference on Economics and Computation (EC), pages 287-304, 2017. https://doi.org/10.1145/3033274.3085138

Ashish Goel, Anilesh K. Krishnaswamy, Sukolsak Sakshuwong, and Tanja Aitamurto. Knapsack voting for participatory budgeting. ACM Transactions on Economics and Computation (TEAC), 7(2):1-27, 2019. https://doi.org/10.1145/3340230

Yannai A. Gonczarowski, Gregory Kehne, Ariel D. Procaccia, Ben Schiffer, and Shirley Zhang. The distortion of binomial voting defes expectation. In Proceedings of the 37th International Conference on Neural Information Processing Systems (NeurIPS), 2024. https://doi.org/10.52202/075280-0103

Teoflo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293-306, 1985. https://doi.org/10.1016/0304-3975(85)90224-5

Kishen N. Gowda, Thomas W. Pensyl, Aravind Srinivasan, and Khoa Trinh. Improved bi-point rounding algorithms and a golden barrier for k-median. In Proceedings of the 34th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 987-1011, 2023. https://doi.org/10.1137/1.9781611977554.ch38

Mohak Goyal and Sahasrajit Sarmasarkar. Metric distortion under probabilistic voting, 2025. URL https://arxiv.org/abs/2405.14223.

Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. Journal of Algorithms, 31(1):228-248, 1999. https://doi.org/10.1006/jagm.1998.0993

Kamal Jain and Vijay V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM, 48(2):274-296, 2001. https://doi.org/10.1145/375827.375845

Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC), pages 731-740, 2002. https://doi.org/10.1145/509907.510012

Michał Jaworski and Piotr Skowron. Phragmén rules for degressive and regressive proportionality. In Proceedings of the Thirty-First International Joint Conference on Artifcial Intelligence (IJCAI), pages 328-334, 2022. https://doi.org/10.24963/ijcai.2022/47

Tushant Jha and Yair Zick. A learning framework for distribution-based gametheoretic solution concepts. In Proceedings of the 21st ACM Conference on Economics and Computation (EC), pages 355-377, 2020. https://doi.org/10.1145/3391403.3399509

Haim Kaplan, David Naori, and Danny Raz. Almost tight bounds for online facility location in the random-order model. In Proceedings of the 34th ACMSIAM Symposium on Discrete Algorithms (SODA), pages 1523-1544, 2023. https://doi.org/10.1137/1.9781611977554.ch56

David Kempe. An analysis framework for metric voting based on LP duality. In Proceedings of the 34th AAAI Conference on Artifcial Intelligence (AAAI), pages 2079-2086, 2020.

https://doi.org/10.1609/aaai.v34i02.5581

Fatih Erdem Kizilkaya and David Kempe. Plurality veto: A simple voting rule achieving optimal metric distortion. In Proceedings of the 31st International Joint Conference on Artifcial Intelligence (IJCAI), pages 349-355, 2022. https://doi.org/10.24963/ijcai.2022/50

Nirman Kumar and Benjamin Raichel. Fault tolerant clustering revisited. In Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG), 2013.

Martin Lackner and Piotr Skowron. Approval-based multi-winner rules and strategic voting. In Proceedings of the 27th International Joint Conference on Artifcial Intelligence (IJCAI), pages 340-346, 2018.

Martin Lackner and Piotr Skowron. Utilitarian welfare and representation guarantees of approval-based multiwinner rules. Artifcial Intelligence, 288: 103366, 2020. https://doi.org/10.1016/j.artint.2020.103366

Martin Lackner and Piotr Skowron. Consistent approval-based multi-winner rules. Journal of Economic Theory, 192:105173, 2021. https://doi.org/10.1016/j.jet.2020.105173

Martin Lackner and Piotr Skowron. Multi-Winner Voting with Approval Preferences. SpringerBriefs in Intelligent Systems. Springer International Publishing, 2023.

Jean-Francois Laslier and M. Remzi Sanver, editors. Handbook on Approval Voting. Springer, 2010. https://doi.org/10.1007/978-3-642-02839-7

Mohamad Latifan and Alexandros A. Voudouris. The distortion of threshold approval matching, 2024. https://doi.org/10.1007/s10458-025-09724-6

Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45-58, 2013. https://doi.org/10.1016/j.ic.2012.01.007

Shi Li and Ola Svensson. Approximating k-median via pseudo-approximation. SIAM Journal on Computing, 45(2):530-547, 2016. https://doi.org/10.1137/130938645

Thomas Ma, Vijay Menon, and Kate Larson. Improving welfare in one-sided matchings using simple threshold queries. In Proceedings of the Thirtieth International Joint Conference on Artifcial Intelligence (IJCAI), pages 321- 327, 2021. https://doi.org/10.24963/ijcai.2021/45

Pasin Manurangsi and Warut Suksompong. When do envy-free allocations exist? SIAM Journal on Discrete Mathematics, 34(3):1505-1521, 2020. https://doi.org/10.1137/19M1279125

Samuel Merrill III. A Unifed Theory of Voting: Directional and Proximity Spatial Models. Cambridge University Press, 1999. https://doi.org/10.1017/CBO9780511605864

Adam Meyerson. Online facility location. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 426-431, 2001. https://doi.org/10.1109/SFCS.2001.959917

Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995. https://doi.org/10.1017/CBO9780511814075

Kamesh Munagala and Kangning Wang. Improved metric distortion for deterministic social choice rules. In Proceedings of the 2019 ACM Conference on Economics and Computation (EC), pages 245-262, 2019. https://doi.org/10.1145/3328526.3329550

Roger B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58-73, 1981. https://doi.org/10.1287/moor.6.1.58

Balas K. Natarajan. On learning sets and functions. Machine Language, 4(1): 67-97, 1989. https://doi.org/10.1023/A:1022605311895

Balas K. Natarajan. Machine Learning: A Theoretical Approach. Morgan Kaufmann Publishers Inc., 1991.

Athanasios Papoulis and S. Unnikrishna Pillai. Probability, Random Variables and Stochastic Processes. McGraw-Hill Higher Education, 2002.

Grzegorz Pierczynski and Piotr Skowron. Approval-based elections and distortion of voting rules. In Proceedings of the 28th International Joint Conference on Artifcial Intelligence (IJCAI), pages 543-549, 2019. https://doi.org/10.24963/ijcai.2019/77

Marcus Pivato. Asymptotic utilitarianism in scoring rules. Social Choice & Welfare, 47(2):431-458, 2016. https://doi.org/10.1007/s00355-016-0971-2

Geoffrey Pritchard and Mark C. Wilson. Asymptotics of the minimum manipulating coalition size for positional voting rules under impartial culture behaviour. Mathematical Social Sciences, 58(1):35-57, 2009. https://doi.org/10.1016/j.mathsocsci.2009.02.004

Ariel D. Procaccia and Jeffrey S. Rosenschein. The distortion of cardinal preferences in voting. In Proceedings of the 10th International Workshop on Cooperative Information Agents (CIA), volume 4149 of Lecture Notes in Computer Science, pages 317-331. Springer, 2006. https://doi.org/10.1007/11839354_23

Ariel D. Procaccia, Jeffrey S. Rosenschein, and Aviv Zohar. On the complexity of achieving proportional representation. Social Choice and Welfare, 30:353- 362, April 2008. https://doi.org/10.1007/s00355-007-0235-2

Ariel D. Procaccia, Aviv Zohar, Yoni Peleg, and Jeffrey S. Rosenschein. The learnability of voting rules. Artifcial Intelligence, 173(12):1133-1149, 2009. https://doi.org/10.1016/j.artint.2009.03.003

Haripriya Pulyassary. Algorithm design for ordinal settings. Master's thesis, University of Waterloo, 2022.

Tim Roughgarden, editor. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2020. https://doi.org/10.1017/9781108637435

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. https://doi.org/10.1016/0022-0531(75)90050-2

Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. https://doi.org/10.1017/CBO9781107298019

Piotr Skowron and Piotr Faliszewski. Chamberlin-courant rule with approval ballots: Approximating the maxcover problem with bounded frequencies in FPT time. Journal of Artifcial Intelligence Research, 60(1):687-716, 2017. https://doi.org/10.1613/jair.5628

Chinmay Sonar, Palash Dey, and Neeldhara Misra. On the complexity of winner verifcation and candidate winner for multiwinner voting rules. In Proceedings of the 29th International Joint Conference on Artifcial Intelligence (IJCAI), pages 89-95, 2020.

Thorvald N. Thiele. On multiple choice (in Danish). Bulletin of the Royal Danish Academy of Sciences and Letters, pp. 415-441, 1895.

Panos Toulis and David C. Parkes. Design and analysis of multi-hospital kidney exchange mechanisms using random graphs. Games & Economic Behaviour, 91:360-382, 2015. https://doi.org/10.1016/j.geb.2015.01.001

Ilia Tsetlin, Michel Regenwetter, and Bernard Grofman. The impartial culture maximizes the probability of majority cycles. Social Choice & Welfare, 21(3): 387-398, 2003. https://doi.org/10.1007/s00355-003-0269-z

V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16(2):264-280, 1971. https://doi.org/10.1137/1116025

Hugh E. Warren. Lower bounds for approximation by nonlinear manifolds. Transactions of the American Mathematical Society, 133(1):167-178, 1968. https://doi.org/10.1090/S0002-9947-1968-0226281-1

Lirong Xia. Designing social choice mechanisms using machine learning. In Proceeedings of the 12th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 471-474, 2013. https://doi.org/10.65109/YBLJ9513

Ryo Yoshinaka. Higher-order matching in the linear λ calculus in the absence of constants is np-complete. In Proceedings of the 16th International Conference on Term Rewriting and Applications, pages 235-249, 2005. https://doi.org/10.1007/978-3-540-32033-3_18

Peyton Young. Optimal voting rules. The Journal of Economic Perspectives,9 (1):51-64, 1995. https://doi.org/10.1257/jep.9.1.51

William S. Zwicker. Introduction to the theory of voting. In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, pages 23-56. Cambridge University Press, 2016.