On maximum weighted Nash welfare for binary valuations

DOI10.1016/J.MATHSOCSCI.2022.03.004MaRDI QIDQ2673693zbMATH OpenOpenAlexFDO

Authors Warut Suksompong, Nicholas J. Teh

Publication date 13 June 2022

Published in Mathematical Social Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2204.03803

zbMATH Keywords

fair divisionNash welfareunequal entitlements

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

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.

Recommendations

• A characterization of maximum Nash welfare for indivisible goods
• Maximum Nash welfare and other stories about EFX
• Extending the characterization of maximum Nash welfare
• Improving Nash social welfare approximations of indivisible goods
• Maximizing Nash product social welfare in allocating indivisible goods

Cites work

• Almost envy-freeness in group resource allocation
• Approval balloting for multi-winner elections
• Approval voting
• APX-hardness of maximizing Nash social welfare with indivisible items
• Competitive equilibrium with indivisible goods and generic budgets
• Fair Allocation of Indivisible Goods to Asymmetric Agents
• Fair division with binary valuations: one rule to rule them all
• scientific article; zbMATH DE number 1015852 (Why is no real title available?)
• Introduction to algorithms.
• Maximizing Nash product social welfare in allocating indivisible goods
• Maximum Nash welfare and other stories about EFX
• Monotonicity and competitive equilibrium in cake-cutting
• Picking sequences and monotonicity in weighted fair division
• Proportional representation. Apportionment methods and their applications. With a foreword by Andrew Duff
• Resource-monotonicity and population-monotonicity in connected cake-cutting
• Strategy-proofness, solidarity, and consistency for multiple assignment problems

Cited in

(15)

• Picking sequences and monotonicity in weighted fair division
• Approximating Nash social welfare under binary XOS and binary subadditive valuations
• Almost envy-freeness for groups: improved bounds via discrepancy theory
• A characterization of maximum Nash welfare for indivisible goods
• Fair division with binary valuations: one rule to rule them all
• Extending the characterization of maximum Nash welfare
• Fairness in temporal slot assignment
• Keep your distance: land division with separation
• Weighted fair division with matroid-rank valuations: monotonicity and strategyproofness
• Weighted fair division of indivisible items: a review
• Weighted envy-freeness for submodular valuations
• Pure Nash equilibria of weighted picking sequence protocol is WEF1 for two agents
• Asymptotic analysis of weighted fair division
• Fair division with interdependent values
• Fair division with interdependent values

This page was built for publication: On maximum weighted Nash welfare for binary valuations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2673693)