IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2607.10064.html

Fair Division with Binary Valuations: Characterizations

Author

Listed:
  • Florian Brandl
  • Warut Suksompong
  • Nicholas Teh

Abstract

We consider the fair allocation of indivisible goods with binary valuations. In this setting, the maximum Nash welfare rule, the leximin rule, and all additive welfarist rules with a strictly concave function coincide. We show that for any number of agents, this rule is the only rule that satisfies envy-freeness up to one good, strategyproofness, neutrality, minimal completeness, and invariance under disapproving unassigned goods (IDU). Moreover, we present an alternative characterization for two agents, where we replace IDU with non-redundancy and resource-monotonicity. In both characterizations, all axioms are necessary.

Suggested Citation

  • Florian Brandl & Warut Suksompong & Nicholas Teh, 2026. "Fair Division with Binary Valuations: Characterizations," Papers 2607.10064, arXiv.org.
    • Handle: RePEc:arx:papers:2607.10064
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Siddharth Barman & Sanath Kumar Krishnamurthy & Rohit Vaish, 2018. "Greedy Algorithms for Maximizing Nash Social Welfare," Papers 1801.09046, arXiv.org.
    2. Mithun Chakraborty & Ulrike Schmidt-Kraepelin & Warut Suksompong, 2021. "Picking Sequences and Monotonicity in Weighted Fair Division," Papers 2104.14347, arXiv.org, revised Aug 2021.
    3. Warut Suksompong & Nicholas Teh, 2022. "On Maximum Weighted Nash Welfare for Binary Valuations," Papers 2204.03803, arXiv.org, revised Apr 2022.
    4. Suksompong, Warut, 2023. "A characterization of maximum Nash welfare for indivisible goods," Economics Letters, Elsevier, vol. 222(C).
    5. 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.
    6. Eric Budish, 2011. "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes," Journal of Political Economy, University of Chicago Press, vol. 119(6), pages 1061-1103.
    7. Warut Suksompong & Nicholas Teh, 2023. "Weighted Fair Division with Matroid-Rank Valuations: Monotonicity and Strategyproofness," Papers 2303.14454, arXiv.org, revised Sep 2023.
    8. Suksompong, Warut & Teh, Nicholas, 2022. "On maximum weighted Nash welfare for binary valuations," Mathematical Social Sciences, Elsevier, vol. 117(C), pages 101-108.
    9. Anna Bogomolnaia & Herve Moulin, 2004. "Random Matching Under Dichotomous Preferences," Econometrica, Econometric Society, vol. 72(1), pages 257-279, January.
    10. Sheung Man Yuen & Warut Suksompong, 2023. "Extending the Characterization of Maximum Nash Welfare," Papers 2301.03798, arXiv.org, revised Feb 2023.
    11. Luisa Montanari & Ulrike Schmidt-Kraepelin & Warut Suksompong & Nicholas Teh, 2025. "Weighted envy-freeness for submodular valuations," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 65(4), pages 983-1016, December.
    12. Malik, Komal & Mishra, Debasis, 2021. "Pareto efficient combinatorial auctions: Dichotomous preferences without quasilinearity," Journal of Economic Theory, Elsevier, vol. 191(C).
    13. Yuen, Sheung Man & Suksompong, Warut, 2023. "Extending the characterization of maximum Nash welfare," Economics Letters, Elsevier, vol. 224(C).
    14. 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.
    15. Goko, Hiromichi & Igarashi, Ayumi & Kawase, Yasushi & Makino, Kazuhisa & Sumita, Hanna & Tamura, Akihisa & Yokoi, Yu & Yokoo, Makoto, 2024. "A fair and truthful mechanism with limited subsidy," Games and Economic Behavior, Elsevier, vol. 144(C), pages 49-70.
    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. Luisa Montanari & Ulrike Schmidt-Kraepelin & Warut Suksompong & Nicholas Teh, 2025. "Weighted envy-freeness for submodular valuations," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 65(4), pages 983-1016, December.
    2. 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.
    3. Warut Suksompong & Nicholas Teh, 2023. "Weighted Fair Division with Matroid-Rank Valuations: Monotonicity and Strategyproofness," Papers 2303.14454, arXiv.org, revised Sep 2023.
    4. Tzeh Yuan Neoh & Nicholas Teh, 2025. "Understanding EFX Allocations: Counting and Variants," Papers 2504.03951, arXiv.org.
    5. Xiaohui Bei & Xinhang Lu & Warut Suksompong, 2025. "Truthful cake sharing," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 64(1), pages 309-343, February.
    6. Karen Frilya Celine & Warut Suksompong & Sheung Man Yuen, 2024. "On the Fairness of Additive Welfarist Rules," Papers 2412.15472, arXiv.org, revised Mar 2026.
    7. Felix Brandt & Matthias Greger & Erel Segal-Halevi & Warut Suksompong, 2023. "Coordinating Charitable Donations with Leontief Preferences," Papers 2305.10286, arXiv.org, revised Oct 2025.
    8. Moshe Babaioff & Tomer Ezra & Uriel Feige, 2024. "Fair-Share Allocations for Agents with Arbitrary Entitlements," Mathematics of Operations Research, INFORMS, vol. 49(4), pages 2180-2211, November.
    9. 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.
    10. D. Marc Kilgour & Rudolf Vetschera, 2024. "Two-Person Fair Division with Additive Valuations," Group Decision and Negotiation, Springer, vol. 33(4), pages 745-774, August.
    11. Warut Suksompong & Nicholas Teh, 2022. "On Maximum Weighted Nash Welfare for Binary Valuations," Papers 2204.03803, arXiv.org, revised Apr 2022.
    12. Igarashi, Ayumi & Kawase, Yasushi & Suksompong, Warut & Sumita, Hanna, 2024. "Fair division with two-sided preferences," Games and Economic Behavior, Elsevier, vol. 147(C), pages 268-287.
    13. Eugene Lim & Tzeh Yuan Neoh & Nicholas Teh, 2025. "Fairness in Repeated Matching: A Maximin Perspective," Papers 2510.04624, arXiv.org.
    14. Hannaneh Akrami & Bhaskar Ray Chaudhury & Martin Hoefer & Kurt Mehlhorn & Marco Schmalhofer & Golnoosh Shahkarami & Giovanna Varricchio & Quentin Vermande & Ernest van Wijland, 2026. "Maximizing Nash Social Welfare in Two-Value Instances: Delineating Tractability," Mathematics of Operations Research, INFORMS, vol. 51(2), pages 853-876, May.
    15. Mithun Chakraborty & Erel Segal-Halevi & Warut Suksompong, 2021. "Weighted Fairness Notions for Indivisible Items Revisited," Papers 2112.04166, arXiv.org, revised Jun 2024.
    16. Ortega, Josué, 2020. "Multi-unit assignment under dichotomous preferences," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 15-24.
    17. Brandl, Florian & Peters, Dominik, 2022. "Approval voting under dichotomous preferences: A catalogue of characterizations," Journal of Economic Theory, Elsevier, vol. 205(C).
    18. Jugal Garg & Thorben Trobst & Vijay V. Vazirani, 2020. "One-Sided Matching Markets with Endowments: Equilibria and Algorithms," Papers 2009.10320, arXiv.org, revised Jul 2021.
    19. Pasin Manurangsi & Warut Suksompong, 2020. "Closing Gaps in Asymptotic Fair Division," Papers 2004.05563, arXiv.org.
    20. Nishimura, Koichi & Sumita, Hanna, 2025. "Envy-freeness and maximum Nash welfare for mixed divisible and indivisible goods," Mathematical Social Sciences, Elsevier, vol. 138(C).

    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:2607.10064. 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: https://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.