Theory of Computing
-------------------
Title : Dichotomies in Equilibrium Computation and Membership of PLC Markets in FIXP
Authors : Jugal Garg, Ruta Mehta, and Vijay V. Vazirani
Volume : 12
Number : 20
Pages : 1-25
URL : https://theoryofcomputing.org/articles/v012a020
Abstract
--------
Piecewise-linear, concave (PLC) utility functions play an important
role in work done at the intersection of economics and algorithms. We
prove that the problem of computing an equilibrium in Arrow-Debreu
markets with PLC utilities and PLC production sets is in the class
FIXP. Recently it was shown that these problems are also FIXP-hard
(Garg et al., arXiv:1411.5060), hence settling the long-standing
question of the complexity of this problem. Central to our proof is
capturing equilibria of these markets as fixed points of a continuous
function via a nonlinear complementarity problem (NCP) formulation.
Next, we provide dichotomies for equilibrium computation problems,
both Nash and market. There is a striking resemblance in the
dichotomies for these two problems, hence providing a unifying view.
We note that in the past, dichotomies have played a key role in
bringing clarity to the complexity of decision and counting problems.