论文标题
纳什福利保证公平有效的覆盖范围
Nash Welfare Guarantees for Fair and Efficient Coverage
论文作者
论文摘要
我们研究了覆盖范围问题，在这些问题中，对于一组代理商和给定的阈值$ t $，目标是选择$ t $ subset（代理的），在满足组合限制的同时，在代理之间实现公平有效的覆盖范围。在这种情况下，每个代理的估值等同于包含它的选定子集的数量，再加上一个。当前的工作利用NASH的社会福利职能来量化公平性和集体效率的程度。我们开发了一个多项式时间$ \ left（18 + o（1）\右）$ - 近似算法，以最大程度地提高NASH社交福利。我们的算法适用于所有实例，其中，对于基本的组合约束，存在着最大化的FPTA。我们通过证明NASH的社会福利最大化在覆盖范围实例中是APX，我们对算法结果进行了补充。
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.
