Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Feng, Yuda, Hu, Yang, Li, Shi, Zhang, Ruilong
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computer Science and Game Theory Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps
von: Bei, Xiaohui, et al.
Veröffentlicht: (2025)

A Note on Approximating Weighted Nash Social Welfare with Additive Valuations
von: Feng, Yuda, et al.
Veröffentlicht: (2024)

Approximating Nash Social Welfare by Matching and Local Search
von: Garg, Jugal, et al.
Veröffentlicht: (2022)

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

Online Nash Welfare Maximization Without Predictions
von: Huang, Zhiyi, et al.
Veröffentlicht: (2022)

Welfare Approximation in Additively Separable Hedonic Games
von: Bullinger, Martin, et al.
Veröffentlicht: (2025)

Computing Approximately Proportional Allocations of Indivisible Goods: Beyond Additive and Monotone Valuations
von: Andersen, Martin Jupakkal, et al.
Veröffentlicht: (2025)

Fair Multi-agent Persuasion with Submodular Constraints
von: Bai, Yannan, et al.
Veröffentlicht: (2025)

Cycle Cancellation for Submodular Fractional Allocations and Applications
von: Chekuri, Chandra, et al.
Veröffentlicht: (2025)

Procurement Auctions via Approximately Optimal Submodular Optimization
von: Deng, Yuan, et al.
Veröffentlicht: (2024)

Fair Allocation with Binary Valuations for Mixed Divisible and Indivisible Goods
von: Kawase, Yasushi, et al.
Veröffentlicht: (2023)

Minimum Envy Graphical House Allocation Beyond Identical Valuations
von: Inamdar, Tanmay, et al.
Veröffentlicht: (2026)

Tradeoffs in Privacy, Welfare, and Fairness for Facility Location
von: Fish, Sara, et al.
Veröffentlicht: (2026)

Private Interdependent Valuations: New Bounds for Single-Item Auctions and Matroids
von: Eden, Alon, et al.
Veröffentlicht: (2024)

Optimally Interpolating between Ex-Ante Fairness and Welfare
von: Høgsgaard, Mikael Møller, et al.
Veröffentlicht: (2023)

Approximately Envy-free and Equitable Allocations of Indivisible Items for Non-monotone Valuations
von: Bilò, Vittorio, et al.
Veröffentlicht: (2025)

The Long Arm of Nashian Allocation in Online $p$-Mean Welfare Maximization
von: Huang, Zhiyi, et al.
Veröffentlicht: (2025)

Online Allocation with Multi-Class Arrivals: Group Fairness vs Individual Welfare
von: Zargari, Faraz, et al.
Veröffentlicht: (2025)

A Counterexample to EFX $n \ge 3$ Agents, $m \ge n + 5$ Items, Submodular Valuations via SAT-Solving
von: Akrami, Hannaneh, et al.
Veröffentlicht: (2026)

Covering a Few Submodular Constraints and Applications
von: Bajpai, Tanvi, et al.
Veröffentlicht: (2025)

Weighted Envy Freeness With Bounded Subsidies
von: Elmalem, Noga Klein, et al.
Veröffentlicht: (2024)

Edge-Weighted Online Bipartite Matching
von: Fahrbach, Matthew, et al.
Veröffentlicht: (2020)

Equitable Colorings of Vertex-Weighted Graphs
von: Barman, Siddharth, et al.
Veröffentlicht: (2026)

New Convex Programming Technique for Nash Social Welfare and Scheduling
von: Feng, Yuda, et al.
Veröffentlicht: (2026)

Logarithmic Approximation for Road Pricing on Grids
von: Constantinescu, Andrei, et al.
Veröffentlicht: (2025)

Approximately Bisubmodular Regret Minimization in Billboard and Social Media Advertising
von: Ali, Dildar, et al.
Veröffentlicht: (2025)

The Min Max Average Cycle Weight Problem
von: Elmalem, Noga Klein, et al.
Veröffentlicht: (2025)

Algorithmically Fair Maximization of Multiple Submodular Objective Functions
von: Amanatidis, Georgios, et al.
Veröffentlicht: (2024)

An FPTAS for 7/9-Approximation to Maximin Share Allocations
von: Huang, Xin, et al.
Veröffentlicht: (2025)

Condorcet Winners and Anscombes Paradox Under Weighted Binary Voting
von: Baharav, Carmel, et al.
Veröffentlicht: (2025)

More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules
von: Gupta, Sushmita, et al.
Veröffentlicht: (2025)

Beyond the Half-Approximation: Fair and Efficient Online Class Matching
von: Borst, Sander, et al.
Veröffentlicht: (2026)

Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems
von: Segev, Danny, et al.
Veröffentlicht: (2020)

Computing Power Indices in Weighted Majority Games with Formal Power Series
von: Kakimura, Naonori, et al.
Veröffentlicht: (2025)

Weighted Proportional Allocations of Indivisible Goods and Chores: Insights via Matchings
von: V., Vishwa Prakash H., et al.
Veröffentlicht: (2023)

Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2023)

Smooth Nash Equilibria: Algorithms and Complexity
von: Daskalakis, Constantinos, et al.
Veröffentlicht: (2023)

Polynomial-Time Approximation Schemes via Utility Alignment: Unit-Demand Pricing and More
von: Bowers, Robin, et al.
Veröffentlicht: (2025)

The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations
von: Cesa-Bianchi, Nicolò, et al.
Veröffentlicht: (2023)

The Geometry of Coalition Power: Majorization, Lattices, and Displacement in Multiwinner Elections
von: Guo, Qian, et al.
Veröffentlicht: (2026)