Research map / Multi-agent systems and games / Games and equilibria
Approximations for Indivisible Concave Allocations with Applications to Nash Welfare Maximization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use local multiplicative curvature to guide item reassignment and stopping | ICA · ICA instances | approximation ratio: (1 + ϵ) maxi µi | Helped |
| Use local additive curvature to guide item reassignment and stopping | ICA · ICA instances | additive approximation: P i αi + ϵ | Helped |
| Use uniform agent bids and weighted bang-per-buck item assignment | Asymmetric Nash Welfare with smooth additive valuations · Smooth Asymmetric Nash Welfare | approximation ratio: O(eϵ/(ω ln(1 + 1/ω))) | Helped |
| Apply curvature-based allocation to piecewise-linear valuations when segment lengths cover the maximum item utility | ICA · ICA with piecewise-linear valuations | approximation ratio: (1 + ϵ)4/3 | Helped |
Closest papers by meaning
- 1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations (AAAI 2024 · similarity 0.92)
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.90)
- Constrained Fair and Efficient Allocations (AAAI 2025 · similarity 0.89)
- Weighted Envy-Freeness for Submodular Valuations (AAAI 2024 · similarity 0.89)
- Maximizing Nash Social Welfare under Two-Sided Preferences (AAAI 2024 · similarity 0.89)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.