论文标题
在线公平部门中最有竞争力的机制
Most Competitive Mechanisms in Online Fair Division
论文作者
论文摘要
本文结合了在线算法的两种关键要素 - 竞争分析（例如竞争比率）和建议复杂性（例如，改善在线决策所需的建议位数） - 在一个简单的在线公平部门模型的背景下，项目一一一个人到达，并通过某种机制分配给代理。我们考虑了四种这样的在线机制：根据在线双方匹配等适用于在线公平分区问题首先引入的流行排名匹配机制。我们的第一个贡献是，我们对匹配，功利主义福利和平等福利的预期规模进行了这些机制进行竞争分析。我们还假设甲骨文可以为机制提供许多建议部分。我们的第二个贡献是给出一些不可能的结果。例如没有任何机制可以实现最佳离线机制的平均成果，认为它们会从Oracle那里获得部分建议。我们的第三个贡献是，我们量化了W.R.T.这四种机制的竞争性能。他们可以提出的甲骨文请求数量。因此，我们为每个目标提供了最竞争的机制。
This paper combines two key ingredients for online algorithms - competitive analysis (e.g. the competitive ratio) and advice complexity (e.g. the number of advice bits needed to improve online decisions) - in the context of a simple online fair division model where items arrive one by one and are allocated to agents via some mechanism. We consider four such online mechanisms: the popular Ranking matching mechanism adapted from online bipartite matching and the Like, Balanced Like and Maximum Like allocation mechanisms firstly introduced for online fair division problems. Our first contribution is that we perform a competitive analysis of these mechanisms with respect to the expected size of the matching, the utilitarian welfare, and the egalitarian welfare. We also suppose that an oracle can give a number of advice bits to the mechanisms. Our second contribution is to give several impossibility results; e.g. no mechanism can achieve the egalitarian outcome of the optimal offline mechanism supposing they receive partial advice from the oracle. Our third contribution is that we quantify the competitive performance of these four mechanisms w.r.t. the number of oracle requests they can make. We thus present a most-competitive mechanism for each objective.
