A strongly polynomial algorithm for linear exchange markets
A strongly polynomial algorithm for linear exchange markets
复制标题
DOI：
10.1145/3313276.3316340
复制
发表时间：
2018-09
期刊：
影响因子：
--
通讯作者：
J. Garg;László A. Végh
中科院分区：
文献类型：
--
作者：
J. Garg;László A. Végh
我们提出了一种强多项式算法，用于计算具有线性效用的 Arrow-Debreu 交易市场的均衡。我们的算法基于弱多项式 Duan-Mehlhorn (DM) 算法的变体。我们使用 DM 算法作为子程序来识别显示的边缘，即必须对应于每个均衡解决方案中最佳性价比交易的代理和商品对。每次找到新的显露边时，我们都会使用另一个子例程来决定是否存在使用当前显露边集的最佳解决方案，或者如果不存在，则找到近似最小化对需求和供应约束的违反的解决方案。该任务可以简化为求解线性规划（LP）。尽管我们无法在强多项式时间内求解这个线性规划，但我们表明它可以通过一个更简单的线性规划来近似，其中每个不等式有两个变量，并且可以在强多项式时间内求解。
We present a strongly polynomial algorithm for computing an equilibrium in Arrow-Debreu exchange markets with linear utilities. Our algorithm is based on a variant of the weakly-polynomial Duan-Mehlhorn (DM) algorithm. We use the DM algorithm as a subroutine to identify revealed edges, i.e., pairs of agents and goods that must correspond to best bang-per-buck transactions in every equilibrium solution. Every time a new revealed edge is found, we use another subroutine that decides if there is an optimal solution using the current set of revealed edges, or if none exists, finds the solution that approximately minimizes the violation of the demand and supply constraints. This task can be reduced to solving a linear program (LP). Even though we are unable to solve this LP in strongly polynomial time, we show that it can be approximated by a simpler LP with two variables per inequality that is solvable in strongly polynomial time.