PaperlayerView exact revision on arXiv

Source-linked AI summary

Easier, but Not Easy: Nash Welfare under Lexicographic Valuations

Soumil Aggarwal, Rohit Vaish, Jatin Yadav

arXiv:2608.24537v1cs.GTcs.DS

TL;DR

The paper asks whether large priority gaps make Nash welfare maximization tractable under lexicographic valuations. It combines configuration-LP rounding with domination-based branch-and-prune algorithms, finding stronger approximation and exact results in structured cases while preserving hardness.

  • Problem

    The paper investigates whether lexicographic valuations make Nash welfare maximization tractable despite removing most arbitrary cardinal tradeoffs.

  • Method

    The paper uses configuration-LP rounding and a domination-based branch-and-prune framework with mutual-exclusion and leaf-counting arguments.

  • Results

    The paper obtains stronger approximation and exact algorithms in important cases, while proving NP-hardness for ordered valuations and 0.9996-approximation hardness for doubling valuations.

  • Takeaways & Limitations

    Lexicographic valuations make Nash welfare easier, but not easy: improved algorithms coexist with significant computational hardness.

  • Takeaways & Limitations

    The exact algorithms are XP in the number of agents, and extending them to fixed-parameter algorithms or weakly lexicographic valuations remains open.

Abstract

from arXiv · show

Maximizing Nash welfare over indivisible goods is a central problem in resource allocation. For additive valuations, the best-known approximation factor is roughly $e^{-1/e}\approx0.692$, and the problem is APX-hard. We study Nash welfare maximization under lexicographic valuations, where every good is worth more than the total value of all lower-ranked goods. This large-gap structure makes preferences almost ordinal, which might suggest that the problem becomes easy. We show, however, that the picture is more nuanced: although lexicographic valuations enable stronger algorithmic guarantees, they retain significant computational hardness. Our first main result is a $(1/\sqrt{2}-ε)\approx(0.707-ε)$-approximation algorithm for weighted Nash welfare under lexicographic valuations, improving over the inherited guarantee of roughly $e^{-1/e}$. The algorithm rounds the configuration LP for Nash welfare, for which we show a matching integrality gap of $\sqrt{2}$. Our second main contribution is an exact algorithmic polynomial time framework for ordered lexicographic instances and doubling lexicographic instances. We introduce a domination-based branch-and-prune method for which we prove a mutual-exclusion property between sibling subtrees and use a matrix-based leaf-counting argument to bound the pruned recursion tree by a polynomial when the number of agents is constant. Finally, we show that large gaps do not eliminate hardness, as Nash welfare maximization is NP-hard even for ordered lexicographic valuations, and it is NP-hard to obtain a $0.9996$-approximation even for doubling lexicographic valuations. Thus, lexicographic valuations make Nash welfare maximization easier, but not easy: they admit tighter approximation and exact algorithms in important cases, yet still require intricate techniques and preserve some of the hardness of the general additive setting.

1 Introduction

Lexicographic valuations support stronger approximation and exact algorithms for Nash welfare, but substantial hardness remains. The paper develops configuration-LP rounding and domination-based branch-and-prune techniques to characterize this trade-off.

  • 1 Introduction: Nash welfare maximization seeks allocations of indivisible goods that balance efficiency and fairness through the geometric mean of agents’ utilities.The objective rewards high total value while penalizing imbalance across agents.
  • 1 Introduction: Lexicographic valuations impose priority gaps that remove most arbitrary cardinal tradeoffs, raising whether Nash welfare becomes tractable.A higher-ranked good cannot be compensated for by any collection of lower-ranked goods.
  • 1 Introduction: The resulting landscape is easier than general additive valuation settings but still computationally rich and technically nontrivial.The algorithms rely on domination properties that do not have a direct counterpart for general additive valuations.
  • 1.1 Our results: √2 is the exact configuration-LP integrality gap, making the approximation guarantee tight for that relaxation.The matching lower bound gives a complete characterization of what configuration-LP rounding can achieve here.
  • 1.1 Our results: Polynomial-time exact algorithms exist for ordered and doubling lexicographic instances when the number of agents is constant.The framework uses domination-based branch-and-prune, mutual exclusion between sibling subtrees, and matrix-based leaf counting.
  • 1.3 Overview of Our Techniques: An EPTAS is available for ordered lexicographic valuations with an arbitrary number of agents, using constant lookahead over the top n+ℓ goods.Here ℓ=O(log 1/ε), and the approach is motivated by the need to account for goods beyond the top n.
  • 1.1 Our results: Nash welfare remains NP-hard for ordered valuations and NP-hard to approximate within 0.9996 for doubling valuations.Thus, even common rankings or factor-two value separation do not remove computational hardness.

2 Preliminaries

The paper formalizes Nash welfare, allocation models, lexicographic valuation classes, and separable concave welfare objectives. It also introduces the configuration-LP comparison underlying the approximation guarantee.

  • Valuation classes: Lexicographic valuations require each good to exceed the total value of all lower-ranked goods, making bundle comparisons depend on the highest-ranked differing good.Ordered instances share a common ranking, while doubling instances require each good to be worth at least twice the next lower-ranked good and may use different rankings.
  • Welfare objectives: Nash welfare is the geometric mean of agents’ utilities, balancing total value against imbalance across agents.The weighted version uses positive agent weights summing to one; equal weights recover unweighted Nash welfare.
  • Welfare objectives: Separable concave welfare sums increasing concave transformations of agents’ utilities, with h_i(x)=log x equivalent to maximizing Nash welfare.The framework also covers weighted p-mean welfare through suitable choices of the functions.
  • Approximation framework: Theorem 1 gives a polynomial-time (1/√2−ε)-approximation for weighted Nash welfare under lexicographic valuations.The proof uses configuration-LP rounding, and the resulting deterministic algorithm preserves the same guarantee.
  • Approximation framework: The configuration LP has an integrality gap exactly √2, and Theorem 2 establishes the matching comparison bound for block-balanced and valid allocations.The proof constructs safe groups after transformations that weakly increase the Nash-welfare ratio.

4 Algorithms for Structured Subclasses

Structured lexicographic instances admit exact polynomial-time algorithms for constant numbers of agents, plus an EPTAS for ordered valuations without that restriction. The methods prune domination-based recursion trees and exploit concavity and valuation structure.

  • 4.1 Warm-Up: Identical Valuations and Uniform hi Functions: For identical valuations and identical strictly increasing, strictly concave functions, an optimal allocation gives all agents with multiple goods lower utility than the others.Consequently, the best n−1 goods go one each to n−1 agents, while one agent receives the worst m−n+1 goods.
  • 4.1 Warm-Up: Identical Valuations and Uniform hi Functions: Under these identical-valuation conditions, an optimal allocation maximizing the separable concave welfare can be computed in polynomial time.The result applies when the common valuation and common concave function are computable in polynomial time.
  • 4.2 Ordered Lexicographic Valuations: For ordered lexicographic valuations and constant n, the domination-based algorithm computes an allocation maximizing Wh for any polynomial-time computable increasing concave functions.Domination pruning is correct because assigning a good to a dominated agent cannot appear in an optimal completion.
  • 4.2 Ordered Lexicographic Valuations: Mutual exclusion between explored sibling branches bounds the recursion tree polynomially, with the leaf count controlled by a matrix-based argument.Since the total number of nodes is at most m times the number of leaves, the leaf bound yields polynomial running time for constant n.
  • 4.2 Ordered Lexicographic Valuations: For arbitrary n, an EPTAS for unweighted Nash welfare under ordered lexicographic valuations achieves at least (1−ε) of optimum in time (1/ε)^O(log 1/ε) · (n^3+nm).The guarantee and running time hold for every ε>0.
  • 4.3 Doubling Valuations: For doubling valuations with constant n, a restricted-completion recursion yields polynomial-time exact algorithms for separable concave welfare objectives, including weighted Nash welfare.Candidate recipients are selected using marginal gains, while mutual exclusion bounds the recursion leaves.

5 Hardness Results

Lexicographic valuations preserve substantial hardness: exact Nash welfare optimization is NP-hard for ordered instances, and near-exact approximation remains hard for doubling instances.

  • Ordered lexicographic valuations: NP-hardness holds for Ordered-Lex-NSW, the threshold decision problem for Nash welfare under ordered lexicographic valuations.The proof reduces Perfect 3D Matching to this decision problem.
  • Ordered lexicographic valuations: The reduction creates tuple agents, signature goods from X ∪ Y ∪ Z, and |T|−n dummy goods under a common preference order.Signature valuations are increased using constants B = 10 and C = 3.
  • Ordered lexicographic valuations: Dummy goods occupy distinct agents exclusively, leaving n agents to receive the 3n goods in X ∪ Y ∪ Z.The construction uses phased Nash-product gains to enforce the intended allocation structure.
  • Reduction structure: The Y and Z layers provide controlled multiplicative gains relative to prior assignments, rewarding signature matches and aligning allocations with perfect 3D matchings.The construction first fixes X assignments, then Y assignments conditional on X, and finally Z assignments conditional on X and Y.
  • Reduction correctness: A perfect 3D matching exists if and only if the constructed instance has an allocation with Nash welfare at least θ.The reduction also has polynomial encoding size after scaling valuations to integers.
  • Doubling valuations: NP-hardness of approximation persists for doubling valuations: achieving a factor of 0.9996 is NP-hard.This result follows from a gap-preserving reduction from 4-dimensional matching.

6 Conclusion and Future Directions

The paper concludes that lexicographic valuations offer stronger algorithms while retaining hardness, and identifies open questions about approximation, parameterized exact algorithms, and ties.

  • Conclusion: A (1/√2−ε)-approximation is obtained for general lexicographic valuations, alongside exact polynomial-time algorithms for ordered and doubling subclasses with a constant number of agents.The approximation uses configuration-LP analysis, while the exact algorithms use domination-based branch-and-prune.
  • Conclusion: Exact optimization remains NP-hard for ordered lexicographic valuations, while APX-hardness persists for doubling valuations.Together, these results establish a mixed computational landscape across lexicographic subclasses.
  • Future directions: Open questions ask whether a stronger relaxation can improve the approximation guarantee or whether lexicographic valuations have a matching hardness threshold.The current exact algorithms are XP in the number of agents.
  • Future directions: Further directions include determining whether ordered or doubling instances admit f(n) · poly(m) exact algorithms and whether results extend to weakly lexicographic valuations with ties.These questions concern fixed-parameter tractability and indifference between items.

A Additional Related Work: Generalized Mean welfare

Related work places generalized p-mean welfare between broad approximation results for subadditive valuations and stronger results for additive or identical valuations.

  • Subadditive valuations: For subadditive valuations, an Ω(1/n)-approximation is known for weighted p-mean welfare measures with p ∈ (−∞, 1].This guarantee applies across the stated range of p.
  • Subadditive valuations: For subadditive valuations, ω(1/n) approximations require an exponential number of value queries.The cited results make the Ω(1/n) approximation essentially tight in that query model.
  • Additive valuations: For additive valuations, related generalized mean-welfare work reports a 7/8 ≈ 0.935 guarantee.The supplied passage presents this as a result for additive valuations without further qualification.
  • Egalitarian welfare: Egalitarian welfare admits an ˜Ω(1/n^ε) approximation for n agents and is NP-hard to approximate beyond a factor of 1/2.These results concern the p → −∞ limit of p-mean welfare.
  • Identical additive valuations: For identical additive valuations, a PTAS is known for weighted p-mean welfare.The passage also notes additional results for a constant number of agents.

B Extensions to Generalized p-Mean Welfare Measures

The paper’s exact algorithms extend beyond Nash welfare to weighted p-mean objectives through separable concave formulations and scaling conditions.

  • Generalized objectives: The exact algorithms are stated for separable concave objectives.This objective class provides the framework for the subsequent welfare extensions.
  • Objective formulation: Weighted Nash welfare is captured by setting h_i(x) = w_i log x in the separable concave formulation.Weighted p-mean welfare is represented using h_i(x) = w_i sign(p) x^p.
  • Ordered valuations: For ordered lexicographic valuations, the exact-algorithm theorem applies to weighted p-mean welfare for p < 1, p ≠ 0, and to weighted Nash welfare as p → 0.The extension follows from the generalized objective formulation.
  • Doubling valuations: For doubling valuations, the exact algorithm extends to weighted Nash welfare and weighted p-mean welfare for p ∈ (0, 1) when the additional scaling condition holds.The stated condition is satisfied by h_i(x) = w_i log x and h_i(x) = w_i x^p for p ∈ (0, 1).

C Integrality gap of the config LP for lexicographic valuations

The configuration LP has an integrality gap approaching sqrt(2) for lexicographic valuations, established through a four-agent, five-good construction whose fractional solution outperforms every integral allocation.

  • The construction uses four agents, five goods, weights 1/2 − δ, 1/2 − δ, δ, δ, and parameters δ = 1/L and γ = 2^-L2.For sufficiently large L, the instance has lexicographic valuations.
  • sqrt(2): The configuration LP integrality gap approaches sqrt(2) for lexicographic valuations.The logarithmic difference between fractional and integral optima approaches 1/2 ln 2.
  • The displayed fractional configuration-LP solution provides the benchmark whose objective is compared against integral allocations.The LP objective is evaluated explicitly for this fractional solution.
  • The integral allocation A = ({g1}, {g4}, {g2, g3}, {g5}) has weighted Nash welfare diverging as L approaches infinity.Its welfare is L^(1/2−δ)(1 + 4γ)^(1/2−δ)(2 + 8γ)^δ.
  • Every competing integral allocation is bounded by constant utility constraints and therefore cannot match the constructed allocation for large enough L.The proof bounds relevant agents’ utilities using g1, g4, and g5 assignments, then obtains the asymptotic comparison.

D Proof of Theorem 2

Theorem 2 is proved by transforming arbitrary valid and block-balanced allocations while preserving validity and weakly increasing their Nash-welfare ratio, then reducing the comparison to safe groups.

  • Theorem 2 compares every block-balanced allocation AB with every valid allocation AV through their Nash products.
  • The proof starts with boundary cases and dummy zero-valued goods so the instance can be assumed to have at least 2n goods.When too few goods or zero-valued first goods exist, both Nash products are zero.
  • Safe transfer preserves or increases Nash welfare when the donor’s remaining utility is at least the recipient’s utility.The two-agent product change is nonnegative and strictly positive under a strict inequality.
  • Allocation transformations align first-block goods, compress them to three types, truncate and sort the denominator, and normalize remaining g3 assignments.These operations weakly increase the ratio ρ while retaining validity or block balance where required.
  • Lexicographic inequalities and safe grouping reduce the final ratio bound to groups of at most three agents.The proof uses the inequalities v1 ≥ v2 + v3 + V4, v2 ≥ v3 + V4, and v3 ≥ V4.

D.6 Allocation of the lower types

Lower-valued good types are processed sequentially over a contiguous open interval, with each step certifying safe singleton, pair, or triple groups until no open agents remain.

  • D.6 Allocation of the lower types: The invariant keeps open agents in a consecutive interval whose left endpoint advances with the cumulative number of processed goods.No representative in the interval has received previously processed lower types.
  • D.6 Allocation of the lower types: For each lower type gj, its recipients in the denominator form a prefix of the open interval, while numerator recipients are rearranged into a suffix.These forms enable one-step certification and preserve the invariant after removal.
  • D.6 Allocation of the lower types: Lexicographic inequalities bound singleton and open-pair ratios by 2 across the relevant intersections and differences of recipient sets.The bounds use Vj+1 ≤ vj, v3 ≥ Vj, and v2 ≥ v3 + Vj.
  • D.6 Allocation of the lower types: Singletons in Γj are matched with agents in Λj; when the left agent is an open pair, all three agents form a safe triple.The construction handles both singleton–singleton and pair–singleton matches.
  • D.6 Allocation of the lower types: 14/5: The triple product is bounded by 14/5, which is below 2 under Vj+1 ≤ Vj/2.After certification, remaining open agents are finalized as safe singletons or pairs, and the transformations preserve the ratio bound.
  • D.6 Allocation of the lower types: The resulting partition into groups of size 1, 2, or 3 yields the theorem’s overall ratio bound after multiplying group inequalities.

E Missing Proofs from Section 4

The domination lemma justifies pruning any branch that assigns a good to a dominated agent, because reallocating that good to the dominating agent strictly improves the objective.

  • A dominating agent is better than another agent for a good under every completion of the remaining lower-ranked goods.
  • No optimal completion assigns the good to the dominated agent, so the corresponding recursive branch can be safely pruned.
  • The proof reallocates the good from the dominated agent to the dominating agent and compares marginal objective gains using decreasing marginal functions.The resulting completion has strictly larger objective value.

E.1 Missing Proofs from Section 4.1

The proofs characterize the structure of optimal allocations under lexicographic valuations: agents holding multiple goods must be the least-utility agents, forcing a canonical allocation pattern.

  • Any agent receiving at least two goods has lower utility than every other agent in an optimal allocation.
  • Consequently, exactly one agent receives two or more goods when m > n, while the remaining agents receive the best n −1 goods distinctly.
  • When m = n, every agent receives exactly one good in an optimal allocation.

E.2 Missing Proofs from Section 4.2

The missing proofs bound the branch-and-prune recursion tree by encoding descendant allocations in matrices and exploiting mutual exclusion between sibling branches.

  • The subtree rooted at A has at most a matrix-based expression involving pairwise dot products of allocation-matrix columns.The bound is stated as a product over agent pairs of terms 1 + M(A)_r · M(A)_s.
  • The proof proceeds by induction on the number of goods remaining, comparing each child matrix with the parent matrix after deleting the current-good row.
  • The resulting inequalities establish that the sibling branching probabilities sum to at most one, enabling a random directed-graph argument to complete the leaf bound.
  • Mutual exclusion across sibling branches ensures that, for each later good, at most one sibling subtree can allocate it to its corresponding agent.

E.2.1 Proof of Theorem 4

For ordered lexicographic valuations, the algorithm approximates optimal Nash welfare by enumerating a bounded prefix assignment and solving the remaining assignment through maximum-weight matching.

  • For every ε > 0, the algorithm achieves a (1 −ε)-approximation in time (1/ε)O(log 1/ε) · (n3 + nm).
  • Every Nash-optimal allocation assigns the goods g1, …, gn to distinct agents.
  • The algorithm enumerates assignments of a short block of later goods, then constructs a weight matrix for assigning the first n goods.
  • A maximum-weight perfect matching is computed with the Hungarian algorithm, while all remaining goods are assigned to an arbitrary agent.

E.3 Missing Proofs from Section 4.3

The ordered and doubling lexicographic frameworks use domination to restrict recursive completions, while matrix leaf counting controls the resulting search tree.

  • In doubling instances, an agent selected by marginal gain weakly dominates agents outside a designated eligible set for the relevant favorite good.
  • Therefore, every optimal restricted completion assigns the selected favorite good to an agent in the designated eligible set.
  • When two agents share the same favorite good, any common unallocated good is dominated in one direction under one of the two partial allocations.
  • The leaf-counting proof extends the earlier matrix argument by replacing the currently allocated good and reusing the same probabilistic bound.

F Missing Proofs from Section 5

The proof characterizes allocations meeting threshold θ: dummy-good recipients are isolated, while the remaining agents receive matching signature goods, yielding an equivalence with perfect 3D matching.

  • Reduction correctness: Lemma 11 establishes that a perfect 3D matching exists exactly when the constructed instance has an allocation with Nash welfare at least θ.The forward direction assigns dummy goods outside the matching and three signature goods to each matched agent; the reverse direction derives a perfect matching from any threshold-achieving allocation.
  • Allocation structure: Agents receiving dummy goods cannot receive any other good in a Nash-optimal allocation.A transfer to an agent without a dummy good would improve Nash welfare because the recipient’s gain overwhelms the donor’s utility loss.
  • Z-goods and matching: Agents without dummy goods receive at most one Z-good and, in a threshold-achieving allocation, their signature Z-goods complete the matching.Together with the X- and Y-signature assignments, the signature goods cover X ∪Y ∪Z exactly once, so the agents correspond to a perfect 3D matching.

F.1 Proof of Theorem 7

Theorem 7 reduces hard 4D-matching instances to Nash welfare under lexicographic, specifically doubling, valuations. The construction separates dummy, supporting, signature, and insignificant goods so matching size creates a welfare gap.

  • Hardness result: Theorem 7 shows NP-hardness of achieving a 0.9996-approximation for Nash welfare even with doubling valuations.The reduction is from 4D-matching and uses instances with exactly 3n quadruples.
  • Source problem: 4D-matching asks for the largest subset of quadruples whose elements are disjoint across four sets W, X, Y, and Z.The source hardness result distinguishes matchings of size at least n(1−ε) from those of size at most n(53/54+ε).
  • Construction: The reduction creates one agent per quadruple, goods for the four element sets, dummy goods, supporting goods, and agent-specific signature goods.Each agent’s corresponding quadruple determines its signature goods, while remaining goods are insignificant.
  • Completeness: Assigning supporting goods and signature goods to agents representing a large 4D-matching yields high Nash welfare, with dummy goods allocated to some remaining agents.Insignificant goods receive geometrically decreasing values, keeping their total value below q and preserving lexicographic, doubling valuations.
  • Soundness: If every 4D-matching has size at most (c+ε)n, the constructed instance’s maximum Nash welfare is strictly below 0.9996 × θ.The soundness argument partitions nondummy agents according to whether they receive all signature goods and bounds their utilities accordingly.
Loading 2608.24537v1…