PaperlayerView exact revision on arXiv

Source-linked AI summary

When Maximum Nash Welfare Becomes Strongly Fair: Bi-valued Goods

Zehan Lin, Xiaowei Wu, Shengwei Zhou

arXiv:2610.00122v1cs.GT

TL;DR

Fair allocation of indivisible goods must balance fairness with efficiency, and the reach of MNW’s strong fairness guarantees beyond binary valuations is not fully characterized. This paper characterizes MNW guarantees for bi-valued instances and examines tri-valued instances, finding strong guarantees in the former and substantial deterioration in the latter.

  • Problem

    The paper investigates how far MNW’s strong fairness guarantees extend beyond binary instances, where its guarantees for general valuations are weaker.

    Source: §1 · p. 2

  • Method

    The paper characterizes MNW fairness guarantees for bi-valued instances and constructs counterexamples to examine tri-valued instances.

    Source: §1.1 · p. 3

  • Results

    Every MNW allocation for personalized bi-valued instances is 2/3-EFX and 2/3-GMMS, while tri-valued instances have no constant-factor EFX guarantee and a GMMS guarantee that vanishes with the number of agents.

    Source: §1.1 · p. 3, §3.1 · p. 7, §3.3 · p. 13

  • Takeaways & Limitations

    Bi-valued structure supports improved approximate fairness guarantees alongside PO, while tri-valued instances mark a boundary where MNW’s fairness guarantees deteriorate.

    Source: §1.1 · p. 3

    The analysis assumes m ≥ n and uses a normalization with b_i > 0; the boundary case b_i = 0 is discussed in Appendix C.

    Source: §3 · p. 6

Abstract

from arXiv · show

For the fair allocation of indivisible goods, the milestone work of Caragiannis et al. (2019) revolutionized the understanding of Maximum Nash Welfare (MNW) allocations by revealing their "unreasonable" ability to balance fairness (EF1) and efficiency (PO) for general additive functions. Subsequent work established that MNW allocations simultaneously satisfy EFX and GMMS (and consequently MMS and PMMS) for binary instances (Amanatidis et al. 2021 and Barman et al. 2018), and satisfy EFX for bi-valued instances (Amanatidis et al. 2021). In this paper, we revisit the (personalized) bi-valued instances and provide a tight characterization of the approximation guarantees of MNW allocations with respect to EFX, PMMS, and GMMS, showing that these guarantees are significantly stronger than what is known for general valuations. Furthermore, we demonstrate that even for the slightly more general setting of tri-valued instances, the fairness guarantees of MNW deteriorate significantly, which establishes a sharp boundary on the instances for which MNW allocations are strongly fair.

1 Introduction

Fair division must balance fairness and Pareto efficiency when allocating indivisible goods, and Maximum Nash Welfare (MNW) is a prominent rule for doing so. This paper characterizes where MNW’s strong fairness guarantees hold across bi-valued instances and where they deteriorate in tri-valued instances.

1 Introduction

  • MNW guarantees EF1 and PO for general additive valuations, has exact EFX and GMMS guarantees for binary valuations, and has an EFX guarantee for bi-valued valuations.The cited prior work describes these as distinct strengths across increasingly broad valuation settings.Source: §1 · p. 2

1.1 Our Contribution

  • For personalized bi-valued instances, MNW guarantees at least 2/3-approximation for EFX, PMMS, and GMMS, and each bound is tight.The results cover personalized, bi-valued, and factored bi-valued settings.Source: §1.1 · p. 3
  • For tri-valued instances, MNW has no constant-factor EFX guarantee and its GMMS guarantee vanishes as the number of agents grows.The authors identify tri-valued instances as the threshold at which these fairness guarantees collapse.Source: §1.1 · p. 3
  • For bi-valued instances, the results improve PMMS from 0.781 to 6/7 and GMMS from 0.618 [11] to 2/3, alongside PO.The authors also establish allocations satisfying the listed approximate fairness guarantees simultaneously with PO.Source: §1.1 · p. 3
  • Leximin’s bi-valued guarantees are 1/k for EFX and GMMS and 2/(k+1) for PMMS, while fixed p ≠ 0 provides no constant approximation for these notions.MNW is equivalent to leximin for binary instances, but their performance diverges for bi-valued instances.Source: §1.1 · p. 3

1.2 Related Work

  • For general additive valuations, EFX existence remains open, and 0.618 is the stated state-of-the-art EFX approximation; restricted classes have additional existence results.The related work also surveys EFX existence results for settings including bi-valued and personalized bi-valued valuations.Source: §1.2 · p. 4
  • Related work records approximation advances for MMS, PMMS, and GMMS and studies the computational hardness and approximation of MNW.Maximizing Nash welfare is APX-hard for additive valuations, motivating approximation algorithms.Source: §1.2 · p. 4

2 Preliminaries

The paper formalizes fair allocation of indivisible goods among agents with additive valuations, using fairness criteria alongside Pareto optimality. It defines MNW as maximizing the product of agents’ bundle values and notes that every MNW allocation is Pareto optimal.

2 Preliminaries

  • An allocation partitions indivisible goods among agents, each with an additive valuation, and the objective is an allocation that is fair and efficient.The paper uses M for the goods, N for the agents, and X_i for agent i’s bundle.Source: §2 · p. 5
  • The preliminaries define EF1, EFX, MMS, PMMS, and GMMS as fairness criteria for allocations.PMMS compares an agent’s value with what she could guarantee by repartitioning a pair’s bundles; GMMS extends the MMS requirement to every subgroup.Source: §2 · p. 5
  • In the approximation regime, PMMS does not imply EFX+, motivating separate characterizations of each fairness notion.For bi-valued instances, EFX and EFX+ are equivalent.Source: §2 · p. 5
  • Pareto optimality requires that no other allocation can improve one agent’s utility without reducing another’s.The paper treats PO as its efficiency benchmark.Source: §2 · p. 6
  • MNW maximizes the product of agents’ bundle values, and every MNW allocation is Pareto optimal.The paper studies the fairness guarantees of an arbitrarily fixed MNW allocation.Source: §2 · p. 6

3 Fairness Guarantee for EFX and GMMS

This section analyzes fairness guarantees for personalized bi-valued instances, establishing tight 2/3 guarantees for MNW allocations with respect to EFX and GMMS. It also derives a 2/3-MMS guarantee from an EFX-based value bound and shows that every EFX allocation is tightly 2/3-GMMS.

3 Fairness Guarantee for EFX and GMMS

  • MNW allocations retain a 2/3-GMMS guarantee for personalized bi-valued instances even though they do not guarantee EFX there.For (factored) bi-valued instances, MNW allocations are EFX, which implies the 2/3-GMMS guarantee.Source: §3 · p. 7

3.1 EFX Guarantee for Personalized Bi-valued Instances

  • Every MNW allocation for personalized bi-valued instances is 2/3-EFX, and this approximation guarantee is tight.The result characterizes the approximation guarantee even though MNW allocations need not be EFX in personalized bi-valued instances.Source: §3.1 · p. 7, §3 · p. 7

3.2 Implication of EFX to Approximate GMMS

  • Every EFX allocation for personalized bi-valued instances is tightly 2/3-GMMS.This improves on the 10/17-GMMS guarantee for general additive valuations [57]; EFX and 2/3-GMMS allocations can be computed efficiently using existing algorithms (Jin and Tao [47]; Byrka et al. [22]).Source: §3.2 · p. 10
  • The EFX analysis proves (3/2)v(X_i) ≥ max{k + t, 2t + 1} and MMS ≤ max{k + t, 2t + 1}, yielding v(X_i) ≥ 2/3 MMS.Source: §3.2 · pp. 12–13

3.3 GMMS Guarantee for Personalized Bi-valued Instances

  • Because MNW allocations need not be EFX, the proof replaces EFX steps with EF1 and MNW-optimality arguments to recover the same approximation guarantee.In particular, MNW optimality rules out small items in bundles with two large items when k ≤ v_i(X_i) < 2k.Source: §3.3 · pp. 13–16
  • Every MNW allocation for personalized bi-valued instances is 2/3-GMMS, and this approximation guarantee is tight.Source: §3.3 · p. 13
  • When v_i(X_i) < k, the MNW allocation gives agent i at least MMS_i; when k ≤ v_i(X_i) < 2k, bundles with two large items contain no small items.Source: §3.3 · pp. 14–15

4 Fairness Guarantee for PMMS

MNW’s PMMS guarantee is tight at 1 for factored bi-valued instances, 6/7 for bi-valued instances, and 2/3 for personalized bi-valued instances. The proofs distinguish these settings, and the factored guarantee also yields an efficiently computable allocation satisfying several fairness and efficiency guarantees.

4 Fairness Guarantee for PMMS

  • For non-factored bi-valued instances, the analysis uses EFX to bound bundle-value differences, but yields only a tight 6/7-PMMS guarantee.The proof roadmap contrasts this with factored instances, where integrality allows a 1-PMMS guarantee.Source: §4 · pp. 16, 19
  • MNW is 1-PMMS for factored bi-valued instances and 6/7-PMMS for non-factored bi-valued instances; for any bi-valued instance, 6/7-PMMS is tight, while personalized bi-valued instances have a tight 2/3-PMMS guarantee.Source: §4 · pp. 17, 19
  • For factored bi-valued instances, every MNW allocation is PMMS, and an allocation satisfying EFX, PMMS, 2/3-GMMS, and PO can be computed efficiently.The computational guarantee combines the PMMS result with a polynomial-time algorithm for computing MNW in this setting.Source: §4 · pp. 17–18
  • For non-factored instances, a two-agent example has v1(X1) = 3 and MMS1(X1 ∪ X2, 2) = 3.5, establishing the 6/7 upper bound.The example illustrates why the factored-instance guarantee does not carry over unchanged.Source: §4 · p. 18
  • In personalized bi-valued instances, MNW guarantees only tight 2/3-PMMS; the example shows the non-personalized proof step can fail even when the other bundle’s items are large.The example has v1(X1) = 2 while MMS1(X1 ∪ X2, 2) = 3.Source: §4 · p. 19

5 Upper Bounds for Tri-valued Instances

The section constructs tri-valued instances showing that MNW loses strong fairness guarantees. In particular, it provides no constant-factor EFX guarantee and gives an upper bound for MMS matching the general-instance limitation.

5 Upper Bounds for Tri-valued Instances

  • MNW fails to provide any constant-factor approximation guarantee for EFX on a tri-valued instance.The construction uses three values, whereas the earlier construction it matches used five [8].Source: §5 · p. 20
  • The MMS witness uses n agents and 2n − 1 goods, with item values drawn from {1/k, 1, k}; its MNW allocation gives agent 1 an MMS value of k.The construction assigns x to agent 1 and pairs each other agent’s large and small items in the proposed allocation.Source: §5 · p. 20
  • The tri-valued construction bounds MNW’s MMS approximation ratio by 2/(1 + √4n −3).For two agents, the section notes that PMMS and MMS are equivalent and derives an upper bound of approximately 0.618 for PMMS.Source: §5 · p. 20
  • For tri-valued instances, MNW’s approximation guarantees for EFX, MMS, and PMMS coincide with those established for general instances.The proof strategy adapts a construction of Caragiannis et al. for the MMS upper bound.Source: §5 · p. 20

6 Conclusion and Open Problems

The paper characterizes MNW fairness guarantees across bi-valued and tri-valued instances, identifying a sharp boundary between the stronger bi-valued results and general-setting limitations. It also points to computation of allocations satisfying strengthened guarantees as a next step.

6 Conclusion and Open Problems

  • The paper identifies a sharp contrast: tri-valued instances have general-setting limitations, while bi-valued instances admit tight characterizations for EFX, PMMS, and GMMS.The comparison with leximin and maximum p-mean welfare for p ≤ 1 and p ≠ 0 indicates that these guarantees do not automatically extend to nearby egalitarian objectives.Source: §6 · p. 21
  • A natural next step is finding allocations that simultaneously satisfy the strengthened EFX, GMMS, and PMMS guarantees, with or without PO.Source: §6 · p. 21

Declaration on the Use of Generative AI

The authors state that the paper’s research ideas, formulations, and mathematical results originated with them and that they independently verified the manuscript’s technical claims.

Declaration on the Use of Generative AI

A Leximin Allocations for Bi-valued Instances

For factored bi-valued instances, leximin allocations have tight but weakening fairness guarantees as k grows, unlike the strong guarantees provided by MNW.

A.1 Fairness Guarantee for EFX

For factored bi-valued instances, leximin’s EFX approximation is exactly 1/k; the proof combines a tight example with a structural bound on bundle sizes.

  • Every leximin allocation is 1/k-EFX for factored bi-valued instances, and this guarantee is tight.Source: §A.1 · p. 25
  • With two agents valuing every item at 1 and k respectively, a leximin allocation gives each utility tk yet achieves only a 1/k-scale EFX ratio.The instance has m = t(k + 1) items; Table 9 is identified as the hard instance for leximin EFX.Source: §A.1 · p. 25, Table 9 · p. 25
  • In any leximin allocation, each agent’s bundle contains at most t + 1 items, where t is the minimum utility across agents.The observation follows because moving an item from a larger bundle to a minimum-utility agent would otherwise improve both utilities.Source: §A.1 · p. 25

A.2 Fairness Guarantee for GMMS

For factored bi-valued instances, leximin guarantees a tight 1/k approximation to GMMS, with the proof reducing the lower bound to MMS.

  • Every leximin allocation is 1/k-GMMS for factored bi-valued instances, and the guarantee is tight.Source: §A.2 · p. 26
  • Leximin remains optimal when restricted to subsets of agents, so proving a 1/k-MMS guarantee suffices to establish 1/k-GMMS.Source: §A.2 · p. 26
  • A hard instance with n agents and m = n + kn(n − 1) items gives agent n an MMS ratio of n/[1 + k(n − 1)], limiting guarantees to 1/k.Source: §A.2 · p. 26

A.3 Fairness Guarantee for PMMS

For factored bi-valued instances, leximin’s PMMS approximation is tightly 2/(k + 1), supported by a matching hard instance and a lower-bound argument.

  • Every leximin allocation is 2/(k + 1)-PMMS for factored bi-valued instances, and this guarantee is tight.Source: §A.3 · p. 26
  • The GMMS hard instance with n = 2 also gives a PMMS ratio of 2/(k + 1) for agent 2.Table 11 is identified as the hard instance for leximin PMMS.Source: §A.3 · p. 26, Table 11 · p. 26
  • For any two agents, the lower-bound proof shows vi(Xj) ≤ k · vi(Xi), which suffices to obtain the 2/(k + 1)-PMMS guarantee.Source: §A.3 · p. 27

B Maximum p-Mean Welfare for Bi-valued Instances

For every fixed p ≤ 1 with p ≠ 0, maximum p-mean welfare allocations on factored bi-valued instances lack any positive constant approximation guarantee for EFX, PMMS, and GMMS. The proof constructs instances with arbitrarily poor ratios, including zero ratios when p = 1.

B Maximum p-Mean Welfare for Bi-valued Instances

  • For every fixed p ≤ 1 with p ≠ 0, maximum p-mean welfare gives no positive constant approximation guarantee for EFX, PMMS, or GMMS, even on factored bi-valued instances.The proof obtains ratios below any chosen ϵ ∈ (0, 1) for p < 1 and zero ratios for p = 1.Source: B Maximum p-Mean Welfare for Bi-valued… · pp. 27, 29
  • The theorem excludes p = 0, which the paper identifies with maximum Nash welfare allocations.The negative result applies to nonzero p; p = 0 is the standard convention for MNW.Source: B Maximum p-Mean Welfare for Bi-valued… · p. 27
  • For p < 1, a two-agent instance with m identical items valued at 1 by agent 1 and k by agent 2 yields ratios below any chosen ϵ.The allocation is characterized by the number x of items given to agent 1; the maximizing allocation's x′ is within 1 of the unique optimizer x∗, enabling the ratio bounds.Source: B Maximum p-Mean Welfare for Bi-valued… · pp. 27–29
  • At p = 1, the welfare objective is uniquely maximized by giving all items to agent 2, leaving agent 1 with zero EFX, PMMS, and GMMS approximation ratios.The instance has two agents, with every item valued at 1 by agent 1 and k by agent 2.Source: B Maximum p-Mean Welfare for Bi-valued… · p. 29

C Discussion of Personalized Instances with bi = 0

For personalized instances, agents with b_i = 0 are normalized to binary valuations, so their GMMS guarantee follows from MNW's EF1 property. The discussion then establishes EFX for pairs involving such agents using two cases.

C Discussion of Personalized Instances with bi = 0

  • For agents with b_i = 0, binary normalization and MNW's EF1 property imply that the agent receives her GMMS guarantee.The analysis therefore focuses on EFX for these personalized instances.Source: C Discussion of Personalized Instances… · p. 29
  • When b_i = 0, assuming EFX failure contradicts Lemma 3.3's bound on the value of agent j's bundle.EF1 implies v_i(X_j) = v_i(X_i) + 1; the proof uses the items valued at 1 by i to derive the contradiction.Source: C Discussion of Personalized Instances… · p. 29
  • When b_i > 0 but b_j = 0, Lemma 3.3 bounds i's value after removing any item from X_j by i's own bundle value, establishing EFX.The argument uses v_i(X_i) ≥ k_i · (v_j(X_j) − 1).Source: C Discussion of Personalized Instances… · p. 29

Related papers

Loading 2610.00122v1…