IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2503.03082.html
   My bibliography  Save this paper

A Linear Theory of Multi-Winner Voting

Author

Listed:
  • Lirong Xia

Abstract

We introduces a general linear framework that unifies the study of multi-winner voting rules and proportionality axioms, demonstrating that many prominent multi-winner voting rules-including Thiele methods, their sequential variants, and approval-based committee scoring rules-are linear. Similarly, key proportionality axioms such as Justified Representation (JR), Extended JR (EJR), and their strengthened variants (PJR+, EJR+), along with core stability, can fit within this linear structure as well. Leveraging PAC learning theory, we establish general and novel upper bounds on the sample complexity of learning linear mappings. Our approach yields near-optimal guarantees for diverse classes of rules, including Thiele methods and ordered weighted average rules, and can be applied to analyze the sample complexity of learning proportionality axioms such as approximate core stability. Furthermore, the linear structure allows us to leverage prior work to extend our analysis beyond worst-case scenarios to study the likelihood of various properties of linear rules and axioms. We introduce a broad class of distributions that extend Impartial Culture for approval preferences, and show that under these distributions, with high probability, any Thiele method is resolute, CORE is non-empty, and any Thiele method satisfies CORE, among other observations on the likelihood of commonly-studied properties in social choice. We believe that this linear theory offers a new perspective and powerful new tools for designing and analyzing multi-winner rules in modern social choice applications.

Suggested Citation

  • Lirong Xia, 2025. "A Linear Theory of Multi-Winner Voting," Papers 2503.03082, arXiv.org.
  • Handle: RePEc:arx:papers:2503.03082
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2503.03082
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Haris Aziz & Markus Brill & Vincent Conitzer & Edith Elkind & Rupert Freeman & Toby Walsh, 2017. "Justified representation in approval-based committee voting," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(2), pages 461-485, February.
    2. Amartya Sen, 1999. "The Possibility of Social Choice," American Economic Review, American Economic Association, vol. 89(3), pages 349-378, June.
    3. Edith Elkind & Piotr Faliszewski & Piotr Skowron & Arkadii Slinko, 2017. "Properties of multiwinner voting rules," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(3), pages 599-632, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Andrea C. Hupman & Jay Simon, 2023. "The Legacy of Peter Fishburn: Foundational Work and Lasting Impact," Decision Analysis, INFORMS, vol. 20(1), pages 1-15, March.
    2. Markus Brill & Jean-François Laslier & Piotr Skowron, 2018. "Multiwinner approval rules as apportionment methods," Journal of Theoretical Politics, , vol. 30(3), pages 358-382, July.
    3. Mostapha Diss & Eric Kamwa & Abdelmonaim Tlidi, 2019. "On some k-scoring rules for committee elections: agreement and Condorcet Principle," Working Papers hal-02147735, HAL.
    4. Mostapha Diss & Eric Kamwa & Abdelmonaim Tlidi, 2018. "The Chamberlin-Courant Rule and the k-Scoring Rules: Agreement and Condorcet Committee Consistency," Working Papers halshs-01817943, HAL.
    5. Davide Grossi, 2021. "Lecture Notes on Voting Theory," Papers 2105.00216, arXiv.org.
    6. Chris Dong & Patrick Lederer, 2023. "Refined Characterizations of Approval-based Committee Scoring Rules," Papers 2312.08799, arXiv.org, revised Mar 2024.
    7. Mostapha Diss & Eric Kamwa & Abdelmonaim Tlidi, 2020. "On Some k -scoring Rules for Committee Elections: Agreement and Condorcet Principle," Revue d'économie politique, Dalloz, vol. 130(5), pages 699-725.
    8. Martin Lackner & Piotr Skowron, 2017. "Consistent Approval-Based Multi-Winner Rules," Papers 1704.02453, arXiv.org, revised Oct 2019.
    9. Skowron, Piotr & Faliszewski, Piotr & Slinko, Arkadii, 2019. "Axiomatic characterization of committee scoring rules," Journal of Economic Theory, Elsevier, vol. 180(C), pages 244-273.
    10. Steven J. Brams & D. Marc Kilgour & Richard F. Potthoff, 2019. "Multiwinner approval voting: an apportionment approach," Public Choice, Springer, vol. 178(1), pages 67-93, January.
    11. Markus Brill & Paul Gölz & Dominik Peters & Ulrike Schmidt-Kraepelin & Kai Wilker, 2022. "Approval-based apportionment," Post-Print hal-03816043, HAL.
    12. Piotr Faliszewski & Piotr Skowron & Arkadii Slinko & Nimrod Talmon, 2018. "Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 51(3), pages 513-550, October.
    13. Niclas Boehmer & Robert Bredereck & Piotr Faliszewski & Andrzej Kaczmarczyk & Rolf Niedermeier, 2020. "Line-Up Elections: Parallel Voting with Shared Candidate Pool," Papers 2007.04960, arXiv.org.
    14. Vincenzo Atella & Jay Coggins & Federico Perali, 2005. "Aversion to inequality in Italy and its determinants," The Journal of Economic Inequality, Springer;Society for the Study of Economic Inequality, vol. 2(2), pages 117-144, January.
    15. Antoinette Baujard & Muriel Gilardone, 2017. "Sen is not a capability theorist," Journal of Economic Methodology, Taylor & Francis Journals, vol. 24(1), pages 1-19, January.
    16. Regenwetter, Michel & Grofman, Bernard & Marley, A. A. J., 2002. "On the model dependence of majority preference relations reconstructed from ballot or survey data," Mathematical Social Sciences, Elsevier, vol. 43(3), pages 451-466, July.
    17. Simplice A. Asongu & Jacinta C. Nwachukwu, 2018. "Increasing Foreign Aid for Inclusive Human Development in Africa," Social Indicators Research: An International and Interdisciplinary Journal for Quality-of-Life Measurement, Springer, vol. 138(2), pages 443-466, July.
    18. repec:diw:diwwpp:dp367 is not listed on IDEAS
    19. Ada Ferrer-i-Carbonell & Bernard Van Praag, 2003. "Income Satisfaction Inequality and its Causes," The Journal of Economic Inequality, Springer;Society for the Study of Economic Inequality, vol. 1(2), pages 107-127, August.
    20. David McCune & Erin Martin & Grant Latina & Kaitlyn Simms, 2023. "A Comparison of Sequential Ranked-Choice Voting and Single Transferable Vote," Papers 2306.17341, arXiv.org.
    21. Haris Aziz & Sujit Gujar & Manisha Padala & Mashbat Suzuki & Jeremy Vollen, 2022. "Coordinating Monetary Contributions in Participatory Budgeting," Papers 2206.05966, arXiv.org, revised Feb 2023.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2503.03082. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.