Nash welfare guarantees for fair and efficient coverage

DOI10.1007/978-3-031-22832-2_15MaRDI QIDQ6167253zbMATH OpenOpenAlexFDO

Authors Siddharth Barman, Anand Krishna, Y. Narahari, Soumyarup Sadhukhan

Publication date 4 August 2023

Published in Web and Internet Economics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.01970, https://eprints.iisc.ac.in/79651/1/WINE_2022.pdf

Mathematics Subject Classification ID

Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: 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)ight)$-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.

Recommendations

• Approximating Nash social welfare under binary XOS and binary subadditive valuations
• Improving Nash social welfare approximations of indivisible goods
• On fair division for indivisible items
• Fair Division of Indivisible Goods for a Class of Concave Valuations
• Nash social welfare, matrix permanent, and stable polynomials

Cites work

• A threshold of ln n for approximating set cover
• Almost envy-free repeated matching in two-sided markets
• Approximation algorithms for NP-hard problems.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Fair division with binary valuations: one rule to rule them all
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• Nash welfare guarantees for fair and efficient coverage

Cited in

(2)

• Nash welfare guarantees for fair and efficient coverage
• Approximating Nash social welfare by matching and local search

This page was built for publication: Nash welfare guarantees for fair and efficient coverage

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6167253)