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

• 成果类型: Article
• 署名作者: Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; University of California System; University of California Irvine
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0892
• 发表日期: 2018
• 页码: 996-1024
• 关键词: polynomial-time; Market equilibrium; complexity; points; EXISTENCE

摘要

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.