A FPTAS for computing a symmetric Leontief competitive economy equilibrium

In this paper, we consider a linear complementarity problem (LCP) arisen from the Nash and Arrow–Debreu competitive economy equilibria where the LCP coefficient matrix is symmetric. We prove that the decision problem, to decide whether or not there exists a complementary solution, is NP-complete. Under certain conditions, an LCP solution is guaranteed to exist and we present a fully polynomial-time approximation scheme (FPTAS) for approximating a complementary solution, although the LCP solution set can be non-convex or non-connected. Our method is based on approximating a quadratic social utility optimization problem (QP) and showing that a certain KKT point of the QP problem is an LCP solution. Then, we further show that such a KKT point can be approximated with a new improved running time complexity $${{O}((\frac{n^4}{\epsilon})\log\log(\frac{1}{\epsilon}))}$$ arithmetic operation in accuracy $${\epsilon \in (0,1)}$$. We also report preliminary computational results which show that the method is highly effective. Applications in competitive market model problems with other utility functions are also presented, including global trading and dynamic spectrum management problems.