Approximating the Nash Social Welfare with Indivisible Items
From MaRDI portal
Publication:4571931
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
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