论文标题
公平分享：可行性，统治和激励措施
Fair Shares: Feasibility, Domination and Incentives
论文作者
论文摘要
我们考虑将$ m $不可分化的商品分配给$ n $同样输入的代理商，没有货币转移。每个代理$ i $都有来自某些给定类别的估值功能的评估$ v_i $。共享$ s $是将一对$（v_i，n）$映射到一个值的函数，并解释说，如果分配$ m $，将$ n $ n $ n $ n $ n $ n $ i $ i $ i $ i $ a $ i $ a $ i $等于$ s（v_i，n）$提供给出，则可以证明分配给$ i $ i $ i $不公平。为了使这种解释有意义，我们希望份额可行，这意味着对于班上的任何估值，都有一种分配，至少可以为每个代理人提供她的份额。最大值的份额是添加估值的可行份额的自然候选人。但是，黑川，Procaccia和Wang [2018]表明，这是不可行的。 我们对可行份额的家族进行了系统的研究。我们说，如果真相最大化隐含的保证，则分享是\ emph {自我最大化}。我们表明，每一个可行的份额都由一些自我最大化和可行的份额主导。我们试图确定那些可以计算多项式时间的自我最大的可行股票，并提供最高的份额价值。我们表明，对于增材估值（及以后）而言，不存在一个具有SM为单位的可行份额（主导每一个自我最大化（SM）可行的份额）。因此，我们将统治性属性放松到统治属性，最高为$ρ$（称为$ρ$ domination）。对于加性估值，我们呈现可行，自我最大化和多项式时间可计算的共享。对于$ n $代理商，我们提供这样的份额，即$ \ frac {2n} {3n-1} $ - 统治。对于两个代理商，我们提出了这样的份额，即$（1-ε）$。此外，对于这些股份，我们提出了多个时间算法，这些算法将对每个代理商至少给她的份额提供分配。
We consider fair allocation of a set $M$ of indivisible goods to $n$ equally-entitled agents, with no monetary transfers. Every agent $i$ has a valuation $v_i$ from some given class of valuation functions. A share $s$ is a function that maps a pair $(v_i,n)$ to a value, with the interpretation that if an allocation of $M$ to $n$ agents fails to give agent $i$ a bundle of value at least equal to $s(v_i,n)$, this serves as evidence that the allocation is not fair towards $i$. For such an interpretation to make sense, we would like the share to be feasible, meaning that for any valuations in the class, there is an allocation that gives every agent at least her share. The maximin share was a natural candidate for a feasible share for additive valuations. However, Kurokawa, Procaccia and Wang [2018] show that it is not feasible. We initiate a systematic study of the family of feasible shares. We say that a share is \emph{self maximizing} if truth-telling maximizes the implied guarantee. We show that every feasible share is dominated by some self-maximizing and feasible share. We seek to identify those self-maximizing feasible shares that are polynomial time computable, and offer the highest share values. We show that a SM-dominating feasible share -- one that dominates every self-maximizing (SM) feasible share -- does not exist for additive valuations (and beyond). Consequently, we relax the domination property to that of domination up to a multiplicative factor of $ρ$ (called $ρ$-dominating). For additive valuations we present shares that are feasible, self-maximizing and polynomial-time computable. For $n$ agents we present such a share that is $\frac{2n}{3n-1}$-dominating. For two agents we present such a share that is $(1 - ε)$-dominating. Moreover, for these shares we present poly-time algorithms that compute allocations that give every agent at least her share.
