IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v123y2020icp295-326.html
   My bibliography  Save this article

Tatonnement beyond gross substitutes? Gradient descent to the rescue

Author

Listed:
  • Cheung, Yun Kuen
  • Cole, Richard
  • Devanur, Nikhil R.

Abstract

We identify a class of economies for which tatonnement is equivalent to gradient descent. This is the class of economies for which there is a convex potential function whose gradient is always equal to the negative of the excess demand. Among other consequences, we show that a discrete version of tatonnement converges to the equilibrium for the following economies of complementary goods.

Suggested Citation

  • Cheung, Yun Kuen & Cole, Richard & Devanur, Nikhil R., 2020. "Tatonnement beyond gross substitutes? Gradient descent to the rescue," Games and Economic Behavior, Elsevier, vol. 123(C), pages 295-326.
    • Handle: RePEc:eee:gamebe:v:123:y:2020:i:c:p:295-326
    DOI: 10.1016/j.geb.2019.03.014
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825619300491
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2019.03.014?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. William C. Brainard & Herbert E. Scarf, 2005. "How to Compute Equilibrium Prices in 1891," American Journal of Economics and Sociology, Wiley Blackwell, vol. 64(1), pages 57-83, January.
    2. Keenan, Donald & Kim, Taewon, 2000. "The law of demand implies limits to chaos," Economics Letters, Elsevier, vol. 69(3), pages 313-317, December.
    3. E. Eisenberg, 1961. "Aggregation of Utility Functions," Management Science, INFORMS, vol. 7(4), pages 337-350, July.
    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. Herbert E. Scarf, 1969. "An Example of an Algorithm for Calculating General Equilibrium," Cowles Foundation Discussion Papers 276, Cowles Foundation for Research in Economics, Yale University.
    6. Champsaur, Paul & Dreze, Jacques H & Henry, Claude, 1977. "Stability Theorems with Economic Applications," Econometrica, Econometric Society, vol. 45(2), pages 273-294, March.
    7. 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.
    8. Mas-Colell, Andreu & Whinston, Michael D. & Green, Jerry R., 1995. "Microeconomic Theory," OUP Catalogue, Oxford University Press, number 9780195102680, Decembrie.
    9. Scarf, Herbert, 1969. "An Example of an Algorithm for Calculating General Equilibrium Prices," American Economic Review, American Economic Association, vol. 59(4), pages 669-677, Part I Se.
    10. Keller, Wouter J., 1976. "A nested CES-type utility function and its demand and price-index functions," European Economic Review, Elsevier, vol. 7(2), pages 175-186, February.
    11. H. Uzawa, 1960. "Walras' Tâtonnement in the Theory of Exchange," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 27(3), pages 182-194.
    12. Sergiu Hart & Yishay Mansour, 2013. "How Long To Equilibrium? The Communication Complexity Of Uncoupled Equilibrium Procedures," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 10, pages 215-249, World Scientific Publishing Co. Pte. Ltd..
    13. CHAMPSAUR, Paul & DREZE, Jacques H. & HENRY, Claude, 1977. "Stability theorems with economic," LIDAM Reprints CORE 297, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    14. Franklin M. Fisher, 1972. "On Price Adjustment without an Auctioneer," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 39(1), pages 1-15.
    15. Dohtani, Akitaka, 1993. "Global stability of the competitive economy involving complementary relations among commodities," Journal of Mathematical Economics, Elsevier, vol. 22(1), pages 73-83.
    16. Van Der Laan, G. & Talman, A. J. J., 1987. "A convergent price adjustment process," Economics Letters, Elsevier, vol. 23(2), pages 119-123.
    17. Dohtani, Akitaka, 1998. "The system stability of dynamic processes," Journal of Mathematical Economics, Elsevier, vol. 29(2), pages 161-182, March.
    18. Jain, Kamal & Vazirani, Vijay V., 2010. "Eisenberg-Gale markets: Algorithms and game-theoretic properties," Games and Economic Behavior, Elsevier, vol. 70(1), pages 84-106, September.
    19. Keenan, Donald C., 2001. "Aggregate Substitution Effects Implying Global Stability," Journal of Economic Theory, Elsevier, vol. 101(1), pages 317-329, November.
    20. Saari, Donald G & Simon, Carl P, 1978. "Effective Price Mechanisms," Econometrica, Econometric Society, vol. 46(5), pages 1097-1125, September.
    21. Freund, Yoav & Schapire, Robert E., 1999. "Adaptive Game Playing Using Multiplicative Weights," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 79-103, October.
    22. Herrmann, John D. & Kahn, Peter J., 1999. "A continuity property for local price adjustment mechanisms," Journal of Mathematical Economics, Elsevier, vol. 31(4), pages 419-453, May.
    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. Luofeng Liao & Yuan Gao & Christian Kroer, 2022. "Statistical Inference for Fisher Market Equilibrium," Papers 2209.15422, arXiv.org.
    2. Yun Kuen Cheung & Stefanos Leonardos & Georgios Piliouras, 2021. "Learning in Markets: Greed Leads to Chaos but Following the Price is Right," Papers 2103.08529, arXiv.org, revised Mar 2021.
    3. Jalota, Devansh & Pavone, Marco & Qi, Qi & Ye, Yinyu, 2023. "Fisher markets with linear constraints: Equilibrium properties and efficient distributed algorithms," Games and Economic Behavior, Elsevier, vol. 141(C), pages 223-260.
    4. Eric Budish & Ruiquan Gao & Abraham Othman & Aviad Rubinstein & Qianfan Zhang, 2023. "Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI)," Papers 2305.11406, arXiv.org, revised May 2023.
    5. Yun Kuen Cheung & Stefanos Leonardos & Georgios Piliouras & Shyam Sridhar, 2021. "From Griefing to Stability in Blockchain Mining Economies," Papers 2106.12332, arXiv.org.

    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. W D A Bryant, 2009. "General Equilibrium:Theory and Evidence," World Scientific Books, World Scientific Publishing Co. Pte. Ltd., number 6875, January.
    2. Paul Oslington, 2012. "General Equilibrium: Theory and Evidence," The Economic Record, The Economic Society of Australia, vol. 88(282), pages 446-448, September.
    3. Denizalp Goktas & Jiayi Zhao & Amy Greenwald, 2023. "T\^atonnement in Homothetic Fisher Markets," Papers 2306.04890, arXiv.org.
    4. Aad Ruiter, 2020. "Approximating Walrasian Equilibria," Computational Economics, Springer;Society for Computational Economics, vol. 55(2), pages 577-596, February.
    5. Nikhil Garg & Ashish Goel & Benjamin Plaut, 2021. "Markets for public decision-making," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 56(4), pages 755-801, May.
    6. Ortega, Josué, 2020. "Multi-unit assignment under dichotomous preferences," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 15-24.
    7. Herings, Jean-Jacques & van der Laan, Gerard & Venniker, Richard, 1998. "The transition from a Dreze equilibrium to a Walrasian equilibrium1," Journal of Mathematical Economics, Elsevier, vol. 29(3), pages 303-330, April.
    8. Rabani, Yuval & Schulman, Leonard J., 2021. "The invisible hand of Laplace: The role of market structure in price convergence and oscillation," Journal of Mathematical Economics, Elsevier, vol. 95(C).
    9. Herings, P.J.J., 1994. "A globally and universally stable quantity adjustment process for an exchange economy with price rigidities," Other publications TiSEM 6f90d995-9065-4ad8-bd04-2, Tilburg University, School of Economics and Management.
    10. Mandel, Antoine & Gintis, Herbert, 2014. "Stochastic stability in the Scarf economy," Mathematical Social Sciences, Elsevier, vol. 67(C), pages 44-49.
    11. Alan Kirman, 2006. "Demand Theory and General Equilibrium: From Explanation to Introspection, a Journey down the Wrong Road," History of Political Economy, Duke University Press, vol. 38(5), pages 246-280, Supplemen.
    12. Arkit, Aleksandra, 2003. "Globally stable price dynamics," Journal of Mathematical Economics, Elsevier, vol. 39(1-2), pages 27-38, February.
    13. Herings, P. Jean-Jacques & van der Laan, Gerard & Venniker, Richard, 1996. "The Transition from a Drèze Equilibrium to a Walrasian Equilibrium," LIDAM Discussion Papers IRES 1996013, Université catholique de Louvain, Institut de Recherches Economiques et Sociales (IRES).
    14. Jean-Jacques Herings, P., 2002. "Universally converging adjustment processes--a unifying approach," Journal of Mathematical Economics, Elsevier, vol. 38(3), pages 341-370, November.
    15. Yuval Rabani & Leonard J. Schulman, 2016. "The Invisible Hand of Laplace: the Role of Market Structure in Price Convergence and Oscillation," Papers 1602.07628, arXiv.org.
    16. 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).
    17. Ashish Goel & Reyna Hulett & Benjamin Plaut, 2018. "Markets Beyond Nash Welfare for Leontief Utilities," Papers 1807.05293, arXiv.org, revised Dec 2019.
    18. Keenan, Donald C. & Kim, Taewon, 2013. "Diagonal dominance and global stability," Mathematical Social Sciences, Elsevier, vol. 65(3), pages 217-221.
    19. Anjan Mukherji, 2012. "The second fundamental theorem of positive economics," International Journal of Economic Theory, The International Society for Economic Theory, vol. 8(2), pages 125-138, June.
    20. Mayer, Francine, 1983. "Les modèles de répartition des revenus de type intégré : quelques éléments de comparaison," L'Actualité Economique, Société Canadienne de Science Economique, vol. 59(1), pages 121-134, mars.

    More about this item

    Keywords

    Market; Equilibria; Gradient descent; Tatonnement;
    All these keywords.

    JEL classification:

    • D5 - Microeconomics - - General Equilibrium and Disequilibrium

    Statistics

    Access and download statistics

    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:eee:gamebe:v:123:y:2020:i:c:p:295-326. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    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.