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

Eisenberg-Gale markets: Algorithms and game-theoretic properties

Author

Listed:
  • Jain, Kamal
  • Vazirani, Vijay V.

Abstract

We define a new class of markets, the Eisenberg-Gale markets. This class contains Fisher's linear market, markets from the resource allocation framework of Kelly [Kelly, F.P., 1997. Charging and rate control for elastic traffic. Europ. Transactions Telecommunications 8, 33-37], as well as numerous interesting new markets. We obtain combinatorial, strongly polynomial algorithms for several markets in this class. Our algorithms have a simple description as ascending price auctions. Our algorithms lead to insights into game-theoretic properties of these markets, such as efficiency, fairness, and competition monotonicity. They also help determine if these markets always have rational equilibria. A classification of Eisenberg-Gale markets w.r.t. these properties reveals a surprisingly rich set of possibilities.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:gamebe:v:70:y:2010:i:1:p:84-106
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899-8256(08)00211-X
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. E. Eisenberg, 1961. "Aggregation of Utility Functions," Management Science, INFORMS, vol. 7(4), pages 337-350, July.
    3. Francisco Barahona, 1995. "Packing Spanning Trees," Mathematics of Operations Research, INFORMS, vol. 20(1), pages 104-115, February.
    4. Groenevelt, H., 1991. "Two algorithms for maximizing a separable concave function over a polymatroid feasible region," European Journal of Operational Research, Elsevier, vol. 54(2), pages 227-236, September.
    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. Anna Bogomolnaia & Hervé Moulin & Fedor Sandomirskiy & Elena Yanovskaia, 2019. "Dividing bads under additive utilities," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 52(3), pages 395-417, March.
    2. Laszlo A. Vegh, 2011. "Concave Generalized Flows with Applications to Market Equilibria," Papers 1109.3893, arXiv.org, revised Apr 2012.
    3. Soham R. Phade & Venkat Anantharam, 2018. "Optimal Resource Allocation over Networks via Lottery-Based Mechanisms," Papers 1812.00501, arXiv.org.
    4. Ortega, Josué, 2020. "Multi-unit assignment under dichotomous preferences," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 15-24.
    5. Anna Bogomolnaia & Hervé Moulin & Fedor Sandomirskiy & Elena Yanovskaya, 2017. "Competitive Division of a Mixed Manna," Econometrica, Econometric Society, vol. 85(6), pages 1847-1871, November.
    6. Andrew Yang & Bruce Changlong Xu & Ivan Villa-Renteria, 2021. "Matching Markets," Papers 2109.14850, arXiv.org.
    7. Yuan Gao & Christian Kroer, 2020. "Infinite-Dimensional Fisher Markets and Tractable Fair Division," Papers 2010.03025, arXiv.org, revised Apr 2021.
    8. Gagan Goel & Vijay V. Vazirani, 2011. "A Perfect Price Discrimination Market Model with Production, and a Rational Convex Program for It," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 762-782, November.
    9. 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.
    10. Kelli Francis-Staite, 2022. "Internal multi-portfolio rebalancing processes: Linking resource allocation models and biproportional matrix techniques to portfolio management," Papers 2201.06183, arXiv.org.
    11. 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.
    12. Martijn H. H. Schoot Uiterkamp & Marco E. T. Gerards & Johann L. Hurink, 2022. "On a Reduction for a Class of Resource Allocation Problems," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1387-1402, May.
    13. Anna Bogomolnaia & Herve Moulin & Fedor Sandomirskiy & Elena Yanovskaya, 2016. "Dividing Goods or Bads Under Additive Utilities," HSE Working papers WP BRP 147/EC/2016, National Research University Higher School of Economics.
    14. Fadaei, Salman & Bichler, Martin, 2017. "Truthfulness with value-maximizing bidders: On the limits of approximation in combinatorial markets," European Journal of Operational Research, Elsevier, vol. 260(2), pages 767-777.
    15. Dvijotham, Krishnamurthy & Rabani, Yuval & Schulman, Leonard J., 2022. "Convergence of incentive-driven dynamics in Fisher markets," Games and Economic Behavior, Elsevier, vol. 134(C), pages 361-375.
    16. László A. Végh, 2014. "Concave Generalized Flows with Applications to Market Equilibria," Mathematics of Operations Research, INFORMS, vol. 39(2), pages 573-596, May.
    17. Ashish Goel & Reyna Hulett & Benjamin Plaut, 2018. "Markets Beyond Nash Welfare for Leontief Utilities," Papers 1807.05293, arXiv.org, revised Dec 2019.

    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. 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.
    2. Ortega, Josué, 2020. "Multi-unit assignment under dichotomous preferences," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 15-24.
    3. Denizalp Goktas & Jiayi Zhao & Amy Greenwald, 2023. "T\^atonnement in Homothetic Fisher Markets," Papers 2306.04890, arXiv.org.
    4. Ashish Goel & Reyna Hulett & Benjamin Plaut, 2018. "Markets Beyond Nash Welfare for Leontief Utilities," Papers 1807.05293, arXiv.org, revised Dec 2019.
    5. Taheri Tehrani, Mohammad & Afshin Hemmatyar, Ali Mohammad, 2019. "Welfare-aware strategic demand control in an intelligent market-based framework: Move towards sustainable smart grid," Applied Energy, Elsevier, vol. 251(C), pages 1-1.
    6. Moshe Babaioff & Noam Nisan & Inbal Talgam-Cohen, 2021. "Competitive Equilibrium with Indivisible Goods and Generic Budgets," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 382-403, February.
    7. 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.
    8. Thorsten Hens & Beate Pilgrim & Janos Mayer, "undated". "Existence of Sunspot Equilibria and Uniqueness of Spot Market Equilibria: The Case of Intrinsically Complete Markets," IEW - Working Papers 188, Institute for Empirical Research in Economics - University of Zurich.
    9. Lilia Maliar & Serguei Maliar, 2005. "An Analytical Construction Of Constantinides¿ Social Utility Function," Working Papers. Serie AD 2005-25, Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie).
    10. Edward E. Schlee, 2001. "The Value of Information in Efficient Risk-Sharing Arrangements," American Economic Review, American Economic Association, vol. 91(3), pages 509-524, June.
    11. James Moore, 2010. "On aggregation and welfare analysis," Review of Economic Design, Springer;Society for Economic Design, vol. 14(1), pages 95-129, March.
    12. Jun Tong & Jian-Qiang Hu & Jiaqiao Hu, 2017. "A Computational Algorithm for Equilibrium Asset Pricing Under Heterogeneous Information and Short-Sale Constraints," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(05), pages 1-16, October.
    13. Bruno Codenotti & Kasturi Varadarajan, 2005. "Market Equilibrium in Exchange Economies with Some Families of Concave Utility Functions," Computational Economics 0503001, University Library of Munich, Germany.
    14. Robert W. Dimand, 2019. "Léon Walras, Irving Fisher and the Cowles Approach to General Equilibrium Analysis," Cowles Foundation Discussion Papers 2205, Cowles Foundation for Research in Economics, Yale University.
    15. Jean-Sébastien Lenfant & Jérôme Lallement, 2004. "L'équilibre général comme savoir : de Walras à nos jours," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) hal-01765036, HAL.
    16. Martijn H. H. Schoot Uiterkamp & Marco E. T. Gerards & Johann L. Hurink, 2022. "On a Reduction for a Class of Resource Allocation Problems," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1387-1402, May.
    17. Shafer, Wayne & Sonnenschein, Hugo, 1975. "Some theorems on the existence of competitive equilibrium," Journal of Economic Theory, Elsevier, vol. 11(1), pages 83-93, August.
    18. 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.
    19. Corinna Gottschalk & Hendrik Lüthen & Britta Peis & Andreas Wierz, 2018. "Optimization problems with color-induced budget constraints," Journal of Combinatorial Optimization, Springer, vol. 36(3), pages 861-870, October.
    20. K. Vela Velupillai, 2010. "Introduction to the Phillips Machine and the Analogue Computing Tradition in Economics," ASSRU Discussion Papers 1008, ASSRU - Algorithmic Social Science Research Unit.

    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:70:y:2010:i:1:p:84-106. 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.