论文标题
最好的两者中最好的：在资源分配中的前和前公平性
Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation
论文作者
论文摘要
我们研究了具有添加估值的代理商中不可分割的商品的问题。当允许随机分组时，就可以实现令人信服的公平概念，例如嫉妒，该概念指出，任何代理人都不应更喜欢任何其他代理人的分配而不是自己的分配。当必须确定性的分配时，就不可能实现确切的公平性，但是可以保证诸如嫉妒性诸如嫉妒之类的概念，可以保证。我们在这项工作中的目标是通过构建一个完全公平的前ante且近似公平的前柱的随机分配，同时实现这两者。我们解决的关键问题是，是否可以将前嫉妒与前部的嫉妒结合起来，直到一个善良。我们通过设计一种同时实现这两种属性的有效算法来积极地解决这个问题。如果我们还需要经济效率，我们将获得不可能的结果。但是，我们表明，如果我们稍微放松前公平的保证，经济效率和前嫉妒又可以同时实现。在我们的途中，我们根据最近引入的公平保证，不仅仅是个人，而不仅仅是个人。
We study the problem of allocating indivisible goods among agents with additive valuations. When randomization is allowed, it is possible to achieve compelling notions of fairness such as envy-freeness, which states that no agent should prefer any other agent's allocation to her own. When allocations must be deterministic, achieving exact fairness is impossible but approximate notions such as envy-freeness up to one good can be guaranteed. Our goal in this work is to achieve both simultaneously, by constructing a randomized allocation that is exactly fair ex-ante and approximately fair ex-post. The key question we address is whether ex-ante envy-freeness can be achieved in combination with ex-post envy-freeness up to one good. We settle this positively by designing an efficient algorithm that achieves both properties simultaneously. If we additionally require economic efficiency, we obtain an impossibility result. However, we show that economic efficiency and ex-ante envy-freeness can be simultaneously achieved if we slightly relax our ex-post fairness guarantee. On our way, we characterize the well-known Maximum Nash Welfare allocation rule in terms of a recently introduced fairness guarantee that applies to groups of agents, not just individuals.
