Approximating Nash social welfare under binary XOS and binary subadditive valuations

DOI10.1007/978-3-030-94676-0_21MaRDI QIDQ2152132zbMATH OpenOpenAlexFDO

Authors Siddharth Barman, Paritosh Verma

Publication date 6 July 2022

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

zbMATH Keywords

Nash social welfarebinary marginalsdiscrete fair division

Mathematics Subject Classification ID

Applications of game theory (91A80) Auctions, bargaining, bidding and selling, and other market models (91B26) Internet topics (68M11)

Recommendations

• Improving Nash social welfare approximations of indivisible goods
• Fair Division of Indivisible Goods for a Class of Concave Valuations
• On maximum weighted Nash welfare for binary valuations
• Approximating the Nash social welfare with budget-additive valuations
• Fair division with binary valuations: one rule to rule them all

Cites work

• scientific article; zbMATH DE number 7651150 (Why is no real title available?)
• APX-hardness of maximizing Nash social welfare with indivisible items
• Algorithmic Game Theory
• An improved approximation algorithm for maximin shares
• Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
• Approximating Nash social welfare under rado valuations
• Approximating the Nash social welfare with budget-additive valuations
• Approximating the Nash social welfare with indivisible items
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Collective choice under dichotomous preferences
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Earning limits in Fisher markets with spending-constraint utilities
• Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity
• Fair allocation of indivisible goods: improvement
• Fair division with binary valuations: one rule to rule them all
• Fair enough: guaranteeing approximate maximin shares
• Finding fair and efficient allocations when valuations don't add up
• Inapproximability results for bounded variants of optimization problems.
• Maximizing Nash product social welfare in allocating indivisible goods
• Multi-unit assignment under dichotomous preferences
• Nash social welfare for indivisible items under separable, piecewise-linear concave utilities
• Nash social welfare, matrix permanent, and stable polynomials
• On maximizing welfare when utility functions are subadditive
• Pairwise kidney exchange
• The bargaining problem
• The fair division of hereditary set systems

Cited in

(6)

• Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem
• Nash welfare guarantees for fair and efficient coverage
• Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
• Weighted fair division with matroid-rank valuations: monotonicity and strategyproofness
• Fair division with binary valuations: one rule to rule them all
• A fair and truthful mechanism with limited subsidy

This page was built for publication: Approximating Nash social welfare under binary XOS and binary subadditive valuations

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