# Nash Welfare Guarantees for Fair and Efficient Coverage

arXiv: https://arxiv.org/abs/2207.01970 · HTML: https://mlsanity.com/paper/2207.01970/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jul 2022.

## Built on by (most cited first, 1 of 1)

- [Fair Stable Matching: A Nash Social Welfare Approach](https://mlsanity.com/paper/2609.02354/) (2026)

## Abstract (arXiv)

We study coverage problems in which, for a set of agents and a given threshold T, the goal is to select T subsets (of the agents) that, while satisfying combinatorial constraints, achieve fair and efficient coverage among the agents. In this setting, the valuation of each agent is equated to the number of selected subsets that contain it, plus one. The current work utilizes the Nash social welfare function to quantify the extent of fairness and collective efficiency. We develop a polynomial-time left(18 + o(1) right)-approximation algorithm for maximizing Nash social welfare in coverage instances. Our algorithm applies to all instances wherein, for the underlying combinatorial constraints, there exists an FPTAS for weight maximization. We complement the algorithmic result by proving that Nash social welfare maximization is APX-hard in coverage instances.