Approximating the Nash Social Welfare with Indivisible Items

DOI10.1137/15M1053682zbMath1397.91302OpenAlexW2811122596MaRDI QIDQ4571931

Vasilis Gkatzelis, Richard John Cole

Publication date: 4 July 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1053682

zbMATH Keywords

fair divisionapproximation algorithmsNash social welfarecompetitive equilibrium from equal incomes

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items (13)

THE MAGIC OF NASH SOCIAL WELFARE IN OPTIMIZATION: DO NOT SUM, JUST MULTIPLY! ⋮ Features Selection as a Nash-Bargaining Solution: Applications in Online Advertising and Information Systems ⋮ Maximum Nash welfare and other stories about EFX ⋮ On the existence of EFX allocations ⋮ Fair Division of Indivisible Goods for a Class of Concave Valuations ⋮ Existence of EFX for two additive valuations ⋮ Fair division of indivisible goods: recent progress and open questions ⋮ A Little Charity Guarantees Almost Envy-Freeness ⋮ Competitive Equilibrium with Indivisible Goods and Generic Budgets ⋮ Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings ⋮ Core Pricing in Combinatorial Exchanges with Financially Constrained Buyers: Computational Hardness and Algorithmic Solutions ⋮ Computing Large Market Equilibria Using Abstractions ⋮ Nash Social Welfare Approximation for Strategic Agents

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximizing Nash product social welfare in allocating indivisible goods
• Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods
• Compactly representing utility functions using weighted goals and the Max aggregator
• APX-hardness of maximizing Nash social welfare with indivisible items
• A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation
• Improved algorithms for computing fisher's market clearing prices
• The Santa Claus problem
• Approximating the Nash Social Welfare with Indivisible Items
• The Bargaining Problem
• Santa claus meets hypergraph matchings
• Consensus of Subjective Probabilities: The Pari-Mutuel Method
• Approximation Algorithms for Computing Maximin Share Allocations
• Market equilibrium via a primal--dual algorithm for a convex program
• The Nash Social Welfare Function
• The Impossibility of Bayesian Group Decision Making with Separate Aggregation of Beliefs and Values
• Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities
• Nash Social Welfare, Matrix Permanent, and Stable Polynomials
• On Allocating Goods to Maximize Fairness
• MaxMin allocation via degree lower-bounded arborescences
• Combinatorial Algorithm for Restricted Max-Min Fair Allocation
• An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods
• Algorithmic Game Theory

This page was built for publication: Approximating the Nash Social Welfare with Indivisible Items