Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm

Jugal Garg (), Ruta Mehta () and Vijay V. Vaziranic ()
Additional contact information
Jugal Garg: Department of ISE, University of Illinois at Urbana–Champaign, Urbana, Illinois 61801
Ruta Mehta: Department of Computer Science, University of Illinois at Urbana–Champaign, Urbana, Illinois 61801
Vijay V. Vaziranic: Department of Computer Science, University of California, Irvine, Irvine, California 92697

Mathematics of Operations Research, 2018, vol. 43, issue 3, 996-1024

Abstract: 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.

Keywords: Arrow-Debreu markets; market equilibrium; Leontief-free utilities; LCP; complementary pivot algorithm; PPAD (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0892 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:43:y:2018:i:3:p:996-1024

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().