论文标题
最大值公平，混合可划分和不可分割的商品
Maximin Fairness with Mixed Divisible and Indivisible Goods
论文作者
论文摘要
当资源包含可分割和不可分割的商品的混合时，我们研究公平的资源分配，重点是研究最大的公平性公平概念（MMS）。只有不可分割的商品，可能不存在完整的MMS分配，但是持续的乘法近似分配总是可以的。我们分析当要分配的资源还包含可划分的商品时，MMS近似保证将如何影响。特别是，我们表明，使用混合商品的最差案例MMS近似保证并不比不可分割的商品差。但是，存在添加一些可分割资源的问题实例严格降低了实例的MMS近似比。在算法方面，我们提出了一种建设性算法，该算法始终为任何数量的代理产生$α$ -MMS的分配，其中$α$的值在$ 1/2 $和$ 1 $之间的值，并且是单调的增加功能，由代理人对其MMS价值相对的分配商品的价值确定。
We study fair resource allocation when the resources contain a mixture of divisible and indivisible goods, focusing on the well-studied fairness notion of maximin share fairness (MMS). With only indivisible goods, a full MMS allocation may not exist, but a constant multiplicative approximate allocation always does. We analyze how the MMS approximation guarantee would be affected when the resources to be allocated also contain divisible goods. In particular, we show that the worst-case MMS approximation guarantee with mixed goods is no worse than that with only indivisible goods. However, there exist problem instances to which adding some divisible resources would strictly decrease the MMS approximation ratio of the instance. On the algorithmic front, we propose a constructive algorithm that will always produce an $α$-MMS allocation for any number of agents, where $α$ takes values between $1/2$ and $1$ and is a monotone increasing function determined by how agents value the divisible goods relative to their MMS values.
