论文标题
与比例保证的预算建议的真实汇总
Truthful Aggregation of Budget Proposals with Proportionality Guarantees
论文作者
论文摘要
我们研究了一个参与性的预算问题，其中一组战略代理希望通过将其提案汇总在一个部门上，以将可分裂的预算分开。不幸的是，将预算分配的直截了当规则比例地易受操纵。在最近的作品中，Freeman等人。 [ARXIV：1905.00457]提出了一类真实的机制，称为移动幻影机制。除其他外，他们提出了一种比例机制，从某种意义上说，在极端情况下，所有代理人都倾向于单个项目接受全部数量，预算是按比例分配的。虽然比例性是一种自然期望的属性，但它是在有限类型的偏好概况上定义的。为了解决这个问题，我们通过提出一个定量框架来扩展相称的概念，该框架根据其与比例分配的最差距离评估预算聚合机制。至关重要的是，这是针对每个首选项概况的定义。我们研究了移动幻影机制类别的措施，并提供近似保证。对于两个项目，我们表明统一的幻影机制是所有真实机制中的最佳选择。对于三个项目，我们提出了一种新的比例机制，在所有移动的幻影机制中实际上是最佳的。最后，我们为移动幻象机制的近似性提供了不可能的结果。
We study a participatory budgeting problem, where a set of strategic agents wish to split a divisible budget among different projects, by aggregating their proposals on a single division. Unfortunately, the straight-forward rule that divides the budget proportionally is susceptible to manipulation. In a recent work, Freeman et al. [arXiv:1905.00457] proposed a class of truthful mechanisms, called moving phantom mechanisms. Among others, they propose a proportional mechanism, in the sense that in the extreme case where all agents prefer a single project to receive the whole amount, the budget is assigned proportionally. While proportionality is a naturally desired property, it is defined over a limited type of preference profiles. To address this, we expand the notion of proportionality, by proposing a quantitative framework which evaluates a budget aggregation mechanism according to its worst-case distance from the proportional allocation. Crucially, this is defined for every preference profile. We study this measure on the class of moving phantom mechanisms, and we provide approximation guarantees. For two projects, we show that the Uniform Phantom mechanism is the optimal among all truthful mechanisms. For three projects, we propose a new, proportional mechanism which is virtually optimal among all moving phantom mechanisms. Finally, we provide impossibility results regarding the approximability of moving phantom mechanisms.
