Research map / Learning theory and algorithms / Submodular and game algorithms
Maximizing Nash Social Welfare under Two-Sided Preferences
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies computational complexity of maximizing Nash social welfare for many-to-one two-sided matchings (workers and firms with cardinal valuations), giving hardness, approximation, FPT, and polynomial-time results for restricted domains.
Problem
Maximizing Nash social welfare (geometric mean / Nash product of utilities) in many-to-one two-sided matching where workers and firms both have cardinal valuations and firms have capacities.
Approach
Extends Nash welfare from one-sided fair division to two-sided matching; the worker-firm edge utility is combined on both sides, yielding NP-hardness already at capacity 2 and ternary valuations, plus approximation (1/sqrt(OPT), QPTAS), FPT (3^m, polynomial-multiplication 2^m) and polynomial algorithms for restricted domains.
Key results
- Maximizing Nash welfare is NP-hard even when each firm has capacity 2, valuations are in {0,1,2}, and each agent has degree at most 3.
- A 1/sqrt(OPT)-approximation in polynomial time for positive valuations, and a constant approximation when valuations and capacities are bounded by a constant.
- An exact O*(3^m) FPT algorithm in the number of workers, and an O*(2^m) FPT approximation scheme (1+eps)^{-(n+1)/(m+n)} via polynomial multiplication.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict every firm to capacity 1 | Two-sided Nash welfare maximization · Two-sided matching | computational complexity | Helped |
| Allow firm capacity 2 while restricting valuations to {0,1,2} and degree to at most 3 | Two-sided Nash welfare maximization · Two-sided matching | computational complexity | Hurt |
| Require symmetric binary valuations | Two-sided Nash welfare maximization · Symmetric binary valuations | computational complexity | Helped |
| Use positive valuations and reduce to submodular maximization | Two-sided Nash welfare maximization · Positive-valuation instances | approximation ratio: $\frac{1}{\sqrt{\opt}}$ | Helped |
| Bound valuations and firm capacities by a constant | Two-sided Nash welfare maximization · Positive valuations with constant-bounded valuations and capacities | approximation ratio | Helped |
| Restrict to a constant number of firms and polynomially-bounded valuations | Two-sided Nash welfare maximization · Constant-firm instances | approximation ratio: $\frac{1}{(1+\varepsilon)}$ | Helped |
| Bound every firm capacity by a constant | Dynamic programming algorithm · Two-sided matching | running time: $\OO^\star(3^m)$ to $\OO^\star(2^m)$ | Helped |
| Restrict all agents to degree at most 2 | Two-sided Nash welfare maximization · Degree-at-most-2 instances | optimality | Helped |
Surprising findings
- Maximizing Nash welfare is NP-hard even for two identical firms with symmetric valuations, and the problem is NP-hard under strict preferences.
- Capacity-1 instances are polynomial-time solvable via max-weight bipartite matching, but capacity 2 already yields NP-hardness.
Limitations
- No constant-factor approximation is known for the general problem.
- Polynomial-time algorithms are restricted to special cases (degree at most 2 or 3 with capacity exactly 2, symmetric binary valuations); asymmetric binary case left open.
Experimental setup
Metrics: Nash social welfare approximation ratio running time
Builds on: Eisenberg-Gale convex program submodular fair division with matroid constraints rainbow perfect matching bihierarchical quota-constraint rounding
Closest papers by meaning
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.89)
- Constrained Fair and Efficient Allocations (AAAI 2025 · similarity 0.88)
- Welfare Maximization in Perpetual Voting (Student Abstract) (AAAI 2024 · similarity 0.88)
- Weighted Envy-Freeness for Submodular Valuations (AAAI 2024 · similarity 0.87)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.87)
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning (NeurIPS 2024 · similarity 0.87)
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.