Simultaneously Achieving Ex-ante and Ex-post Fairness
Simultaneously Achieving Ex-ante and Ex-post Fairness
复制标题
同时实现事前事后公平
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
H. Aziz
中科院分区：
文献类型：
--
作者：
H. Aziz
我们提出了一个多项式时间的算法，计算一个事前的嫉妒免费彩票嫉妒免费一个项目（EF 1）确定性分配。与最近提出的算法相比，它具有以下优点：它不依赖于包括分离预言机在内的线性规划机器;它是SD有效的（事前和事后）;事前结果相当于由著名的概率序列规则返回的结果。因此，我们回答了Freeman，Shah和Vaish（2020）提出的一个问题，即概率序列规则的结果是否可以通过事后EF 1分配来实现。在光的一对夫妇的不可能性的结果，我们证明，我们的算法可以被视为满足最大的一组属性。在二进制效用下，我们的算法也是事前群体策略的预防和事前帕累托最优的。最后，我们还表明，检查是否可以实现一个给定的随机分配的彩票EF 1和帕累托最优分配是NP-难的。
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.
二元估值的公平除法：一条规则来统治它们
DOI：
--
发表时间：
2020
期刊：
WINE
影响因子：
--
作者：
Halpern, Daniel;Shah, Nisarg;Psomas, Alexandros;Procaccia, Ariel D.
通讯作者：
Procaccia, Ariel D.
不可分割物品分配的群体公平性
DOI：
10.1609/aaai.v33i01.33011853
发表时间：
2019
期刊：
Proceedings of the AAAI Conference on Artificial Intelligence
影响因子：
--
作者：
Conitzer, Vincent;Freeman, Rupert;Shah, Nisarg;Vaughan, Jennifer Wortman
通讯作者：
Vaughan, Jennifer Wortman