Budget-Feasible Maximum Nash Social Welfare Is Almost Envy-Free.pdf

Problem Setup:

Each agent has a budget B.
Each item has a cost c.
An allocation is budget-feasible if the total cost allocated to each agent stays below their budget.
Max-NSW aims to maximize the product of individual utilities (values) for each agent from their allocated items.

Main Findings:

1. 1/4-Approximation of Envy-Free (EF1): A budget-feasible Max-NSW allocation achieves a 1/4 approximation of EF1, meaning no agent envies another's bundle by more than one item. This ratio is tight and cannot be improved.

2. Improving Approximation with Larger Budgets: The approximation ratio gracefully improves as the budget-to-cost ratio (κ) increases, reaching a 1/2 approximation when κ goes to infinity.

Technical Contributions:

The authors develop new techniques distinct from previous work on EF1 guarantees for Max-NSW without budget constraints. They address the challenges posed by budgeted allocations, where:

Reallocating items to improve NSW must respect budget limits.
Discarding items during reallocation is necessary.

Significance:

This work bridges the gap between fairness and efficiency in resource allocation problems with budget constraints. It highlights the trade-off between achieving near-perfect envy-free allocations (1/4 approximation) and maximizing overall social welfare, offering valuable insights for designing fair and efficient systems in practice.