NP-Hardness of Approximating Nash Social Welfare with Supermodular Valuations

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Bebchuk, Alon
Format:	Preprint
Published:	2025
Subjects:	Computer Science and Game Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
by: Feng, Yuda, et al.
Published: (2024)

Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps
by: Bei, Xiaohui, et al.
Published: (2025)

A Note on Approximating Weighted Nash Social Welfare with Additive Valuations
by: Feng, Yuda, et al.
Published: (2024)

Compatibility of Fairness and Nash Welfare under Subadditive Valuations
by: Barman, Siddharth, et al.
Published: (2024)

Approximating One-Sided and Two-Sided Nash Social Welfare With Capacities
by: Gokhale, Salil, et al.
Published: (2024)

Approximating Competitive Equilibrium by Nash Welfare
by: Garg, Jugal, et al.
Published: (2024)

Approximating Nash Social Welfare by Matching and Local Search
by: Garg, Jugal, et al.
Published: (2022)

Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability
by: Akrami, Hannaneh, et al.
Published: (2022)

The Fairness of Maximum Nash Social Welfare Under Matroid Constraints and Beyond
by: Wang, Yuanyuan, et al.
Published: (2024)

Maximum Welfare Allocations under Quantile Valuations
by: Aziz, Haris, et al.
Published: (2025)

Platform Equilibrium: Analayzing Social Welfare in Online Market Places
by: Eden, Alon, et al.
Published: (2023)

Linear Contracts for Supermodular Functions Based on Graphs
by: Pashkovich, Kanstantsin, et al.
Published: (2024)

On Optimal Tradeoffs between EFX and Nash Welfare
by: Feldman, Michal, et al.
Published: (2023)

Stable Matching under Matroid Rank Valuations
by: Eden, Alon, et al.
Published: (2025)

Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs
by: Brown, Adam, et al.
Published: (2024)

On the Hardness of Fair Allocation under Ternary Valuations
by: Fitzsimmons, Zack, et al.
Published: (2024)

The Incentive Guarantees Behind Nash Welfare in Divisible Resources Allocation
by: Bei, Xiaohui, et al.
Published: (2023)

Maximizing Nash Social Welfare in 2-Value Instances: A Simpler Proof for the Half-Integer Case
by: Mehlhorn, Kurt
Published: (2024)

Deep Learning Based Auction Design for Selling Agricultural Produce through Farmer Collectives to Maximize Nash Social Welfare
by: Bhardwaj, Mayank Ratan, et al.
Published: (2025)

MMS Approximations Under Additive Leveled Valuations
by: Afshinmehr, Mahyar, et al.
Published: (2024)

Approximability Landscape of Welfare Maximization within Fair Allocations
by: Bu, Xiaolin, et al.
Published: (2022)

Multidimensional Bayesian Utility Maximization: Tight Approximations to Welfare
by: Goldner, Kira, et al.
Published: (2024)

Online Nash Welfare Maximization Without Predictions
by: Huang, Zhiyi, et al.
Published: (2022)

Social Welfare in Budget Aggregation
by: Cembrano, Javier, et al.
Published: (2026)

Approximating N-Player Nash Equilibrium through Gradient Descent
by: Wang, Dongge, et al.
Published: (2025)

Social Welfare in Battery Charging Games
by: Krogmann, Simon, et al.
Published: (2025)

Social Welfare under Heterogeneous Time Preferences
by: Bahmani, Sarvin, et al.
Published: (2026)

On the Interplay between Social Welfare and Tractability of Equilibria
by: Anagnostides, Ioannis, et al.
Published: (2023)

Interdependent Bilateral Trade: Information vs Approximation
by: Dobzinski, Shahar, et al.
Published: (2025)

Social Welfare Maximization for Federated Learning with Network Effects
by: Li, Xiang, et al.
Published: (2024)

Private Interdependent Valuations: New Bounds for Single-Item Auctions and Matroids
by: Eden, Alon, et al.
Published: (2024)

Estimating the Expected Social Welfare and Cost of Random Serial Dictatorship
by: Caragiannis, Ioannis, et al.
Published: (2024)

Hardness of Approximate Hylland-Zeckhauser Equilibria
by: Braverman, Mark, et al.
Published: (2026)

Social Welfare Maximization in Approval-Based Committee Voting under Uncertainty
by: Aziz, Haris, et al.
Published: (2025)

Algorithmic Fairness and Social Welfare
by: Liang, Annie, et al.
Published: (2024)

Learning Social Welfare Functions
by: Pardeshi, Kanad Shrikar, et al.
Published: (2024)

On Approximate Nash Equilibria in Mean Field Games
by: Djete, Mao Fabrice, et al.
Published: (2026)

Existence of EFX for Two Additive Valuations
by: Mahara, Ryoga
Published: (2020)

Reinforcement Nash Equilibrium Solver
by: Wang, Xinrun, et al.
Published: (2024)

Maximizing Social Welfare with Side Payments
by: Geffner, Ivan, et al.
Published: (2025)