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

Jugal Garg, Ruta Mehta, Vijay V. Vazirani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationSTOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages525-534
Number of pages10
ISBN (Print)9781450327107
DOIs
StatePublished - Jan 1 2014
Externally publishedYes
Event4th Annual ACM Symposium on Theory of Computing, STOC 2014 - New York, NY, United States
Duration: May 31 2014Jun 3 2014

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other4th Annual ACM Symposium on Theory of Computing, STOC 2014
CountryUnited States
CityNew York, NY
Period5/31/146/3/14

Keywords

  • FIXP
  • LCP
  • Leontief-free
  • Market equilibrium

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions'. Together they form a unique fingerprint.

  • Cite this

    Garg, J., Mehta, R., & Vazirani, V. V. (2014). Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions. In STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing (pp. 525-534). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/2591796.2591863