Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve
Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve
复制标题
顺序公平分配：实现最优嫉妒-效率权衡曲线
DOI：
10.1145/3489048.3526951
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Yu, Christina Lee
中科院分区：
文献类型：
--
作者：
Sinclair, Sean R.;Banerjee, Siddhartha;Yu, Christina Lee
我们考虑将有限资源分配给经过 T 轮到达的个人的问题。每轮都有随机数量的个体到达，个体可以通过其类型（即对不同资源的偏好）来表征。在这种情况下，“公平”的标准概念是分配同时满足无嫉妒和效率。对于可分割资源，当预先知道每种类型的个体数量时，对于一大类效用函数来说，上述需求可以同时实现。然而，在在线环境中，当每种类型的个体数量仅逐轮揭示时，没有任何策略可以同时保证这些需求。我们表明，在在线环境中，两个所需的属性（无嫉妒性和效率）是直接争论的，因为任何实现加性反事实无嫉妒性高达 LT 因子的算法必然会遭受至少 1 / LT 的效率损失。我们用一个简单的算法 Guarded-Hope 来补充这种不确定性原理，该算法基于自适应阈值策略分配资源，并且能够在该边界上实现任何公平效率点。
We consider the problem of dividing limited resources to individuals arriving over T rounds. Each round has a random number of individuals arrive, and individuals can be characterized by their type (i.e. preferences over the different resources). A standard notion of 'fairness' in this setting is that an allocation simultaneously satisfy envy-freeness and efficiency. For divisible resources, when the number of individuals of each type are known upfront, the above desiderata are simultaneously achievable for a large class of utility functions. However, in an online setting when the number of individuals of each type are only revealed round by round, no policy can guarantee these desiderata simultaneously.We show that in the online setting, the two desired properties (envy-freeness and efficiency) are in direct contention, in that any algorithm achieving additive counterfactual envy-freeness up to a factor of LT necessarily suffers a efficiency loss of at least 1 / LT. We complement this uncertainty principle with a simple algorithm, Guarded-Hope, which allocates resources based on an adaptive threshold policy and is able to achieve any fairness-efficiency point on this frontier.
登录
查看更多内容
公平理论中的两个问题
DOI：
--
发表时间：
1976
期刊：
影响因子：
--
作者：
H. Varian
通讯作者：
H. Varian
DOI：
10.1145/3219166.3219179
发表时间：
2018-06
期刊：
Proceedings of the 2018 ACM Conference on Economics and Computation
影响因子：
--
作者：
Gerdus Benade;Aleksandr M. Kazachkov;Ariel D. Procaccia;Alexandros Psomas
通讯作者：
Gerdus Benade;Aleksandr M. Kazachkov;Ariel D. Procaccia;Alexandros Psomas
死者器官匹配的公平性
DOI：
10.1145/3278721.3278749
发表时间：
2018
期刊：
Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society
影响因子：
--
作者：
Nicholas Mattei;Abdallah Saffidine;T. Walsh
通讯作者：
T. Walsh
在线器官匹配机制
DOI：
10.24963/ijcai.2017/49
发表时间：
2017
期刊：
arXiv: Optimization and Control
影响因子：
--
作者：
Nicholas Mattei;Abdallah Saffidine;T. Walsh
通讯作者：
T. Walsh
DOI：
10.1145/3357713.3384280
发表时间：
2019
期刊：
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
N. Bansal;Haotian Jiang;Sahil Singla;Makrand Sinha
通讯作者：
Makrand Sinha