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

Approximate Core for Committee Selection via Multilinear Extension and Market Clearing

Author

Listed:
  • Kamesh Munagala
  • Yiheng Shen
  • Kangning Wang
  • Zhiyi Wang

Abstract

Motivated by civic problems such as participatory budgeting and multiwinner elections, we consider the problem of public good allocation: Given a set of indivisible projects (or candidates) of different sizes, and voters with different monotone utility functions over subsets of these candidates, the goal is to choose a budget-constrained subset of these candidates (or a committee) that provides fair utility to the voters. The notion of fairness we adopt is that of core stability from cooperative game theory: No subset of voters should be able to choose another blocking committee of proportionally smaller size that provides strictly larger utility to all voters that deviate. The core provides a strong notion of fairness, subsuming other notions that have been widely studied in computational social choice. It is well-known that an exact core need not exist even when utility functions of the voters are additive across candidates. We therefore relax the problem to allow approximation: Voters can only deviate to the blocking committee if after they choose any extra candidate (called an additament), their utility still increases by an $\alpha$ factor. If no blocking committee exists under this definition, we call this an $\alpha$-core. Our main result is that an $\alpha$-core, for $\alpha 1.015$ for submodular utilities, and a lower bound of any function in the number of voters and candidates for general monotone utilities.

Suggested Citation

  • Kamesh Munagala & Yiheng Shen & Kangning Wang & Zhiyi Wang, 2021. "Approximate Core for Committee Selection via Multilinear Extension and Market Clearing," Papers 2110.12499, arXiv.org.
  • Handle: RePEc:arx:papers:2110.12499
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. William C. Brainard & Herbert E. Scarf, 2005. "How to Compute Equilibrium Prices in 1891," American Journal of Economics and Sociology, Wiley Blackwell, vol. 64(1), pages 57-83, January.
    2. Monroe, Burt L., 1995. "Fully Proportional Representation," American Political Science Review, Cambridge University Press, vol. 89(4), pages 925-940, December.
    3. 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.
    4. Nash, John, 1950. "The Bargaining Problem," Econometrica, Econometric Society, vol. 18(2), pages 155-162, April.
    5. Steven Brams & D. Kilgour & M. Sanver, 2007. "A minimax procedure for electing committees," Public Choice, Springer, vol. 132(3), pages 401-420, September.
    6. Foley, Duncan K, 1970. "Lindahl's Solution and the Core of an Economy with Public Goods," Econometrica, Econometric Society, vol. 38(1), pages 66-72, January.
    7. Chamberlin, John R. & Courant, Paul N., 1983. "Representative Deliberations and Representative Decisions: Proportional Representation and the Borda Rule," American Political Science Review, Cambridge University Press, vol. 77(3), pages 718-733, September.
    8. Nicolaus Tideman & Daniel Richardson, 2000. "Better Voting Methods Through Technology: The Refinement-Manageability Trade-Off in the Single Transferable Vote," Public Choice, Springer, vol. 103(1), pages 13-34, April.
    9. Tideman, Nicolaus & Richardson, Daniel, 2000. "Better Voting Methods through Technology: The Refinement-Manageabililty Trade-Off in the Single Transferable Vote," Public Choice, Springer, vol. 103(1-2), pages 13-34, April.
    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. 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.
    2. 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.
    3. 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.
    4. Haris Aziz & Barton E. Lee, 2020. "The expanding approvals rule: improving proportional representation and monotonicity," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(1), pages 1-45, January.
    5. Eric Kamwa, 2022. "The Condorcet Loser Criterion in Committee Selection," Working Papers hal-03880064, HAL.
    6. 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.
    7. Nikhil Garg & Ashish Goel & Benjamin Plaut, 2021. "Markets for public decision-making," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 56(4), pages 755-801, May.
    8. Egor Ianovski, 2022. "Electing a committee with dominance constraints," Annals of Operations Research, Springer, vol. 318(2), pages 985-1000, November.
    9. 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.
    10. Ashish Goel & Reyna Hulett & Benjamin Plaut, 2018. "Markets Beyond Nash Welfare for Leontief Utilities," Papers 1807.05293, arXiv.org, revised Dec 2019.
    11. Martin Lackner & Piotr Skowron, 2017. "Consistent Approval-Based Multi-Winner Rules," Papers 1704.02453, arXiv.org, revised Oct 2019.
    12. Skowron, Piotr & Faliszewski, Piotr & Slinko, Arkadii, 2019. "Axiomatic characterization of committee scoring rules," Journal of Economic Theory, Elsevier, vol. 180(C), pages 244-273.
    13. Klamler, Christian & Pferschy, Ulrich & Ruzika, Stefan, 2012. "Committee selection under weight constraints," Mathematical Social Sciences, Elsevier, vol. 64(1), pages 48-56.
    14. 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.
    15. Dominik Peters & Grzegorz Pierczy'nski & Piotr Skowron, 2020. "Proportional Participatory Budgeting with Additive Utilities," Papers 2008.13276, arXiv.org, revised Oct 2022.
    16. Mostapha Diss & Eric Kamwa & Abdelmonaim Tlidi, 2019. "On some k-scoring rules for committee elections: agreement and Condorcet Principle," Working Papers hal-02147735, HAL.
    17. 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.
    18. Nicolaus Tideman, 2015. "Multiple-winner voting rules," Chapters, in: Jac C. Heckelman & Nicholas R. Miller (ed.), Handbook of Social Choice and Voting, chapter 17, pages 303-324, Edward Elgar Publishing.
    19. Duddy, Conal, 2014. "Electing a representative committee by approval ballot: An impossibility result," Economics Letters, Elsevier, vol. 124(1), pages 14-16.
    20. Kamwa, Eric, 2017. "On stable rules for selecting committees," Journal of Mathematical Economics, Elsevier, vol. 70(C), pages 36-44.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:2110.12499. 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.