Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores
Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores
复制标题
用于寻找家务近似竞争平衡的多项式时间算法
DOI：
10.1137/1.9781611977073.92
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Mehta, Ruta
中科院分区：
文献类型：
--
作者：
Boodaghians, Shant;Chaudhury, Bhaskar Ray;Mehta, Ruta
等收入竞争均衡(CEEI)被认为是在代理人之间公平和有效地分配一组物品的最佳机制之一。本文研究了以线性函数为子例的1齐次凹效用函数下，当物品是代理不喜欢(负值)的琐事时的CEEI计算问题。众所周知，即使使用线性效用，CEEI集也可能是非凸的和不连通的，在更一般的交换模型中，问题是PPAD-Hard。针对这些否定的结果，我们设计了一个FPTAS：一个多项式时间算法来计算∊-近似CEEI，其中运行时间依赖于多项式。(2017)证明了一个非凸极小化问题的KKT点的坐标都不为零。由于这种非零约束，基于朴素梯度的方法无法找到期望的局部极小值，因为它们被吸引到零。我们发展了一种外点法，它交替地猜测非零KKT点和沿着这些点处的支撑超平面最大化目标。当效用函数是线性函数时，我们给出了求精确迭代的显式过程，并证明了在多项式时间内可以找到更强形式的近似CEEI。最后，我们注意到，我们的算法扩展到不平等收入(CE)的设置，以及具有线性效用的混合甘露，其中每个代理人可能喜欢(正值)一些项目而不喜欢(负值)其他项目。
Competitive equilibrium with equal income (CEEI) is considered one of the best mechanisms to allocate a set of items among agents fairly and efficiently. In this paper, we study the computation of CEEI when items are chores that are disliked (negatively valued) by agents, under 1-homogeneous and concave utility functions which includes linear functions as a subcase. It is well-known that, even with linear utilities, the set of CEEI may be non-convex and disconnected, and the problem is PPAD-hard in the more general exchange model. In contrast to these negative results, we design a FPTAS: A polynomial-time algorithm to compute∊-approximate CEEI where the running-time depends polynomially on .Our algorithm relies on the recent characterization due to Bogomolnaia et al. (2017) of the CEEI set as exactly the KKT points of a non-convex minimization problem that have all coordinates non-zero. Due to thisnon-zeroconstraint, naïve gradient-based methods fail to find the desired local minima as they are attracted towards zero. We develop anexterior-point methodthat alternates between guessingnon-zeroKKT points and maximizing the objective along supporting hyperplanes at these points. We show that this procedure must converge quickly to an approximate KKT point which then can be mapped to an approximate CEEI; this exterior point method may be of independent interest.When utility functions are linear, we give explicit procedures for finding the exact iterates, and as a result show that a stronger form of approximate CEEI can be found in polynomial time. Finally, we note that our algorithm extends to the setting of un-equal incomes (CE), and to mixed manna with linear utilities where each agent may like (positively value) some items and dislike (negatively value) others.
登录
查看更多内容
DOI：
10.2139/ssrn.2914241
发表时间：
2017-02
期刊：
National Research University Higher School of Economics Research Paper Series
影响因子：
--
作者：
Anna Bogomolnaia;H. Moulin;Fedor Sandomirskiy;E. Yanovskaya
通讯作者：
Anna Bogomolnaia;H. Moulin;Fedor Sandomirskiy;E. Yanovskaya
DOI：
10.1287/moor.2023.1361
发表时间：
2019
期刊：
ArXiv
影响因子：
--
作者：
Simina Brânzei;Fedor Sandomirskiy
通讯作者：
Fedor Sandomirskiy
一类可分离凸目标最小成本流问题的强多项式算法
DOI：
--
发表时间：
2011
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
László A. Végh
通讯作者：
László A. Végh
混合甘露的竞争性分配
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.1145/2488608.2488617
发表时间：
2013
期刊：
Proceedings of the 22nd ACM Conference on Economics and Computation
影响因子：
--
作者：
M. Feldman;N. Gravin;Brendan Lucier
通讯作者：
Brendan Lucier