Dichotomies in equilibrium computation and membership of PLC markets in FIXP

Jugal Garg, Ruta Mehta, Vijay V. Vazirani

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Article number20
JournalTheory of Computing
Volume12
DOIs
StatePublished - 2016

Keywords

  • Dichotomy
  • FIXP
  • Market equilibrium
  • Non-linear complementarity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Dichotomies in equilibrium computation and membership of PLC markets in FIXP'. Together they form a unique fingerprint.

Cite this