论文标题
通过最佳运输来实现最佳效率的权衡
Optimal Efficiency-Envy Trade-Off via Optimal Transport
论文作者
论文摘要
我们考虑将项目分配给$ n $接收者的问题，在这些问题中，每个收件人都必须分配固定的所有项目的预先指定的部分，同时确保每个收件人都不会感到太羡慕。我们表明，这个问题可以作为半污垢最佳传输（OT）问题的变体进行表述，在这种情况下，其解决方案结构具有简洁的表示和简单的几何解释。与现有的文献将嫉妒性视为严格的约束不同，我们的表述使我们能够\ emph {optim}以不断地进行效率和嫉妒。此外，我们通过显示出近似样品中最佳解决方案所需的样品数量的多项式结合来研究基于OT的分配策略空间的统计特性。我们的方法适用于大规模的公平分配问题，例如献血匹配问题，我们从数值上表明，它在先前的现实数据模拟器上表现良好。
We consider the problem of allocating a distribution of items to $n$ recipients where each recipient has to be allocated a fixed, prespecified fraction of all items, while ensuring that each recipient does not experience too much envy. We show that this problem can be formulated as a variant of the semi-discrete optimal transport (OT) problem, whose solution structure in this case has a concise representation and a simple geometric interpretation. Unlike existing literature that treats envy-freeness as a hard constraint, our formulation allows us to \emph{optimally} trade off efficiency and envy continuously. Additionally, we study the statistical properties of the space of our OT based allocation policies by showing a polynomial bound on the number of samples needed to approximate the optimal solution from samples. Our approach is suitable for large-scale fair allocation problems such as the blood donation matching problem, and we show numerically that it performs well on a prior realistic data simulator.
