Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation
Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation
复制标题
两全其美：资源分配的事前和事后公平
DOI：
10.1145/3391403.3399537
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Rohit Vaish
中科院分区：
文献类型：
--
作者：
Rupert Freeman;Nisarg Shah;Rohit Vaish
我们研究了不可分货物在代理人之间的分配问题。当随机化被允许时，就有可能实现令人信服的公平保证，例如无嫉妒(Foley，1967)，该保证指出，任何代理人(在预期中)都不应倾向于任何其他代理人的分配。例如，我们可以简单地将每种商品分配给统一随机选择的代理人，而不是其他商品。然而，尽管这一计划在事前是公平的，但它可能会产生非常不公平的事后结果，例如偶然地将所有货物分配给一个代理人。另一方面，在没有随机化的情况下，一定程度的事后不公平是不可避免的。然而，有可能保证放松无嫉妒，从而限制最大程度的嫉妒。一种流行的放松是对一种商品的无嫉妒(Lipton等人，2004；Budish，2011)，这要求任何代理人对另一种代理人的嫉妒可以通过从被嫉妒的代理人的捆绑中最多消除一种商品来消除。我们在这项工作中的目标是开发用于构建随机分配的算法，该算法同时具有严格的事前公平和近似公平的事后分配。我们关注加性估值，在这种情况下，代理人对两个不相交的资源集合的并集的价值是她对这两个集合的价值的总和。我们解决的关键问题是，在确定性分配上，是否总是存在一个事前无嫉妒(EF)分布，每个分配满足最多一个好的无嫉妒(EF1)。我们积极地解决了这一问题，设计了一种新的算法-递归概率序列，它是Bogomolneia和Moulin(2001)的经典概率序列(PS)算法的改编，继承了PS的许多理想行为(特别是无嫉妒)，同时还允许对EF1分配进行简单和自然的分解。虽然我们对算法的天真解释得到了确定性分配的可能指数数量上的分布，但我们证明了代理和商品数量中的支持大小多项式是足够的，从而产生了递归概率序列的有效变体。除了事前EF和事后EF1之外，人们可能想要实现经济效率概念的帕累托最优，即不可能找到一种在不降低任何其他代理人效用的情况下提高某一代理人效用的配置。我们证明，与事前EF和事后EF1一起实现事前帕累托最优(即关于随机分配)是不可能的。然而，如果我们愿意在事后担保问题上妥协，就可以实现强有力的事前担保-在公平和经济效率方面。特别是，我们能够实现事前群体公平(Conitzer等人，2019年)，它同时推广了无嫉妒和帕累托最优，并结合了EF1所暗示的两个事后公平性质：最多一种好或一种建议的相称性(Conitzer等人，2017年)和最多一种好或少一种好或$EF_1^1$(Barman和Krishnamurthy，2019)。我们的算法使用了著名的最大Nash福利分配的四舍五入，通过一个新的特征，我们证明了这是唯一可以用来实现期望属性的分配规则。有关更多细节，我们请读者参阅该论文的完整版(Freeman等人，2020年)。
We study the problem of allocating indivisible goods among agents. When randomization is allowed, it is possible to achieve compelling fairness guarantees such as envy-freeness (Foley, 1967), which states that no agent should (in expectation) prefer any other agent's allocation to her own. For instance, we can simply allocate each good, independently of the other goods, to an agent chosen uniformly at random. However, while this scheme is fair ex-ante, it may produce outcomes that are very unfair ex-post, such as by chance assigning all the goods to a single agent. On the other hand, in the absence of randomization, some amount of ex-post unfairness is unavoidable. Nevertheless, it is possible to guarantee relaxations of envy-freeness that bound the maximum level of envy. One popular relaxation is envy-freeness up to one good (Lipton et al., 2004; Budish, 2011), which requires that the envy of any agent toward another agent can be removed by the elimination of at most one good from the envied agent's bundle. Our goal in this work is to develop algorithms for constructing randomized allocations that are simultaneously exactly fair ex-ante and approximately fair ex-post. We focus on additive valuations, under which an agent's value for the union of two disjoint sets of resources is the sum of her values for the two sets. The key question we address is whether there always exists an ex-ante envy-free (EF) distribution over deterministic allocations that each satisfy envy-freeness up to one good (EF1). We settle this positively by designing a novel algorithm, Recursive Probabilistic Serial, which is an adaptation of the classic Probabilistic Serial (PS) algorithm of Bogomolnaia and Moulin (2001) that inherits much of the desirable behavior of PS (in particular, ex-ante envy-freeness), while also allowing a simple and natural decomposition over EF1 allocations. While a naive interpretation of our algorithm yields a distribution over a possibly-exponential number of deterministic allocations, we show that a support size polynomial in the number of agents and goods is sufficient, thus yielding an efficient variant of Recursive Probabilistic Serial. In addition to ex-ante EF and ex-post EF1, one may want to achieve the economic efficiency notion of Pareto optimality, which states that it should be impossible to find an allocation that improves some agent's utility without reducing any other agent's. We show that it is impossible to achieve ex-ante Pareto optimality (that is, with respect to the randomized allocation) in conjunction with ex-ante EF and ex-post EF1. However, strong ex-ante guarantees --- in terms of both fairness and economic efficiency --- can be achieved if we are willing to compromise on the ex-post guarantee. In particular, we are able to achieve ex-ante group fairness (Conitzer et al., 2019), which generalizes both envy-freeness and Pareto optimality, in conjunction with two ex-post fairness properties that are incomparable but are both implied by EF1: proportionality up to one good or Prop1 (Conitzer et al, 2017) and envy-freeness up to one good more-and-less or $EF_1^1$ (Barman and Krishnamurthy, 2019). Our algorithm uses a rounding of the well-known Maximum Nash Welfare allocation, and by a novel characterization, we prove that this is the only allocation rule that can be used to achieve the desired properties. For more details, we refer the reader to the full version of the paper (Freeman et al., 2020).
登录
查看更多内容
DOI：
10.1145/3391403.3399526
发表时间：
2019-02
期刊：
Proceedings of the 21st ACM Conference on Economics and Computation
影响因子：
--
作者：
J. Garg;Setareh Taki
通讯作者：
J. Garg;Setareh Taki
使用混合甘露计算竞争均衡
DOI：
--
发表时间：
2020
期刊：
AAMAS Conference proceedings
影响因子：
--
作者：
Garg, Jugal;McGlaughlin, Peter
通讯作者：
McGlaughlin, Peter
二元估值的公平除法：一条规则来统治它们
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