IDEAS home Printed from https://ideas.repec.org/a/eee/matsoc/v126y2023icp48-59.html
   My bibliography  Save this article

Weighted fair division with matroid-rank valuations: Monotonicity and strategyproofness

Author

Listed:
  • Suksompong, Warut
  • Teh, Nicholas

Abstract

We study the problem of fairly allocating indivisible goods to agents with weights corresponding to their entitlements. Previous work has shown that, when agents have binary additive valuations, the maximum weighted Nash welfare rule is resource-, population-, and weight-monotone, satisfies group-strategyproofness, and can be implemented in polynomial time. We generalize these results to the class of weighted additive welfarist rules with concave functions and agents with matroid-rank (also known as binary submodular) valuations.

Suggested Citation

  • Suksompong, Warut & Teh, Nicholas, 2023. "Weighted fair division with matroid-rank valuations: Monotonicity and strategyproofness," Mathematical Social Sciences, Elsevier, vol. 126(C), pages 48-59.
    • Handle: RePEc:eee:matsoc:v:126:y:2023:i:c:p:48-59
    DOI: 10.1016/j.mathsocsci.2023.09.004
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0165489623000793
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.mathsocsci.2023.09.004?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Haris Aziz & Xinhang Lu & Mashbat Suzuki & Jeremy Vollen & Toby Walsh, 2023. "Best-of-Both-Worlds Fairness in Committee Voting," Papers 2303.03642, arXiv.org, revised Dec 2023.
    2. Camacho, Franklin & Fonseca-Delgado, Rigoberto & Pino Pérez, Ramón & Tapia, Guido, 2023. "Generalized binary utility functions and fair allocations," Mathematical Social Sciences, Elsevier, vol. 121(C), pages 50-60.
    3. Mithun Chakraborty & Ayumi Igarashi & Warut Suksompong & Yair Zick, 2019. "Weighted Envy-Freeness in Indivisible Item Allocation," Papers 1909.10502, arXiv.org, revised Mar 2021.
    4. Sheung Man Yuen & Warut Suksompong, 2023. "Extending the Characterization of Maximum Nash Welfare," Papers 2301.03798, arXiv.org, revised Feb 2023.
    5. Suksompong, Warut, 2023. "A characterization of maximum Nash welfare for indivisible goods," Economics Letters, Elsevier, vol. 222(C).
    6. 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.
    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. Luisa Montanari & Ulrike Schmidt-Kraepelin & Warut Suksompong & Nicholas Teh, 2022. "Weighted Envy-Freeness for Submodular Valuations," Papers 2209.06437, arXiv.org.
    9. Mithun Chakraborty & Ulrike Schmidt-Kraepelin & Warut Suksompong, 2021. "Picking Sequences and Monotonicity in Weighted Fair Division," Papers 2104.14347, arXiv.org, revised Aug 2021.
    10. Warut Suksompong & Nicholas Teh, 2022. "On Maximum Weighted Nash Welfare for Binary Valuations," Papers 2204.03803, arXiv.org, revised Apr 2022.
    11. Yuen, Sheung Man & Suksompong, Warut, 2023. "Extending the characterization of maximum Nash welfare," Economics Letters, Elsevier, vol. 224(C).
    12. 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.
    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. Warut Suksompong & Nicholas Teh, 2023. "Weighted Fair Division with Matroid-Rank Valuations: Monotonicity and Strategyproofness," Papers 2303.14454, arXiv.org, revised Sep 2023.
    2. Warut Suksompong & Nicholas Teh, 2022. "On Maximum Weighted Nash Welfare for Binary Valuations," Papers 2204.03803, arXiv.org, revised Apr 2022.
    3. Felix Brandt & Matthias Greger & Erel Segal-Halevi & Warut Suksompong, 2023. "Coordinating Charitable Donations," Papers 2305.10286, arXiv.org, revised Sep 2024.
    4. 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.
    5. Yuen, Sheung Man & Suksompong, Warut, 2023. "Extending the characterization of maximum Nash welfare," Economics Letters, Elsevier, vol. 224(C).
    6. Mithun Chakraborty & Erel Segal-Halevi & Warut Suksompong, 2021. "Weighted Fairness Notions for Indivisible Items Revisited," Papers 2112.04166, arXiv.org, revised Jun 2024.
    7. Erlanson, Albin & Szwagrzak, Karol, 2013. "Strategy-Proof Package Assignment," Working Papers 2013:43, Lund University, Department of Economics.
    8. 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.
    9. Marek Pycia & M. Utku Ünver, 2021. "Arrovian Efficiency and Auditability in Discrete Mechanism Design," Boston College Working Papers in Economics 1044, Boston College Department of Economics.
    10. Yuji Fujinaka & Takuma Wakayama, 2011. "Secure implementation in Shapley–Scarf housing markets," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 48(1), pages 147-169, September.
    11. Miralles, Antonio & Pycia, Marek, 2021. "Foundations of pseudomarkets: Walrasian equilibria for discrete resources," Journal of Economic Theory, Elsevier, vol. 196(C).
    12. Papai, Szilvia, 2007. "Exchange in a general market with indivisible goods," Journal of Economic Theory, Elsevier, vol. 132(1), pages 208-235, January.
    13. Bettina Klaus & Alexandru Nichifor, 2020. "Serial dictatorship mechanisms with reservation prices," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(3), pages 665-684, October.
    14. Pycia, Marek & Ãœnver, M. Utku, 2020. "Arrovian Efficiency and Auditability in the Allocation of Discrete Resources," CEPR Discussion Papers 15377, C.E.P.R. Discussion Papers.
    15. Di Feng & Jacob Coreno, 2024. "Justified Fairness in House Allocation Problems: two Characterizations of Strategy-proof Mechanisms," Papers 2407.14101, arXiv.org.
    16. Papai, Szilvia, 2003. "Strategyproof exchange of indivisible goods," Journal of Mathematical Economics, Elsevier, vol. 39(8), pages 931-959, November.
    17. Gian Caspari, 2023. "A market design solution to a multi-category housing allocation problem," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 8(1), pages 75-96, December.
    18. Salvador Barberà, 2010. "Strategy-proof social choice," UFAE and IAE Working Papers 828.10, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
    19. Onur Kesten & Ayşe Yazıcı, 2012. "The Pareto-dominant strategy-proof and fair rule for problems with indivisible goods," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 50(2), pages 463-488, June.
    20. Eric Budish & Estelle Cantillon, 2012. "The Multi-unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard," American Economic Review, American Economic Association, vol. 102(5), pages 2237-2271, August.

    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:eee:matsoc:v:126:y:2023:i:c:p:48-59. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/505565 .

    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.