IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v43y2018i3p996-1024.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Jugal Garg & Ruta Mehta & Vijay V. Vaziranic, 2018. "Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm," Mathematics of Operations Research, INFORMS, vol. 43(3), pages 996-1024, August.
  • Handle: RePEc:inm:ormoor:v:43:y:2018:i:3:p:996-1024
    DOI: 10.1287/moor.2017.0892
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/moor.2017.0892
    Download Restriction: no

    File URL: https://libkey.io/10.1287/moor.2017.0892?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. B. Curtis Eaves, 1975. "A Finite Algorithm for the Linear Exchange Model," Cowles Foundation Discussion Papers 389, Cowles Foundation for Research in Economics, Yale University.
    2. Gilboa, Itzhak & Zemel, Eitan, 1989. "Nash and correlated equilibria: Some complexity considerations," Games and Economic Behavior, Elsevier, vol. 1(1), pages 80-93, March.
    3. Smale, Steve, 1976. "A convergent process of price adjustment and global newton methods," Journal of Mathematical Economics, Elsevier, vol. 3(2), pages 107-120, July.
    4. Michael J. Todd, 1976. "Orientation in Complementary Pivot Algorithms," Mathematics of Operations Research, INFORMS, vol. 1(1), pages 54-66, February.
    5. C. E. Lemke, 1965. "Bimatrix Equilibrium Points and Mathematical Programming," Management Science, INFORMS, vol. 11(7), pages 681-689, May.
    6. Sonnenschein, Hugo, 1973. "Do Walras' identity and continuity characterize the class of community excess demand functions?," Journal of Economic Theory, Elsevier, vol. 6(4), pages 345-354, August.
    7. Conitzer, Vincent & Sandholm, Tuomas, 2008. "New complexity results about Nash equilibria," Games and Economic Behavior, Elsevier, vol. 63(2), pages 621-641, July.
    8. M. Seetharama Gowda & Jong-Shi Pang, 1992. "On Solution Stability of the Linear Complementarity Problem," Mathematics of Operations Research, INFORMS, vol. 17(1), pages 77-83, February.
    9. Mantel, Rolf R., 1974. "On the characterization of aggregate excess demand," Journal of Economic Theory, Elsevier, vol. 7(3), pages 348-353, March.
    10. Herbert E. Scarf, 1967. "The Approximation of Fixed Points of a Continuous Mapping," Cowles Foundation Discussion Papers 216R, Cowles Foundation for Research in Economics, Yale University.
    11. Shoven,John B. & Whalley,John, 1992. "Applying General Equilibrium," Cambridge Books, Cambridge University Press, number 9780521266550, October.
    12. McFadden, Daniel & Mas-Colell, Andreu & Mantel, Rolf & Richter, Marcel K., 1974. "A characterization of community excess demand functions," Journal of Economic Theory, Elsevier, vol. 9(4), pages 361-374, December.
    13. Rahul Savani & Bernhard Stengel, 2006. "Hard-to-Solve Bimatrix Games," Econometrica, Econometric Society, vol. 74(2), pages 397-429, March.
    14. Debreu, Gerard, 1974. "Excess demand functions," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 15-21, March.
    15. Maxfield, Robert R., 1997. "General equilibrium and the theory of directed graphs," Journal of Mathematical Economics, Elsevier, vol. 27(1), pages 23-51, February.
    16. Eaves, B. Curtis, 1976. "A finite algorithm for the linear exchange model," Journal of Mathematical Economics, Elsevier, vol. 3(2), pages 197-203, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Yang Zhan & Chuangyin Dang, 2021. "Computing equilibria for markets with constant returns production technologies," Annals of Operations Research, Springer, vol. 301(1), pages 269-284, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Joosten, Reinoud & Talman, Dolf, 1998. "A globally convergent price adjustment process for exchange economies," Journal of Mathematical Economics, Elsevier, vol. 29(1), pages 15-26, January.
    2. Kenneth J. Arrow & Timothy J. Kehoe, 1994. "Distinguished Fellow: Herbert Scarf's Contributions to Economics," Journal of Economic Perspectives, American Economic Association, vol. 8(4), pages 161-181, Fall.
    3. Aad Ruiter, 2020. "Approximating Walrasian Equilibria," Computational Economics, Springer;Society for Computational Economics, vol. 55(2), pages 577-596, February.
    4. Joosten, Reinoud & Talman, Dolf, 1998. "A globally convergent price adjustment process for exchange economies," Journal of Mathematical Economics, Elsevier, vol. 29(1), pages 15-26, January.
    5. Charalambos Aliprantis & Kim Border & Owen Burkinshaw, 1996. "Market economies with many commodities," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 19(1), pages 113-185, March.
    6. repec:dau:papers:123456789/6360 is not listed on IDEAS
    7. Tim Roughgarden, 2010. "Computing equilibria: a computational complexity perspective," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 193-236, January.
    8. Pierre-André Chiappori & Ivar Ekeland & Felix Kübler & Heracles M. Polemarchakis, 1999. "The Identification of Preferences from Equilibrium Prices," Working Papers hal-00598229, HAL.
    9. Rahul Savani & Bernhard Stengel, 2015. "Game Theory Explorer: software for the applied game theorist," Computational Management Science, Springer, vol. 12(1), pages 5-33, January.
    10. José Victor Rios-Rull, 2002. "Desigualdad, ¿qué sabemos?," Investigaciones Economicas, Fundación SEPI, vol. 26(2), pages 221-254, May.
    11. Jean-Jacques Herings, P., 1997. "A globally and universally stable price adjustment process," Journal of Mathematical Economics, Elsevier, vol. 27(2), pages 163-193, March.
    12. Herings,P. Jean-Jacques, 2000. "Universally Stable Adjustment Processes - A Unifying Approach -," Research Memorandum 006, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    13. Yang Zhan & Chuangyin Dang, 2018. "A smooth path-following algorithm for market equilibrium under a class of piecewise-smooth concave utilities," Computational Optimization and Applications, Springer, vol. 71(2), pages 381-402, November.
    14. Lehmann-Waffenschmidt, Marco, 1995. "On the equilibrium price set of a continuous perturbation of exchange economies," Journal of Mathematical Economics, Elsevier, vol. 24(5), pages 497-519.
    15. Jean-Jacques Herings, P., 2002. "Universally converging adjustment processes--a unifying approach," Journal of Mathematical Economics, Elsevier, vol. 38(3), pages 341-370, November.
    16. P. A. Chiappori & I. Ekeland, 1999. "Aggregation and Market Demand: An Exterior Differential Calculus Viewpoint," Econometrica, Econometric Society, vol. 67(6), pages 1435-1458, November.
    17. Joosten, Reinoud, 1995. "Evolution, dynamics, and fixed points," Research Memorandum 005, Maastricht University, Maastricht Economic Research Institute on Innovation and Technology (MERIT).
    18. Chiappori, Pierre-Andre & Ekeland, Ivar, 2004. "Applying exterior differential calculus to economics: a presentation and some new results," Japan and the World Economy, Elsevier, vol. 16(3), pages 363-385, August.
    19. Yariv, Leeat & Jackson, Matthew O., 2018. "The Non-Existence of Representative Agents," CEPR Discussion Papers 13397, C.E.P.R. Discussion Papers.
    20. Momi, Takeshi, 2010. "Excess demand function around critical prices in incomplete markets," Journal of Mathematical Economics, Elsevier, vol. 46(3), pages 293-302, May.
    21. Ghiglino, Christian & Tvede, Mich, 1997. "Multiplicity of Equilibria," Journal of Economic Theory, Elsevier, vol. 75(1), pages 1-15, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:43:y:2018:i:3:p:996-1024. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.