Approximating Nash social welfare by matching and local search

DOI10.1145/3564246.3585255MaRDI QIDQ6499303zbMATH OpenFDO

Authors Jugal Garg, Edin Husić, Wenzheng Li, László A. Végh, Jan Vondrák

Publication date 8 May 2024

Full work available at URL https://doi.org/10.1145/3564246.3585255

zbMATH Keywords

approximation algorithmscombinatorial optimizationenvy-freenessfairnesslocal searchNash social welfare

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Generalized Nash Solution for Two-Person Bargaining Games with Incomplete Information
• A Little Charity Guarantees Almost Envy-Freeness
• Almost envy-freeness with general valuations
• Approximating Nash social welfare under rado valuations
• Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
• 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
• APX-hardness of maximizing Nash social welfare with indivisible items
• Bargaining among groups: an axiomatic viewpoint
• Bargaining in committees as an extension of Nash's bargaining theory
• Earning limits in Fisher markets with spending-constraint utilities
• Extension of Additive Valuations to General Valuations on the Existence of EFX.
• Fair Division of Indivisible Goods for a Class of Concave Valuations
• Handbook of Computational Social Choice
• scientific article; zbMATH DE number 1234106 (Why is no real title available?)
• scientific article; zbMATH DE number 1015852 (Why is no real title available?)
• scientific article; zbMATH DE number 2153479 (Why is no real title available?)
• scientific article; zbMATH DE number 7651150 (Why is no real title available?)
• Maximum Nash welfare and other stories about EFX
• Nash social welfare for indivisible items under separable, piecewise-linear concave utilities
• Nash social welfare, matrix permanent, and stable polynomials
• Nonsymmetric Nash solutions and replications of 2-person bargaining
• The bargaining problem
• The Nash Social Welfare Function
• The Santa Claus problem
• Welfare bounds in the fair division problem

Cited in

(4)

• A note on approximating weighted Nash social welfare with additive valuations
• A note on approximating weighted Nash social welfare with additive valuations
• Approximating Nash social welfare by matching and local search
• Fairness and incentive compatibility via percentage fees

This page was built for publication: Approximating Nash social welfare by matching and local search

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