论文标题
综合的序数最大值共享近似
Ordinal Maximin Share Approximation for Chores
论文作者
论文摘要
我们研究了将一组不可分割的杂务（具有非阳性价值的项目）分配给n个药物的问题。我们考虑了D-D最大蛋白份额（MMS）的理想公平概念 - 代理可以通过将项目划分为D捆绑包并收到价值最低的捆绑包来保证的最低价值 - 并关注旨在找到最大的D <= n的MMS的序数近似值，而其中1-out-D-D-D MMS分配存在。我们的主要贡献是用于1层（2N/3）MMS分配的多项式时间算法，以及一个杂马分配的1层（3N/4）MMS分配的证明。此外，我们展示了如何使用最近开发的算法进行bin包装，以近似后者在多项式时间内绑定到对数因子。
We study the problem of fairly allocating a set of m indivisible chores (items with non-positive value) to n agents. We consider the desirable fairness notion of 1-out-of-d maximin share (MMS) -- the minimum value that an agent can guarantee by partitioning items into d bundles and receiving the least valued bundle -- and focus on ordinal approximation of MMS that aims at finding the largest d <= n for which 1-out-of-d MMS allocation exists. Our main contribution is a polynomial-time algorithm for 1-out-of-floor(2n/3) MMS allocation, and a proof of existence of 1-out-of-floor(3n/4) MMS allocation of chores. Furthermore, we show how to use recently-developed algorithms for bin-packing to approximate the latter bound up to a logarithmic factor in polynomial time.
