Fair Division via Quantile Shares

本文研究的是公平分配问题，即如何在一个有限的不可分割物品集合中，将这些物品公平地分配给一组有组合估值的代理人。为了捕捉公平性，作者采用了“份额”的概念，即每个代理人都有权获得一个公平的份额，基于某种公平标准，如果分配的价值(弱)超过她的公平份额，则认为是公平的。如果一个基于份额的概念被认为是普遍可行的，那么它就能够适用于所有单调估值的情况下，实现公平分配。一个重要的问题是：是否存在一个非平凡的基于份额的概念，它是普遍可行的？最为人熟知的基于份额的概念，即比例和最大最小份额，都不是普遍可行的，也没有任何常数逼近它们。 作者提出了一种新的份额概念，其中一个代理人通过将其与随机分配中的估值进行比较来评估一个捆绑的公平性。在这个框架下，如果一个捆绑至少与一个在随机分配中以概率至少为$q$获得的捆绑一样好，那么它被认为是$q$-分位公平。作者的主要问题是是否存在一个常数值$q$，使得$q$-分位份额是普遍可行的。 作者的主要结果建立在分位份额的可行性和经典的Erdős匹配猜想之间的强联系上。具体而言，如果这个猜想的一个版本是正确的，那么$\frac{1}{2e}$分位份额是普遍可行的。此外，对于常数值的$q$，我们还提供了加性、单位需求和拟阵秩估值的无条件可行性结果。最后，我们还讨论了我们的结果对其他份额概念的影响。

本论文试图解决公平分配问题，即如何在具有组合估值的代理人集合中公平地分配不可分割的商品。论文提出了一种新的股份概念，即q-分位数股份，以解决传统股份概念无法普适的问题。

论文提出了一种新的股份概念，即q-分位数股份，其中代理人通过将其分配与随机分配进行比较来评估其公平性。论文还证明了当Erdős匹配猜想成立时，q取1/2e时，q-分位数股份是普适的。此外，论文还对加性、单元需求和拟阵-秩估值提出了无条件的普适性结果。

论文的亮点在于提出了一种新的股份概念以解决传统股份概念无法普适的问题，并且将其与Erdős匹配猜想联系起来。此外，论文还提供了对加性、单元需求和拟阵-秩估值的无条件普适性结果。

最近在这个领域中，还有一些相关的研究，如“Proportionality, Efficiency, and Envy-Freeness in Cake Cutting”和“Fair Allocation without Trade”.