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

On Maximum Weighted Nash Welfare for Binary Valuations

Author

Listed:
  • Warut Suksompong
  • Nicholas Teh

Abstract

We consider the problem of fairly allocating indivisible goods to agents with weights representing their entitlements. A natural rule in this setting is the maximum weighted Nash welfare (MWNW) rule, which selects an allocation maximizing the weighted product of the agents' utilities. We show that when agents have binary valuations, a specific version of MWNW is resource- and population-monotone, satisfies group-strategyproofness, and can be implemented in polynomial time.

Suggested Citation

  • Warut Suksompong & Nicholas Teh, 2022. "On Maximum Weighted Nash Welfare for Binary Valuations," Papers 2204.03803, arXiv.org, revised Apr 2022.
    • Handle: RePEc:arx:papers:2204.03803
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Moshe Babaioff & Noam Nisan & Inbal Talgam-Cohen, 2021. "Competitive Equilibrium with Indivisible Goods and Generic Budgets," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 382-403, February.
    2. Erel Segal-Halevi & Balázs R. Sziklai, 2019. "Monotonicity and competitive equilibrium in cake-cutting," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 68(2), pages 363-401, September.
    3. D. Marc Kilgour, 2010. "Approval Balloting for Multi-winner Elections," Studies in Choice and Welfare, in: Jean-François Laslier & M. Remzi Sanver (ed.), Handbook on Approval Voting, chapter 0, pages 105-124, Springer.
    4. Mithun Chakraborty & Ayumi Igarashi & Warut Suksompong & Yair Zick, 2019. "Weighted Envy-Freeness in Indivisible Item Allocation," Papers 1909.10502, arXiv.org, revised Mar 2021.
    5. Siddharth Barman & Sanath Kumar Krishnamurthy & Rohit Vaish, 2018. "Greedy Algorithms for Maximizing Nash Social Welfare," Papers 1801.09046, arXiv.org.
    6. Mithun Chakraborty & Ulrike Schmidt-Kraepelin & Warut Suksompong, 2021. "Picking Sequences and Monotonicity in Weighted Fair Division," Papers 2104.14347, arXiv.org, revised Aug 2021.
    7. Bettina Klaus & Eiichi Miyagawa, 2002. "Strategy-proofness, solidarity, and consistency for multiple assignment problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 30(3), pages 421-435.
    8. Jean-François Laslier & M. Remzi Sanver (ed.), 2010. "Handbook on Approval Voting," Studies in Choice and Welfare, Springer, number 978-3-642-02839-7, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Jonathan Scarlett & Nicholas Teh & Yair Zick, 2023. "For One and All: Individual and Group Fairness in the Allocation of Indivisible Goods," Papers 2302.06958, arXiv.org.
    2. Warut Suksompong & Nicholas Teh, 2023. "Weighted Fair Division with Matroid-Rank Valuations: Monotonicity and Strategyproofness," Papers 2303.14454, arXiv.org, revised Sep 2023.

    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. Warut Suksompong & Nicholas Teh, 2023. "Weighted Fair Division with Matroid-Rank Valuations: Monotonicity and Strategyproofness," Papers 2303.14454, arXiv.org, revised Sep 2023.
    2. Jean-François Laslier & Karine Straeten, 2016. "Strategic voting in multi-winner elections with approval balloting: a theory for large electorates," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(3), pages 559-587, October.
    3. 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.
    4. Mithun Chakraborty & Erel Segal-Halevi & Warut Suksompong, 2021. "Weighted Fairness Notions for Indivisible Items Revisited," Papers 2112.04166, arXiv.org.
    5. 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.
    6. Jean-François Laslier & Karine van Der Straeten, 2015. "Strategic Voting under Committee Approval: A Theory," Working Papers halshs-01168767, HAL.
    7. Duddy, Conal, 2014. "Electing a representative committee by approval ballot: An impossibility result," Economics Letters, Elsevier, vol. 124(1), pages 14-16.
    8. Gilbert Laffond & Jean Lainé, 2012. "Searching for a Compromise in Multiple Referendum," Group Decision and Negotiation, Springer, vol. 21(4), pages 551-569, July.
    9. Carlos Alós-Ferrer & Ðura-Georg Granić, 2012. "Two field experiments on Approval Voting in Germany," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 39(1), pages 171-205, June.
    10. Martin Lackner & Piotr Skowron, 2017. "Consistent Approval-Based Multi-Winner Rules," Papers 1704.02453, arXiv.org, revised Oct 2019.
    11. Mostapha Diss & Ahmed Doghmi, 2016. "Multi-winner scoring election methods: Condorcet consistency and paradoxes," Public Choice, Springer, vol. 169(1), pages 97-116, October.
    12. Subiza, Begoña & Peris, Josep E., 2014. "A Consensual Committee Using Approval Balloting," QM&ET Working Papers 14-5, University of Alicante, D. Quantitative Methods and Economic Theory.
    13. 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.
    14. Begoña Subiza & Josep E. Peris, 2017. "A Representative Committee by Approval Balloting," Group Decision and Negotiation, Springer, vol. 26(5), pages 1029-1040, September.
    15. Pietro Speroni di Fenizio & Daniele A. Gewurz, 2019. "The space of all proportional voting systems and the most majoritarian among them," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 52(4), pages 663-683, April.
    16. 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.
    17. Kilgour, D. Marc, 2018. "Multi-Winner Voting/Votación con múltiples ganadores," Estudios de Economia Aplicada, Estudios de Economia Aplicada, vol. 36, pages 167-180, Enero.
    18. Martin Lackner & Jan Maly, 2020. "Approval-Based Shortlisting," Papers 2005.07094, arXiv.org, revised May 2022.
    19. Michel Balinski & Rida Laraki, 2022. "Majority Judgment vs. Approval Voting," Operations Research, INFORMS, vol. 70(3), pages 1296-1316, May.
    20. Erlanson, Albin & Szwagrzak, Karol, 2013. "Strategy-Proof Package Assignment," Working Papers 2013:43, Lund University, Department of Economics.

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