Nash Social Welfare, Matrix Permanent, and Stable Polynomials

DOI10.4230/LIPIcs.ITCS.2017.36zbMath1402.91126arXiv1609.07056OpenAlexW2962836029MaRDI QIDQ4638089

Amin Saberi, Nima Anari, Unnamed Author, Mohit Singh

Publication date: 3 May 2018

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

zbMATH Keywords

matchingrandomized algorithmsaddle pointpermanentstable polynomialNash welfare

Mathematics Subject Classification ID

Convex programming (90C25) Determinants, permanents, traces, other special matrix functions (15A15) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Randomized algorithms (68W20) Welfare economics (91B15)

Related Items

Approximating the Nash Social Welfare with Indivisible Items ⋮ Approximating Nash social welfare under binary XOS and binary subadditive valuations ⋮ APX-hardness of maximizing Nash social welfare with indivisible items ⋮ Existence of EFX for two additive valuations ⋮ Unnamed Item ⋮ A generalization of permanent inequalities and applications in counting and optimization ⋮ A Little Charity Guarantees Almost Envy-Freeness ⋮ On fair division for indivisible items ⋮ A Tight Analysis of Bethe Approximation for Permanent ⋮ Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings ⋮ Nash Social Welfare Approximation for Strategic Agents

Cites Work

• Unnamed Item
• Unnamed Item
• Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods
• Welfare bounds in the fair division problem
• APX-hardness of maximizing Nash social welfare with indivisible items
• The Santa Claus problem
• Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures
• Approximating the Nash Social Welfare with Indivisible Items
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Santa Claus Meets Hypergraph Matchings
• Lower Bounds for Partial Matchings in Regular Bipartite Graphs and Applications to the Monomer–Dimer Entropy
• Hyperbolic Polynomials and Interior Point Methods for Convex Programming
• On Allocating Goods to Maximize Fairness
• Maximizing determinants under partition constraints