An Improved Approximation Scheme for Computing Arrow-Debreu Prices for the Linear Case

摘要

Recently, Jain, Mahdian and Saberi had given a FPTAS for the problem of computing a market equilibrium in the Arrow-Debreu setting, when the utilities are linear functions. Their running time depended on the size of the numbers representing the utilities and endowments of the buyers. In this paper, we give a strongly polynomial time approximation scheme for this problem. Our algorithm builds upon the main ideas behind the algorithm in [3].