Algorithms for Competitive Division of Chores
Algorithms for Competitive Division of Chores
复制标题
竞争性家务分工算法
DOI：
10.1287/moor.2023.1361
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Fedor Sandomirskiy
中科院分区：
文献类型：
--
作者：
Simina Brânzei;Fedor Sandomirskiy
我们研究了在不允许货币转移的情况下，在多个代理人之间分配可分的坏（家务）的问题。竞争规则以其在商品方面的显著公平和效率属性而闻名。这条规则被Bogomolnaia、Moulin、Sandomirskiy和Yanovskaya扩展到家务。对于货物和杂务，该规则产生帕累托最优和无嫉妒的分配。在货物的情况下，竞争规则的结果可以很容易地计算出来。竞争分配解决了艾森伯格-盖尔凸规划;因此结果是唯一的，可以通过标准梯度方法近似找到。Orlin给出了一个关于代理商和商品数量的多项式时间内运行的精确算法。在家务的情况下，竞争规则并不能解决任何凸优化问题;相反，竞争分配对应于可行效用集的帕累托边界上的纳什社会福利的局部最小值、局部最大值和鞍点。帕累托边界可能包含许多这样的点，因此，竞争规则的结果不再是唯一的。在本文中，我们证明了竞争规则的家务的所有结果可以计算在强多项式时间，如果代理的数量或家务的数量是固定的。该方法是基于三个想法的组合：帕累托最优分配的所有消费图可以在多项式时间内列出;对于一个给定的消费图，一个竞争性的效用配置文件的候选人可以通过一个明确的公式构建;每个候选人可以检查的竞争力和分配可以使用最大流计算重建。我们的算法立即给出了一个近似公平的分配不可分割的家务的四舍五入技术的Barman和Krishnamurthy。资金来源：这项工作得到了美国国家科学基金会（CNS 1518941）、耶路撒冷希伯来大学戴维斯夫人奖学金信托基金、H2020欧洲研究理事会（740435）和加州理工学院林德研究所的支持。
We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities when monetary transfers are not allowed. The competitive rule is known for its remarkable fairness and efficiency properties in the case of goods. This rule was extended to chores by Bogomolnaia, Moulin, Sandomirskiy, and Yanovskaya. For both goods and chores, the rule produces Pareto optimal and envy-free allocations. In the case of goods, the outcome of the competitive rule can be easily computed. Competitive allocations solve the Eisenberg-Gale convex program; hence the outcome is unique and can be approximately found by standard gradient methods. An exact algorithm that runs in polynomial time in the number of agents and goods was given by Orlin. In the case of chores, the competitive rule does not solve any convex optimization problem; instead, competitive allocations correspond to local minima, local maxima, and saddle points of the Nash social welfare on the Pareto frontier of the set of feasible utilities. The Pareto frontier may contain many such points and, consequently, the outcome of the competitive rule is no longer unique. In this paper, we show that all the outcomes of the competitive rule for chores can be computed in strongly polynomial time if either the number of agents or the number of chores is fixed. The approach is based on a combination of three ideas: all consumption graphs of Pareto optimal allocations can be listed in polynomial time; for a given consumption graph, a candidate for a competitive utility profile can be constructed via an explicit formula; each candidate can be checked for competitiveness and the allocation can be reconstructed using a maximum flow computation. Our algorithm immediately gives an approximately-fair allocation of indivisible chores by the rounding technique of Barman and Krishnamurthy. Funding: This work was supported by National Science Foundation (CNS 1518941); Lady Davis Fellowship Trust, Hebrew University of Jerusalem; H2020 European Research Council (740435); Linde Institute at Caltech.
登录
查看更多内容
DOI：
10.1145/3490486.3538255
发表时间：
2022
期刊：
EC '22: Proceedings of the 23rd ACM Conference on Economics and Computation
影响因子：
--
作者：
Chaudhury, Bhaskar Ray;Garg, Jugal;McGlaughlin, Peter;Mehta, Ruta
通讯作者：
Mehta, Ruta
混合甘露的竞争性分配
DOI：
10.1137/1.9781611976465.85
发表时间：
2021
期刊：
ACM-SIAM Symposium on Discrete Algorithms (SODA
影响因子：
--
作者：
Bhaskar Ray Chaudhury, Jugal Garg
通讯作者：
Bhaskar Ray Chaudhury, Jugal Garg
论家务劳动竞争均衡的存在性
DOI：
10.4230/lipics.itcs.2022.41
发表时间：
2022
期刊：
13th Innovations in Theoretical Computer Science Conference (ITCS 2022
影响因子：
--
作者：
Chaudhury, Bhaskar Ray;Garg, Jugal;McGlaughlin, Peter;Mehta, Ruta
通讯作者：
Mehta, Ruta
用于寻找家务近似竞争平衡的多项式时间算法
DOI：
10.1137/1.9781611977073.92
发表时间：
2022
期刊：
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
影响因子：
--
作者：
Boodaghians, Shant;Chaudhury, Bhaskar Ray;Mehta, Ruta
通讯作者：
Mehta, Ruta
DOI：
10.1145/3313276.3316340
发表时间：
2018-09
期刊：
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
J. Garg;László A. Végh
通讯作者：
J. Garg;László A. Végh