论文标题
近似和策略范围的最大值共享杂务的分配
Approximate and Strategyproof Maximin Share Allocation of Chores with Ordinal Preferences
论文作者
论文摘要
我们从算法和机理设计的角度使用其序式偏好，仅使用其序偏见对n个代理进行M Maximin共享（MMS）公平分配的工作。先前最著名的近似值为2-1/n，Aziz等人。 [IJCAI 2017]。我们通过给出一个简单的确定性5/3-辅助算法来改善该结果，该算法确定了代理的分配顺序，根据哪些项目被一个一个一个分配。通过更严格的分析，我们表明，对于n = 2,3，我们的算法实现了更好的近似值，实际上是最佳的。我们还考虑了战略代理商的设置，在这种情况下，代理商可能会误导他们操纵结果的偏好。我们首先提供O（\ log（m/n）） - 近似连续的选择算法，然后通过随机算法提高近似值与O（\ sqrt {\ log n}）。我们的结果发现了琐事与商品的近似比之间的一些有趣的对比。
We initiate the work on maximin share (MMS) fair allocation of m indivisible chores to n agents using only their ordinal preferences, from both algorithmic and mechanism design perspectives. The previous best-known approximation is 2-1/n by Aziz et al. [IJCAI 2017]. We improve this result by giving a simple deterministic 5/3-approximation algorithm that determines an allocation sequence of agents, according to which items are allocated one by one. By a tighter analysis, we show that for n=2,3, our algorithm achieves better approximation ratios, and is actually optimal. We also consider the setting with strategic agents, where agents may misreport their preferences to manipulate the outcome. We first provide a O(\log (m/n))-approximation consecutive picking algorithm, and then improve the approximation ratio to O(\sqrt{\log n}) by a randomized algorithm. Our results uncover some interesting contrasts between the approximation ratios achieved for chores versus goods.
