Substitution with satiation: A new class of utility functions and a complementary pivot algorithm

Jugal Garg, Ruta Mehta, Vijay V. Vazirani

Research output: Contribution to journalArticlepeer-review


We introduce new classes of utility functions and production sets, called Leontief-free, which are applicable when goods are substitutes and utilities/production are subadditive (to model inter-good satiation). When goods are complements, the well studied Leontief utility functions do an adequate job; however, to the best of our knowledge, a similar concept for the case of goods that are substitutes was not known. For markets with these utility functions and production sets, we obtain the following results: Rational-valued equilibria, despite the fact that these utility functions and production sets are nonseparable. We prove that the problem of computing an equilibrium is PPAD-complete, where PPAD stands for Polynomial Parity Arguments on Directed Graphs. We obtain complementary pivot algorithms based on a suitable adaptation of Lemke's classic algorithm. Our algorithms run in strongly polynomial time if the number of goods is a constant, despite the fact that the set of solutions is disconnected. Experimental verification confirms that our algorithms are practical.

Original languageEnglish (US)
Pages (from-to)996-1024
Number of pages29
JournalMathematics of Operations Research
Issue number3
StatePublished - Aug 2018


  • Arrow-Debreu markets
  • Complementary pivot algorithm
  • LCP
  • Leontief-free utilities
  • Market equilibrium
  • PPAD

ASJC Scopus subject areas

  • General Mathematics
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Substitution with satiation: A new class of utility functions and a complementary pivot algorithm'. Together they form a unique fingerprint.

Cite this