Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions

After more than a decade of work in TCS on the computabil- ity of market equilibria, complementary pivot algorithms have emerged as the best hope of obtaining practical al- gorithms. So far they have been used for markets under separable, piecewise-linear concave (SPLC) utility functions [23] and SPLC production sets [25]. Can his approach extend to non-separable utility functions and production sets? A major impediment is rationality, i.e., if all parameters are set to rational numbers, there should be a rational equilibrium. Recently, [35] introduced classes of non-separable utility functions and production sets, called Leontief-free, which are applicable when goods are substitutes. For markets with these utility functions and production sets, and satisfying mild sufficiency conditions, we obtain the following results: • Proof of rationality. • Complementary pivot algorithms based on a suitable adaptation of Lemke's classic algorithm. • A strongly polynomial bound on the running time of our algorithms if the number of goods is a constant, despite the fact that the set of solutions is disconnected. • Experimental verification, which confirms that our algorithms are practical. • Proof of PPAD-completeness. Next we give a proof of membership in FIXP for markets under piecewise-linear concave (PLC) utility functions and PLC production sets by capturing equilibria as fixed points of a continuous function via a nonlinear complementarity problem (NCP) formulation. Finally we provide, for the first time, dichotomies for equilibrium computation problems, both Nash and market; in particular, the results stated above play a central role in arriving at the dichotomies for exchange markets and for markets with production. We note that in the past, dichotomies have played a key role in bringing clarity to the complexity of decision and counting problems.