论文标题
同时实现前安特和前公平
Simultaneously Achieving Ex-ante and Ex-post Fairness
论文作者
论文摘要
我们提出了一种多项式时间算法，该算法计算出一个前嫉妒的彩票，而无需嫉妒的一项（EF1）确定性分配。它在最近提出的算法上具有以下优点：它不依赖于包括分离甲骨文的线性编程机制；它是SD效率（前Ante和Ex-Post）；前结果等同于众所周知的概率序列规则返回的结果。结果，我们回答了Freeman，Shah和Vaish（2020）提出的一个问题（2020）是否可以通过EX-POST EF1分配来实施概率序列规则的结果。鉴于我们证明的几个不可能的结果，我们的算法可以看作是满足最大属性集的。在二进制实用程序下，我们的算法也是前群组 - 策略性的，并且是前Ante Pareto的最佳选择。最后，我们还表明，检查给定的随机分配是否可以通过彩票对EF1实施，而Pareto最佳分配是NP-HARD。
We present a polynomial-time algorithm that computes an ex-ante envy-free lottery over envy-free up to one item (EF1) deterministic allocations. It has the following advantages over a recently proposed algorithm: it does not rely on the linear programming machinery including separation oracles; it is SD-efficient (both ex-ante and ex-post); and the ex-ante outcome is equivalent to the outcome returned by the well-known probabilistic serial rule. As a result, we answer a question raised by Freeman, Shah, and Vaish (2020) whether the outcome of the probabilistic serial rule can be implemented by ex-post EF1 allocations. In the light of a couple of impossibility results that we prove, our algorithm can be viewed as satisfying a maximal set of properties. Under binary utilities, our algorithm is also ex-ante group-strategyproof and ex-ante Pareto optimal. Finally, we also show that checking whether a given random allocation can be implemented by a lottery over EF1 and Pareto optimal allocations is NP-hard.
