Asymptotically Fair and Truthful Allocation of Public Goods

我们研究了在n个具有不同物品偏好的代理人之间公平诚实地分配m个可分割公共物品的问题。为了公平地汇总代理人的偏好，我们遵循公共物品公平分配的文献，并旨在找到核心解决方案。对于可分割的物品，核心解决方案总是存在的，并且可以通过最大化Nash福利目标来高效地计算。然而，这种解决方案很容易被操纵；代理人可能会有操纵其偏好的动机。为了缓解这个问题，目前的最新技术在保证近似真实性的同时，以高概率找到近似核心解决方案。然而，这种方法有两个主要局限性。首先，由于几个近似，核心的近似误差可能随着n的增加而增加，导致非渐近核心解决方案。这个限制在公共物品分配机制经常应用于涉及大量代理人的场景中，例如分配市政项目的公共税款时，特别重要。其次，实施当前方法的实际应用被证明是一个非常棘手的任务。为了解决这些局限性，我们引入了PPGA，一种（差分）私有公共物品分配算法，并表明它具有渐近真实性，并以高概率找到渐近核心解决方案。此外，为了展示我们算法的实际适用性，我们实施了PPGA，并使用市政预算数据进行了实证研究。

解决公共物品分配问题中的真实性和公平性问题，特别是在涉及大量代理人的实际应用中。

提出了一个新的算法PPGA，它能够在保证差分隐私的同时，找到一个渐进真实和渐进核心解的高概率算法。

论文实现了PPGA算法，并使用市政预算数据进行了实验研究。该算法具有较高的实用性和可扩展性，可以应用于实际的公共物品分配问题中。

与此相关的研究包括公共物品分配领域的其他算法，以及与隐私保护相关的研究。例如，Efficient and Strategyproof Mechanisms for Public Project Allocation with Single-Dimensional Types和Differentially Private Truthful Mechanisms for Combinatorial Auctions。