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.
翻译:我们研究的是覆盖问题,即对于一组代理人和一个给定的门槛美元T美元,目标是选择(代理人的)美元子集,在满足组合制约的同时,在代理人之间实现公平和高效的覆盖;在这一背景下,每个代理人的估值等于包含该子集的选定子集的数量,加上一个。目前的工作利用纳什社会福利功能来量化公平和集体效率的程度。我们为在覆盖的情况下尽量扩大纳什社会福利,制定了一个多元时间-左(18+o(1)\right)美元-准值的计算法。我们的算法适用于所有情况下,对于潜在的组合制约,存在着一个最大重量的FPTAS。我们通过证明纳什社会福利最大化在覆盖情况下是硬的APX来补充算法结果。