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

Nash welfare maximization under lexicographic valuations may seem tractable because sharp priority orderings largely remove arbitrary cardinal tradeoffs. The paper develops approximation and exact algorithms while proving that substantial hardness persists.

  • Problem

    The paper asks whether the large-gap structure of lexicographic valuations makes Nash welfare maximization tractable.

    Source: §1 · p. 2

  • Method

    The paper combines configuration-LP rounding with domination-based branch-and-prune methods for structured lexicographic instances.

    Source: §1 · p. 2, §1.1 · p. 3

  • Results

    The paper obtains stronger algorithms, including a PTAS for ordered instances, while proving NP-hardness for ordered valuations and persistent APX-hardness for doubling valuations.

    Source: §1.3 · p. 6, §6 · p. 29

  • Takeaways & Limitations

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

    Source: §1 · p. 2, §6 · p. 29

    The exact algorithms are XP in the number of agents, and extending them to an f(n) · poly(m) exact algorithm remains open.

    Source: §6 · p. 29

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 improve Nash-welfare algorithms through large-gap structure, but the problem remains computationally hard. The paper develops stronger approximation and exact methods while establishing tight relaxation limits and hardness under severe restrictions.

1 Introduction

  • Lexicographic valuations make Nash-welfare optimization easier than general additive valuations, yet retain significant computational hardness.Their superincreasing values make bundle comparisons depend on the most preferred differing good while preserving cardinal welfare structure.Source: §1 · p. 2, §1.2 · p. 4

1.1 Our results

  • The paper gives a polynomial-time (1/√2−ε)≈(0.707−ε)-approximation for general lexicographic valuations, improving on the nearly e−1/e≈0.692 additive guarantee.The algorithm rounds the configuration LP using domination relations and agent grouping, and the LP has matching integrality gap √2.Source: §1.1 · pp. 2–3
  • For constant agents, domination-based branch-and-prune gives exact polynomial-time algorithms for ordered and doubling valuations, while ordered instances admit an EPTAS for arbitrary agents.The method uses mutual exclusion between sibling subtrees and matrix-based leaf counting; it also extends to specified weighted p-mean objectives.Source: §1.1 · pp. 3–4

1.2 Why lexicographic valuations?

  • Large gaps do not make Nash welfare tractable: ordered instances are NP-hard, and doubling instances are NP-hard to approximate within 0.9996.The reductions encode Perfect 3-Dimensional Matching and 4-Dimensional Matching, respectively.Source: §1.1 · p. 4, §1.3 · p. 7

1.3 Overview of Our Techniques

  • The algorithmic overview shows that top-good matching alone can lose a factor of two, whereas O(log 1/ε) lookahead yields an EPTAS and domination pruning enables exact search for constant agents.The exact framework branches over top-good matchings, prunes dominated assignments, and bounds leaves via mutual exclusion and binary-matrix arguments.Source: §1.3 · pp. 5–7

1.4 Related Work

  • The introduction situates the results within prior APX-hardness, approximation, lexicographic-welfare, and configuration-LP-rounding literature, then organizes the paper into modeling, algorithms, and hardness sections.Prior work gives an e−1/e≈0.692 weighted additive approximation and establishes earlier hardness for lexicographic Nash welfare.Source: §1.4 · p. 8, §1.5 · p. 9

2 Preliminaries

This section sets up the allocation, valuation, welfare, and oracle framework, develops configuration-LP rounding for lexicographic valuations, and establishes the block-balanced comparison underlying its guarantee. It also proves the Nash-welfare ratio bound through structure-preserving transformations, normalization of the first two blocks, and a partition into safe groups.

2 Preliminaries

  • Lexicographic valuations impose superincreasing ranks, while ordered and doubling valuations are structured subclasses used to characterize common or agent-specific good orderings.Ordered instances share one ranking across agents; doubling valuations are lexicographic but need not be ordered.Source: §2 · p. 9, Ordered lexicographic valuations · p. 9, Doubling valuations · pp. 9–10
  • Nash welfare is the geometric mean of utilities, with weighted and p-mean generalizations represented through separable concave objectives; exact algorithms use comparison oracles when needed.For unweighted Nash welfare, objective comparisons reduce to exact comparisons of rational Nash products, so the standard Turing model suffices.Source: Doubling valuations · p. 10

3.1 The Feng-Li Configuration LP and its Rounding

  • The weighted configuration LP has integrality gap exactly √2 even when all valuations are lexicographic.This matching lower bound complements the improved rounding guarantee.Source: Doubling valuations · p. 12

3.2 Nash welfare ratio in the auxiliary instance

  • Theorem 2 shows that enforcing block-balanced allocations in the copied auxiliary instance loses at most a factor of √2 in Nash welfare.The instance has identical agents, lexicographically ordered good types, and valid allocations assign copies of each type to distinct agents.Source: §3.2 · p. 15
  • Theorem 2 bounds the Nash-welfare ratio between every block-balanced allocation and every valid allocation.Block-balanced allocations assign goods in each aligned block to distinct agents; the theorem’s explicit numerical bound is not included in the supplied passage.Source: §3.2 · p. 15
  • The proof applies weakly ratio-increasing allocation and valuation transformations, including first-block alignment, L-normalization, three-mini-block reduction, and second-block simplification.The normalized first block is grouped into mini-blocks A, B, and C, while denominator goods beyond the second block are discarded and remaining assignments are reordered.Source: §3.2 · pp. 15–16, Figure 2 · p. 16
  • The analysis uses a weak lexicographic condition in this section, although the definition in Section 2 requires strict inequality.This relaxation is stated explicitly as sufficient for the argument.Source: §3.2 · p. 15
  • The core argument groups agents into safe singletons, pairs, and groups of at most three while processing lower-valued goods through prefix-suffix structure.Safe transformations preserve a consecutive interval of open agents; after all open agents are eliminated, multiplying group inequalities and taking n-th roots yields the ratio bound.Source: §3.2 · p. 16

4 Algorithms for Structured Subclasses

This section develops domination-based exact algorithms and approximation schemes for structured lexicographic instances, with polynomial-time guarantees for important subclasses. It focuses on branch-and-prune methods that exploit lexicographic structure, including pruning dominated assignments and bounding recursion trees through mutual exclusion and matrix arguments.

4 Algorithms for Structured Subclasses

  • For any partial allocation, domination certifies that assigning a specified good to the dominated agent cannot appear in an optimal completion, enabling safe recursion-tree pruning.The condition compares worst-case marginal gains, and Lemma 1 proves that every completion assigning the good to the dominated agent is suboptimal.Source: §4 · pp. 17–18

4.1 Warm-Up: Identical Valuations and Uniform hi Functions

  • With identical valuations and identical strictly increasing, strictly concave functions, an optimal allocation gives one agent the worst m−n+1 goods and one best good to each other agent.Consequently, the resulting optimal allocation can be computed in polynomial time when the common function is polynomial-time computable.Source: §4.1 · p. 18

4.2 Ordered Lexicographic Valuations

  • For ordered lexicographic valuations with constant n, the algorithm computes an allocation maximizing any polynomial-time computable increasing concave welfare function in polynomial time.It processes goods in common decreasing order, branches only to undominated agents, and uses mutual exclusion between sibling subtrees plus matrix leaf counting to bound recursion size.Source: §4.2 · pp. 19, 21, 22

4.2.1 An EPTAS for General n

  • A (1−ε)-approximation for unweighted Nash welfare under ordered lexicographic valuations runs in time (1/ε)^O(log 1/ε) · (n^3 + nm).This extends the ordered-valuation algorithmic treatment to a nonconstant number of agents through an EPTAS.Source: §4.2.1 · p. 22

4.3 Doubling Valuations

  • For doubling valuations and constant n, a polynomial-time algorithm optimizes separable concave welfare functions satisfying the theorem’s marginal-function condition, including weighted Nash and weighted p-mean welfare.The algorithm enumerates agents receiving goods and candidate favorite goods, then computes optimal restricted completions using weak domination to prune assignments.Source: §4.3 · pp. 22–23
  • For an agent maximizing Δ_s(2v_s(B_s), v_s(f_s)), the favorite feasible good f_s belongs to some agent in Z_f_s in every optimal restricted completion.This identifies the good that must be allocated before recursively trying candidate agents.Source: §4.3 · p. 24
  • Weak domination safely prunes candidate assignments because a weakly dominated agent cannot receive the selected good in any optimal completion.The algorithm therefore tries all remaining assignments of the selected good while preserving at least one optimal restricted completion.Source: §4.3 · pp. 24–25
  • Sibling subtrees satisfy mutual exclusion: for every other unallocated good, at least one sibling subtree never allocates it to its corresponding child agent.This follows from the refined dominance lemma for agents sharing the same favorite good.Source: §4.3 · p. 25
  • A matrix-based leaf-counting argument applies the mutual-exclusion property to bound the recursion tree of OptimalRestrictedCompletion.The matrix records whether each remaining good can be allocated to each agent in a subtree, yielding the same leaf bound used for the ordered lexicographic case.Source: §4.3 · pp. 25–26
  • A polynomial-time exact algorithm computes an optimal complete allocation for doubling valuations when the number of agents is constant.It runs OptimalRestrictedCompletion for each of O(mn) choices of maximum-valued goods, with each call taking O((m + 1)(n^2) · poly(n, m)) time.Source: §4.3 · p. 26

5 Hardness Results

The section establishes NP-hardness for Nash welfare under ordered lexicographic valuations and a 0.9996-approximation hardness result for doubling valuations. The ordered-hardness reduction encodes perfect 3D matching through phased multiplicative valuation gains.

Ordered lexicographic valuations

  • Nash welfare maximization is NP-hard for ordered lexicographic valuations.The decision problem Ordered-Lex-NSW asks whether an allocation reaches a threshold θ.Source: §5 · p. 27
  • The ordered-hardness reduction maps Perfect 3D Matching to allocations whose Nash product sequentially favors signature X-, Y-, and Z-goods.Dummy goods are distributed first, then X, Y, and Z act as successive multiplicative phases, so reaching threshold θ is equivalent to selecting non-conflicting signature triples [Karp, 1972].Source: §5 · pp. 28–29
  • The constructed ordered instance has polynomial encoding size after scaling valuations and the threshold by B30n.The scaled values use O(n + |T|) bits, while the threshold and entire construction remain polynomial in n and |T|.Source: §5 · p. 29

Doubling valuations

  • 0.9996-approximation hardness holds for Nash welfare even under doubling valuations.This follows from a gap-preserving reduction from 4-dimensional matching.Source: §5 · p. 29

6 Conclusion and Future Directions · Appendix

The paper establishes a nuanced computational landscape for Nash welfare under lexicographic valuations, combining improved approximation and exact algorithms with persistent hardness. It also identifies open questions about stronger relaxations, parameterized exact algorithms, and ties between items.

6 Conclusion and Future Directions

  • For Nash welfare under lexicographic valuations, the work obtains an approximation guarantee for general lexicographic valuations via a tight analysis of the configuration LP.Source: §6 · p. 29
  • Exact polynomial-time algorithms are obtained for ordered and doubling lexicographic valuations when the number of agents is constant.These algorithms are XP parameterized by the number of agents.Source: §6 · p. 29
  • The exact algorithms use domination-based branch-and-prune, whose recursion tree is polynomially bounded by a mutual-exclusion argument.Source: §6 · p. 29
  • Exact Nash welfare optimization remains NP-hard for ordered lexicographic valuations, while APX-hardness persists for doubling valuations.Source: §6 · p. 29
  • It remains open whether a relaxation stronger than the configuration LP can improve the approximation guarantee or whether lexicographic valuations have a matching hardness threshold.Source: §6 · p. 29
  • Future work should determine whether ordered or doubling valuations admit f(n) · poly(m) exact algorithms and whether results extend to weakly lexicographic valuations with ties.Source: §6 · p. 29

A Additional Related Work: Generalized Mean welfare

Prior work shows that weighted p-mean welfare has sharply varying approximation and complexity guarantees across valuation classes and welfare parameters. General subadditive valuations admit essentially tight Θ(1/n)-scale guarantees, while additive valuations range from efficient optimization to strong hardness and approximation schemes in special cases.

Subadditive valuations

  • For subadditive valuations, every weighted p-mean measure with p ∈ (−∞, 1] has an Ω(1/n)-approximation, and improving asymptotically requires exponentially many value queries [Chaudhury, Garg, and Mehta, 2021; Dobzinski, Nisan, and Schapira, 2005; Barman, Bhaskar, Krishna, and Sundaram, 2020].The known approximation is therefore essentially tight in the value-query model.Source: A Additional Related Work: Generalized… · p. 34

Additive valuations

  • For additive valuations, weighted utilitarian welfare is easy, weighted Nash welfare admits a 0.692-approximation but is NP-hard beyond 0.935, and egalitarian welfare has an ˜Ω(1/n^ε)-approximation but is NP-hard beyond 1/2 [Feng and Li, 2025; Garg, Hoefer, and Mehlhorn, 2024; Chakrabarty, Chuzhoy, and Khanna, 2009; Bezáková and Dani, 2005].These results demonstrate a diverse complexity landscape across p = 1, p = 0, and p → −∞.Source: A Additional Related Work: Generalized… · p. 34

Special cases

  • For additive valuations, weighted p-mean welfare has a PTAS with identical valuations and an FPTAS for a constant number of agents with possibly non-identical valuations [Garg, Husić, Murhekar, and Végh, 2022].The schemes apply across weighted p-mean welfare rather than only a single welfare parameter.Source: A Additional Related Work: Generalized… · p. 34

B Extensions to Generalized p-Mean Welfare Measures

The exact algorithms extend beyond Nash welfare to broad weighted p-mean objectives through separable concave formulations. Ordered lexicographic instances support all p < 1, p ≠ 0, while doubling instances support p ∈ (0, 1) under an additional scaling condition.

B Extensions to Generalized p-Mean Welfare Measures

  • The exact algorithms in Section 4 apply to separable concave objectives.Source: B Extensions to Generalized p-Mean… · p. 34
  • Weighted Nash welfare and weighted p-mean welfare arise by choosing h_i(x) = w_i log x and h_i(x) = w_i sign(p) x^p, respectively.Maximizing weighted p-mean welfare is equivalent to maximizing sign(p) times the weighted p-power sum because the outer power is monotone, with direction depending on p.Source: B Extensions to Generalized p-Mean… · p. 34
  • For ordered lexicographic valuations, Theorem 3 applies to weighted p-mean welfare for every p < 1, p ≠ 0, and to weighted Nash welfare as p → 0.Source: B Extensions to Generalized p-Mean… · p. 34
  • For doubling valuations, Theorem 5’s scaling condition holds for weighted Nash welfare and weighted p-mean welfare when p ∈ (0, 1), extending the exact algorithm to both objectives.Source: B Extensions to Generalized p-Mean… · p. 34

C Integrality gap of the config LP for lexicographic valuations

The section constructs a lexicographic instance showing that the configuration LP has a nonzero asymptotic integrality gap. Its fractional and integral optima differ by 1/2 ln 2 in the limit.

Instance construction

  • The construction uses four agents and five goods, with weights 1/2 − δ, 1/2 − δ, δ, δ, where δ = 1/L and γ = 2^−L^2.For sufficiently large L, the instance has lexicographic valuations.Source: C Integrality gap of the config LP for… · p. 35

Fractional solution

Integral solution

Integral optimum

  • Any competing allocation is bounded by constant utility constraints, so the displayed allocation is optimal for sufficiently large L.The argument forces g1 to a1 or a2 and limits the remaining agents’ utilities, yielding an upper bound of 3 for alternatives in the relevant case.Source: C Integrality gap of the config LP for… · p. 35

Integrality gap

D Proof of Theorem 2 … D.5 Allocation of the remaining copies of g3 in AV

The proof of Theorem 2 transforms the allocations through alignment, normalization, compression, and sorted second-block reassignment while preserving or improving the relevant Nash-welfare ratio. It then controls the remaining g3 copies in AV using safe groups based on lexicographic value inequalities.

D Proof of Theorem 2

  • The proof first handles degenerate instances and establishes a safe-transfer lemma: moving a good from i to j is welfare-nondecreasing when Ui − x ≥ Uj, and strictly improving under strict inequality.It also pads instances with zero-valued dummy copies when needed, without changing either allocation’s utilities or Nash welfare.Source: D Proof of Theorem 2 · p. 36

D.1 Aligning the first block

  • AV is modified so the first n goods go to distinct agents, using swaps or safe transfers, after which bundle permutations align ei with agent i in both allocations.The swaps preserve validity and Nash products, while the transfers rely on comparing the least valuable duplicated first-block good with the recipient’s highest-valued good.Source: §D.1 · pp. 36–37

D.2 The L-normalization

  • The L-normalization replaces ei by a new value-L good for agents preferring AB, preserves validity and block balance, and does not decrease the Nash-welfare ratio.The transformed L-valued goods form a prefix, enabling subsequent structural reductions.Source: §D.2 · p. 37

D.3 Compressing the first block to three mini-blocks

  • The first block is compressed to three mini-blocks by lowering intermediate good types to the tail value sum, which only increases the relevant utility ratios while retaining a lexicographic instance.The resulting first block consists of g1, g2, and g3, with the normalized structure illustrated by Figure 5.Source: §D.3 · p. 37, Figure 5 · p. 38

D.4 Second block allocation in AB

  • After discarding goods beyond e2n and sorting the second-block pairing in AB, the denominator product weakly decreases, so agent i has denominator utility val(ei) + val(en+i).The sorted pairing is valid because positions i and n+i cannot contain copies of the same type when each type has at most n copies.Source: §D.4 · p. 38

D.5 Allocation of the remaining copies of g3

  • Remaining g3 copies in AV are transferred from A to uncovered agents in B whenever possible, and within each mini-block their recipients can be made prefixes without changing validity or Nash welfare.These transformations use the fact that a top g1 item exceeds the combined value of all lower types.Source: §D.5 · p. 38
  • The final comparison partitions agents into singletons, pairs, and triples whose products of utility ratios are at most 2, using lexicographic inequalities and matched A/B agents to construct safe open pairs.Agents receiving g3 in both allocations form safe singletons, while unmatched cases are organized among four open-agent classes based on their numerator and denominator bases.Source: §D.5 · pp. 38–39

D.6 Allocation of the lower types

The lower types are processed sequentially while maintaining a contiguous open-agent interval. Each step certifies the relevant agents into safe groups, eventually eliminating all open agents and proving the target ratio bound.

Invariant

  • Processing each lower type maintains open agents as a contiguous interval whose representatives have received no previously processed lower types.The invariant starts with the initial open set and updates its left endpoint after each processed type.Source: §D.6 · pp. 40–41

Lower-type processing

  • For each type gj, numerator recipients among open agents can be rearranged into a suffix without decreasing Nash product or compromising previously established open-pair safety.The corresponding denominator recipients form a prefix, enabling the later matching argument.Source: §D.6 · p. 40

One-step certification

  • Lemma 13 certifies all agents receiving gj in either allocation into safe groups and preserves the invariant after removing them.The proof handles intersections directly, unmatched prefix or suffix agents individually, and matches remaining singleton agents across the two sides.Source: §D.6 · p. 41
  • The only nontrivial triple grouping is safe because its ratio product is at most 14/5 < 2, using Vj+1 ≤ Vj/2.This handles a suffix singleton matched to a prefix open pair.Source: §D.6 · p. 41

Termination

  • Processing terminates once the second block is exhausted, after which remaining open singletons and pairs can be finalized safely.The open interval must eventually move beyond the agent set, and remaining singletons have ratio at most 5/4 < 2.Source: §D.6 · pp. 41–42

Conclusion

  • Multiplying the group-wise bounds shows that every transformation preserves or improves the ratio, yielding the final bound of 2 and proving Theorem 2.All agents are partitioned into safe groups of size one, two, or three.Source: §D.6 · p. 42

E Missing Proofs from Section 4

The domination lemma rules out assigning an unallocated good to an agent dominated by another agent in any optimal completion. Reallocating that good to the dominating agent strictly increases weighted Nash welfare.

Domination Lemma

  • A completion assigning good g to dominated agent i cannot be optimal when agent k dominates i with respect to g.This applies to any partial allocation A and any completion that assigns g to i.Source: E Missing Proofs from Section 4 · p. 42

Proof

  • Reallocating g from i to k yields higher weighted Nash welfare because decreasing marginal values establish the first inequality and domination establishes the second.The proof compares the original completion B with the modified completion B′.Source: E Missing Proofs from Section 4 · p. 42

E.1 Missing Proofs from Section 4.1

The missing proofs establish that optimal allocations concentrate multiple goods with a single lowest-utility agent, forcing a canonical allocation structure.

Lemma 2

  • In any optimal allocation, every agent receiving at least two goods has lower utility than all other agents.The proof removes one good from that agent and uses strict concavity to show another agent dominates it, contradicting optimality.Source: §E.1 · pp. 42–43

Corollary 1

  • Consequently, one agent receives exactly the worst m−n+1 goods, while the best n−1 goods go one each to the other agents.For m=n, each agent receives one good; for m>n, Lemma 2 rules out multiple multi-good agents and prevents the lowest-utility agent from receiving any of the best n−1 goods.Source: §E.1 · p. 43

E.2 Missing Proofs from Section 4.2

The missing proofs establish a domination dichotomy for sibling allocations and bound each pruned recursion subtree using a matrix-based leaf count. The leaf bound follows from mutual exclusion across sibling branches and a probabilistic orientation argument.

Lemma 4

  • For any good unallocated in both allocations, either agent k dominates i under A or agent i dominates k under A′ when both agents receive their common most valuable unallocated good g.The proof uses lexicographic valuation gaps and strict concavity to show that assuming neither domination condition leads to contradictory inequalities.Source: §E.2 · pp. 43–44

Lemma 5

  • The subtree rooted at A has at most ∏_{r<s}(1 + M(A)_r · M(A)_s) leaves, where M(A) records remaining-good indicators by agent.The result is proved by induction on the number of goods remaining.Source: §E.2 · p. 44
  • Mutual exclusion across sibling branches implies that for each later good, the two sibling subtrees cannot both assign it to their respective branching agents, yielding M(C_i)_i · M′(A)_k + M(C_k)_k · M′(A)_i ≤ M′(A)_i · M′(A)_k.This inequality controls the cross terms in the inductive leaf-count bound.Source: §E.2 · pp. 45–46
  • A random directed-graph construction proves the remaining product inequality because distinct vertices cannot simultaneously have all incident edges directed outward.Edge directions use probabilities h_i,k and h_k,i, with the condition h_i,k + h_k,i ≤ 1 ensuring a valid distribution.Source: §E.2 · p. 46

E.2.1 Proof of Theorem 4

Theorem 4 establishes an EPTAS for Nash welfare under ordered lexicographic valuations, achieving a (1−ε)-approximation in time (1/ε)^O(log 1/ε) · (n^3 + nm). The proof combines structural properties of Nash-optimal allocations with enumeration and maximum-weight matching.

E.2.1 Proof of Theorem 4

  • A (1−ε)-approximation is computable in time (1/ε)^O(log 1/ε) · (n^3 + nm) for ordered lexicographic valuations.The algorithm returns an allocation whose Nash welfare is at least (1−ε) times optimal.Source: §E.2.1 · pp. 46, 48
  • Every Nash-optimal allocation assigns the top n goods g1,...,gn to distinct agents.If one agent receives two such goods and another receives none, transferring the lower-ranked good reduces the first agent’s utility by at most half while more than doubling the second’s, increasing Nash welfare.Source: §E.2.1 · p. 46
  • The algorithm enumerates assignments of the next ℓ goods, then uses a maximum-weight perfect matching to assign the top n goods.For each guessed assignment, matching weights are log(vi(gj)+vi(Bi)); remaining goods are given to an arbitrary agent.Source: §E.2.1 · pp. 47–48

E.3 Missing Proofs from Section 4.3

This section supplies missing proofs establishing domination for allocating a selected good, mutual exclusion between sibling recursion branches, and the matrix-based bound used to analyze the recursion tree.

Claim 1

  • Claim 1 shows that if s maximizes Δ_s(2v_s(B_s), v_s(f_s)), every optimal restricted completion allocates f_s to an agent in Z_{f_s}.The proof establishes that s weakly dominates every agent outside Z_{f_s} who can receive f_s, using lexicographic and doubling properties plus concavity and monotonicity conditions.Source: §E.3 · pp. 48–49

Algorithmic consequence

  • When ℓ = m − n, the algorithm finds the optimal Nash welfare because the residual set R is empty and v_i(R) = 0.This is stated as a special case of the algorithm’s guarantee.Source: §E.3 · p. 48

Lemma 8

  • Lemma 8 proves that when two agents share a favorite good, any other jointly unallocated good induces weak domination in at least one of the two partial allocations.The proof uses lexicographic ordering and strict concavity to derive a contradiction if neither domination condition holds.Source: §E.3 · pp. 49–50

Lemma 9

  • Lemma 9 extends the matrix-based leaf-counting argument to every recursion-tree node, using the same inductive structure as Lemma 5.The proof removes the row for the currently allocated good, preserves the key inequality h_i,k + h_k,i ≤ 1, and then reuses the probabilistic argument.Source: §E.3 · pp. 50–51

F Missing Proofs from Section 5

The section proves the reduction’s threshold characterization: a perfect 3D matching exists exactly when an allocation reaches Nash welfare θ. The reverse direction uses transfer-based structural claims to force every non-dummy agent to receive its three signature goods, yielding a perfect matching.

Transfer lemma

  • The transfer lemma shows that if another agent can receive a good with sufficiently greater relative gain, the original complete allocation cannot be Nash optimal.The proof removes the good, compares logarithmic utility gains, and applies domination under the resulting partial allocation.Source: F Missing Proofs from Section 5 · p. 51

Reduction correctness

Reverse direction

  • Any allocation meeting θ assigns each dummy good to a separate agent, leaving n non-dummy agents who each receive exactly one good from X, Y, and Z.Otherwise, transferring duplicated or mixed goods to an agent without them strictly increases the Nash product, contradicting optimality.Source: F Missing Proofs from Section 5 · pp. 52, 53, 54, 56
  • The n non-dummy agents must receive their signature goods from X and Y; any mismatched assignment makes the Nash product strictly smaller than θ^|T|.The argument uses permutation structure and the large valuation gaps to show that even one mismatch contradicts the threshold.Source: F Missing Proofs from Section 5 · pp. 53–56
  • Each non-dummy agent must also receive its signature good from Z, so their combined signature goods cover X ∪ Y ∪ Z exactly once and form a perfect 3D matching.A non-signature Z assignment similarly lowers the Nash product below θ^|T|, while the signature goods’ coverage establishes the matching.Source: F Missing Proofs from Section 5 · pp. 56–57

F.1 Proof of Theorem 7

The proof establishes a 0.9996-inapproximability result for Nash welfare under doubling valuations by reducing gap-4D-matching to a carefully constructed lexicographic instance. The reduction preserves doubling valuations, and a structural analysis separates high-value dummy allocations from signature-good allocations to obtain the welfare gap.

Hardness result

  • Nash welfare is NP-hard to approximate within 0.9996 even for doubling valuations.This is Theorem 7’s hardness guarantee.Source: §F.1 · p. 57

Reduction

  • The reduction maps 4D-matching instances with |Q| = 3n to Nash-welfare instances with one agent per quadruple, producing 3n agents and 9n goods.Source: §F.1 · pp. 57–58

Valuation construction

  • Assigning geometrically decreasing values to insignificant goods makes every constructed valuation lexicographic and doubling, although the instance is not ordered.The insignificant goods have values q/2, q/4, q/8, ... and total value below q.Source: §F.1 · p. 58

Completeness and soundness

  • The completeness case allocates supporting goods broadly and signature goods to matched agents, yielding welfare threshold θ, while the soundness lemma bounds every allocation below 0.9996 × θ.The soundness analysis shows dummy goods cannot be profitably duplicated or combined with other goods, and at most (c + ϵ)n agents can receive all signature goods.Source: §F.1 · pp. 58–59
Loading 2608.24537v1…