Budget-feasible Maximum Nash Social Welfare is Almost Envy-free

Xiaowei Wu, Bo Li, Jiarui Gan

Abstract

In standard fair division, maximizing Nash Social Welfare (NSW) yields allocations that are "envy-free up to one item" (EF1). This paper examines whether this property persists under budget constraints. We prove that budget-feasible Max-NSW allocations are 1/4-EF1 and Pareto Optimal. Furthermore, we show that this fairness guarantee improves toward 1/2-EF1 as the budget-to-cost ratio increases.

Introduction

Fair division of indivisible goods often relies on the Maximum Nash Social Welfare (Max-NSW) objective, which maximizes the product of agents' utilities. In unconstrained settings, Max-NSW is famously Envy-Free up to one item (EF1). However, real-world applications—such as task assignment with time constraints—introduce budgets. When an agent cannot afford another's bundle, the standard EF1 guarantee may fail. This research investigates the robustness of NSW's fairness properties in the presence of such budget constraints.

Methodology

The authors model the problem using a set of items with costs $c_j$ and agents with budgets $B_i$. An allocation is feasible only if the total cost of items assigned to an agent does not exceed their budget. To handle unallocated items, a "charity agent" is introduced—a dummy entity that receives items without generating envy or contributing to the welfare product.

The core results are derived through contradiction proofs using reallocation arguments. By assuming an allocation is not 1/4-EF1, the authors demonstrate that items can be shifted to increase the total NSW, contradicting the optimality of the original allocation. For asymptotic results, they analyze the "density" (value-to-cost ratio) of items relative to the total budget.

Key Results

The 1/4-EF1 Bound and Tightness

The primary finding is that every budget-feasible Max-NSW allocation is 1/4-EF1 and Pareto Optimal. This means that for any two agents $i$ and $k$, agent $i$’s utility is at least $1/4$ of their utility for agent $k$’s bundle after removing one item.

The authors prove that this 1/4 bound is tight. For any constant $c > 1/4$, there exists an instance where Max-NSW fails to be $c$-EF1.

Table 1: Instance demonstrating the tightness of the 1/4-EF1 bound.

In the example shown in Table 1, as $\epsilon \to 0$, the ratio of utilities in the Max-NSW allocation approaches 1/4, confirming that no higher constant guarantee is possible for all instances.

Asymptotic Improvement with Large Budgets

When items are small relative to the total budget (a high budget-to-cost ratio $\kappa$), the fairness guarantee improves. The authors show that the ratio converges to 1/2-EF1 as $\kappa \to \infty$.

Table 2: Instance used to analyze the large budget-to-cost ratio case.

Specifically, the fairness ratio is bounded by $(\frac{1}{2} - \frac{5}{\kappa^{1/4}})$. Table 2 illustrates the type of structured instances used to explore these asymptotic properties.

Discussion

While this work establishes a robust floor for fairness in budget-constrained NSW, several questions remain. It is currently unknown if an exact EF1 (1-EF1) budget-feasible allocation always exists, even if Max-NSW does not find it. Additionally, while the properties of the optimal solution are now better understood, computing the Max-NSW allocation remains APX-hard. Future research could extend these findings to more complex valuation functions, such as submodular or XOS preferences, or explore other fairness metrics like maximin share fairness.

Summary updated

Abstract

The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivisible goods, it has been shown by Caragiannis et al. (EC 2016 and TEAC 2019) that an allocation maximizing the NSW is envy-free up to one good (EF1). In this paper, we are interested in the fairness of the NSW in a budget-feasible allocation problem, in which each item has a cost that will be incurred to the agent it is allocated to, and each agent has a budget constraint on the total cost of items she receives. We show that a budget-feasible allocation that maximizes the NSW achieves a 1/4-approximation of EF1 and the approximation ratio is tight. The approximation ratio improves gracefully when the items have small costs compared with the agents' budgets; it converges to 1/2 when the budget-cost ratio approaches infinity.
BibTeX
@inproceedings{wu2021budget,
  author = {Xiaowei Wu and Bo Li and Jiarui Gan},
  title = {{Budget-feasible Maximum Nash Social Welfare is Almost Envy-free}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/65},
}
Figure