论文标题
Yankee交换：一种快速而简单的公平分配机制，用于Matroid排名估值
Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations
论文作者
论文摘要
当代理具有矩形排名估值时，我们研究不可分割的商品的公平分配。我们的主要贡献是一种基于口语的洋基交换程序的简单算法，该程序计算出可证明公平有效的洛伦兹（Lorenz）主导分配。尽管存在多项式时间算法来计算此类分配，但我们提出的方法以两种方式对它们进行了改进。 （a）我们的方法易于理解，并且不使用复杂的曲霉优化算法作为子例程。 （b）我们的方法是可扩展的；事实证明，计算洛伦兹主导分配的所有已知算法要快。这两个属性是在任何真正的公平分配设置中采用算法的关键。我们的贡献使我们更接近这个目标。
We study fair allocation of indivisible goods when agents have matroid rank valuations. Our main contribution is a simple algorithm based on the colloquial Yankee Swap procedure that computes provably fair and efficient Lorenz dominating allocations. While there exist polynomial time algorithms to compute such allocations, our proposed method improves on them in two ways. (a) Our approach is easy to understand and does not use complex matroid optimization algorithms as subroutines. (b) Our approach is scalable; it is provably faster than all known algorithms to compute Lorenz dominating allocations. These two properties are key to the adoption of algorithms in any real fair allocation setting; our contribution brings us one step closer to this goal.
