论文标题
计算有限补贴的可羡慕分配的分配
Computing envy-freeable allocations with limited subsidies
论文作者
论文摘要
公平的划分已成为多种系统中非常热门的话题，而嫉妒是最引人注目的公平概念之一。如果没有代理商在价值方面不喜欢任何其他代理商的捆绑，则不可分割的项目分配不可分割的物品是嫉妒的。由于嫉妒的柔和很少是一个可行的目标，因此最近关注放松其定义。在这个方向上的一种方法是补充给代理商的付款（或补贴）。然后，一个可行的目标是根据代理商从分配和补贴中获得的总价值来实现嫉妒性。 我们考虑使用最低补贴量的计算分配的自然优化问题。由于问题是NP-HARD，因此我们专注于近似算法的设计。在正面，我们提出了一种算法，该算法对于恒定数量的代理，在任何必需的准确性中近似最低补贴量，而牺牲了运行时间优雅的增加。在负面的一面，我们表明，对于超常见的代理人，最大程度地减少嫉妒的补贴的问题不仅很难准确地计算（如民俗论点所示），而且更重要的是，很难近似。
Fair division has emerged as a very hot topic in multiagent systems, and envy-freeness is among the most compelling fairness concepts. An allocation of indivisible items to agents is envy-free if no agent prefers the bundle of any other agent to his own in terms of value. As envy-freeness is rarely a feasible goal, there is a recent focus on relaxations of its definition. An approach in this direction is to complement allocations with payments (or subsidies) to the agents. A feasible goal then is to achieve envy-freeness in terms of the total value an agent gets from the allocation and the subsidies. We consider the natural optimization problem of computing allocations that are {\em envy-freeable} using the minimum amount of subsidies. As the problem is NP-hard, we focus on the design of approximation algorithms. On the positive side, we present an algorithm that, for a constant number of agents, approximates the minimum amount of subsidies within any required accuracy, at the expense of a graceful increase in the running time. On the negative side, we show that, for a super-constant number of agents, the problem of minimizing subsidies for envy-freeness is not only hard to compute exactly (as a folklore argument shows) but also, more importantly, hard to approximate.
