pdf icon
Volume 12 (2016) Article 20 pp. 1-25
Dichotomies in Equilibrium Computation and Membership of PLC Markets in FIXP
Received: August 15, 2015
Revised: July 16, 2016
Published: December 30, 2016
Download article from ToC site:
[PDF (291K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: market equilibrium, FIXP, dichotomy, non-linear complementarity
Categories: ecommerce, game theory, algorithmic game theory, Nash equilibrium, market equilibrium, fixed point, dichotomy, completeness, complexity theory
ACM Classification: F.2.0, G.0
AMS Classification: 68Q25, 91B26, 91B50, 90C30, 90C33

Abstract: [Plain Text Version]

$ \newcommand{\cclass}[1]{{\textsf{#1}}} $

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 $\textsf{FIXP}$. Recently it was shown that these problems are also $\textsf{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.

A preliminary version of this paper appeared as part of a paper in STOC'14.