Market equilibrium computation

Last updated

Market equilibrium computation (also called competitive equilibrium computation or clearing-prices computation) is a computational problem in the intersection of economics and computer science. The input to this problem is a market, consisting of a set of resources and a set of agents. There are various kinds of markets, such as Fisher market and Arrow–Debreu market, with divisible or indivisible resources. The required output is a competitive equilibrium , consisting of a price-vector (a price for each resource), and an allocation (a resource-bundle for each agent), such that each agent gets the best bundle possible (for him) given the budget, and the market clears (all resources are allocated).

Contents

Market equilibrium computation is interesting due to the fact that a competitive equilibrium is always Pareto efficient. The special case of a Fisher market, in which all buyers have equal incomes, is particularly interesting, since in this setting a competitive equilibrium is also envy-free. Therefore, market equilibrium computation is a way to find an allocation which is both fair and efficient.

Since the 1960s, there has been attempts to apply the general equilibrium theory to support policy decisions in subjects such as tax reform or simultaneous tariff reductions. These models are typically large, so efficient comnputation is needed. [1]

Definitions

The input to the market-equilibrium-computation consists of the following ingredients: [2] :chap.5

  1. A set of resources with pre-specified supplies. The resources can be divisible (in which case, their supply is w.l.o.g. normalized to 1), or indivisible .
    • A bundle is represented by a vector , where is the quantity of resource . When resources are indivisible, all xj are integers; when resources are divisible, the xj can be arbitrarily real numbers (usually normalized to [0,1]).
  2. A set of agents. For each agent, there is a preference relation over bundles, which can be represented by a utility function. The utility function of agent is denoted by .
  3. An initial endowment for each agent.
    • In a Fisher market, the endowment is a budget of "fiat money" - a money that has no value outside the market, and thus does not enter the utility function. Since the agents come with money only, they are often called buyers.
    • In an Arrow–Debreu market, the endowment is an arbitrary bundle ; in this model, agents can be both buyers and sellers.

The required output should contain the following ingredients:

  1. A price-vector; a price for each resource. The price of a bundle is the sum of the prices of the resources in the, so the price of a bundle is .
  2. An allocation - a bundle for each agent i.

The output should satisfy the following requirements:

  1. The bundle should be affordable to i, that is, its price should be at most the price of agent i's endowment.
    • In a Fisher market, this means that .
    • In an Arrow-Debreu market, this means that .
  2. The bundle should be in the demand set of i: , defined as the set of bundles maximizing the agent's utility among all affordable bundles (regardless of supply), e.g., in a Fisher market:
  3. The market clears, i.e., all resources are allocated. The corresponding prices are called market-clearing prices.

A price and allocation satisfying these requirements are called a competitive equilibrium (CE) or a market equilibrium; the prices are also called equilibrium prices or clearing prices.

Kinds of utility functions

Market equilibrium computation has been studied under various assumptions regarding the agents' utility functions.

Main results

Approximate algorithms

Herbert Scarf [3] presented a proof of existence of a CE using Sperner's lemma (see Fisher market). He converted this proof to an algorithm for computing an approximate CE. In his later work, he continued to develop these algorithms. [4]

Merrill [5] gave an extended algorithm for approximate CE.

Other algorithms for fixed-point computation, such as the homotopy method, can also be used to compute CE.

All these algorithms do not have a polynomial runtime guarantee.

Hardness results

Papadimitriou (who invented the class PPAD) [6] proved that computing an approximate CE for Arrow-Debreu markets given by aggregate excess demand functions is PPAD-complete. Later results have shown PPAD-hardness even for more specific classes of utility functions:

Complementing these results, Garg, Mehta, Vazirani and Yazdanbod [12] show that computing an approximate CE with PLC utilities is in PPAD. The main technical challenge was to show that an approximate fixed-point corresponds to an approximate CE.

Etessami and Yannakkis (who defined the complexity class FIXP) [13] proved that computing CE prices for exchange markets with algebraic demand functions is FIXP-complete. Later results have shown FIXP-hardness for more specific classes of utilities:

Exact algorithms

For some special cases, polynomial-time algorithms have been developed.

Eaves [15] showed that, in an exchange market with Cobb-Douglas utilities, the CE be written as the solution to a linear program; hence it is possible to compute all CE in polynomial time.

Deng, Papadimitriou and Safra [16] :Thm.2 present a polytime algorithm for finding the CE when m is bounded and the utilities are linear.

Kakade, Kearns and Ortiz [17] :Sub.5.1 generalize the above algorithm for bounded m. Their generalized algorithm computes an approximate CE for a general class of non-linear utility functions.

Newman and Primak [18] studied two variants of the ellipsoid method for finding a CE in an Arrow-Debreu market with linear utilities. They prove that the inscribed ellipsoid method is more computationally efficient than the circumscribed ellipsoid method.

Codenotti and Varadarajan [19] gave a polytime algorithm for Fisher markes with Leontief utilities. Their approach extends to a wider family of utilities, which includes CES utilities. However, unlike in the linear case, the equilibrium prices can be irrational, whicn means that an exact computation is not possible.

Codenotti, McCune, Penumatcha and Varadarajan [20] gave a polytime algorithm for Arrow-Debreu markes with CES utilities where the elasticity of substitution is at least 1/2.

Codenotti, Pemmaraju, Raman and Varadarajan [21] presented a polytime algorithm for exchange markets with weak gross substitute utilities; these generalize linear, Cobb-Douglas, CES and even some non-homogeneous utility functions.

Chen, Deng, Sun and Yao [22] gave a polytime algorithm for Fisher markets with logarithmic utilities, when either m or n is constant.

Kamal Jain [23] introduced a convex program (already described in 1983 by Nenakov and Primak) that characterizes the CE for exchange markets with linear utilities, CES utilities with r>0, and some other utility functions. He also proved that for linear utilities there exists a normalized CE with rational prices. Jain used this property to develop a variant of the ellipsoid method to compute the CE exactly in polytime. Later, Ye [24] showed how to use Interior-point methods, which are much more efficient in practice. Codenotti and Varadarajan [25] presented a different convex program that characterizes the CE also for CES utilities with -1 < r < 0.

Devanur, Papadimitriou, Saberi and Vazirani [26] gave a polynomial-time algorithm for exactly computing an equilibrium for Fisher markets with linear utility functions. Their algorithm uses the primal–dual paradigm in the enhanced setting of KKT conditions and convex programs. Their algorithm is weakly-polynomial: it solves maximum flow problems, and thus it runs in time , where umax and Bmax are the maximum utility and budget, respectively.

Orlin [27] gave an improved algorithm for a Fisher market model with linear utilities, running in time . He then improved his algorithm to run in strongly-polynomial time: .

Devanur and Kannan [8] gave algorithms for Arrow-Debreu markets with concave utility functions, where all resources are goods (the utilities are positive):

Garg, Mehta, Vazirani and Yazdanbod [12] gave a polytime algorithm for Leontief utilities when n is constant and m is variable.

Bads and mixed manna

Bogomolnaia and Moulin and Sandomirskiy and Yanovskaia studied the existence and properties of CE in a Fisher market with bads (items with negative utilities) [28] and with a mixture of goods and bads. [29] In contrast to the setting with goods, when the resources are bads the CE does not solve any convex optimization problem even with linear utilities. CE allocations correspond to local minima, local maxima, and saddle points of the product of utilities on the Pareto frontier of the set of feasible utilities. The CE rule becomes multivalued. This work has led to several works on algorithms of finding CE in such markets:

If both n and m are variable, the problem becomes computationally hard:

Indivisible goods

When the goods are indivisible, a CE may not exist, but it may be possible to compute an approximate CE.

Deng, Papadimitriou and Safra [16] study exchange markets with m goods, that may be indivisible. They show the following:

  1. WIth indivisible goods, it is NP-hard to approximate the deficiency of the market to a factor better than 1/3. It is NP-hard to find equilibrium prices even when they are known to exist. This holds even for linear utilities.
  2. With indivisible goods, there is a polytime algorithm for finding an approximate CE when m is bounded and the utilities are linear.
  3. When utilities are not strictly-concave, computing a Pareto efficient allocation requires Omega(n log(m+n)) bits of communication, in order to coordinate the bundles (when utilities are strictly-concave no coordination is needed, as each agent has a unique optimal bundle given the price vector). The lower bound holds even for divisible goods; for indivisible goods, the lower bound is even for approximately-efficient allocation, for any approximation ratio. These bounds hold even for constant m.

Main techniques

Bang-for-buck

When the utilities are linear, the bang-per-buck of agent i (also called BPB or utility-per-coin) is defined as the utility of i divided by the price paid. The BPB of a single resource is ; the total BPB is .

A key observation for finding a CE in a Fisher market with linear utilities is that, in any CE and for any agent i: [2]

Assume that every product has a potential buyer - a buyer with . Then, the above inequalities imply that , i.e, all prices are positive.

Cell decomposition

Cell decomposition [8] is a process of partitioning the space of possible prices into small "cells", either by hyperplanes or, more generally, by polynomial surfaces. A cell is defined by specifying on which side of each of these surfaces it lies (with polynomial surfaces, the cells are also known as semialgebraic sets). For each cell, we either find a market-clearing price-vector (i.e., a price in that cell for which a market-clearing allocation exists), or verify that the cell does not contain a market-clearing price-vector. The challenge is to find a decomposition with the following properties:

Convex optimization: homogeneous utilities

If the utilities of all agents are homogeneous functions, then the equilibrium conditions in the Fisher model can be written as solutions to a convex optimization program called the Eisenberg-Gale convex program. [34] This program finds an allocation that maximizes the weighted geometric mean of the buyers' utilities, where the weights are determined by the budgets. Equivalently, it maximizes the weighted arithmetic mean of the logarithms of the utilities:

Maximize
Subject to:
Non-negative quantities: For every buyer and product :
Sufficient supplies: For every product :

(since supplies are normalized to 1).

This optimization problem can be solved using the Karush–Kuhn–Tucker conditions (KKT). These conditions introduce Lagrangian multipliers that can be interpreted as the prices, . In every allocation that maximizes the Eisenberg-Gale program, every buyer receives a demanded bundle. I.e, a solution to the Eisenberg-Gale program represents a market equilibrium. [2] :141–142

Vazirani's algorithm: linear utilities, weakly polynomial-time

A special case of homogeneous utilities is when all buyers have linear utility functions. We assume that each resource has a potential buyer - a buyer that derives positive utility from that resource. Under this assumption, market-clearing prices exist and are unique. The proof is based on the Eisenberg-Gale program. The KKT conditions imply that the optimal solutions (allocations and prices ) satisfy the following inequalities:

  1. All prices are non-negative: .
  2. If a product has a positive price, then all its supply is exhausted: .
  3. The total BPB is weakly larger than the BPB from any individual resource, .
  4. Agent i consumes only resources with the maximum possible BPB, i.e., .

Assume that every product has a potential buyer - a buyer with . Then, inequality 3 implies that , i.e, all prices are positive. Then, inequality 2 implies that all supplies are exhausted. Inequality 4 implies that all buyers' budgets are exhausted. I.e, the market clears. Since the log function is a strictly concave function, if there is more than one equilibrium allocation then the utility derived by each buyer in both allocations must be the same (a decrease in the utility of a buyer cannot be compensated by an increase in the utility of another buyer). This, together with inequality 4, implies that the prices are unique. [2] :107

Vazirani [2] :109–121 presented an algorithm for finding equilibrium prices and allocations in a linear Fisher market. The algorithm is based on condition 4 above. The condition implies that, in equilibrium, every buyer buys only products that give him maximum BPB. Let's say that a buyer "likes" a product, if that product gives him maximum BPB in the current prices. Given a price-vector, construct a flow network in which the capacity of each edge represents the total money "flowing" through that edge. The network is as follows:

The price-vector p is an equilibrium price-vector, if and only if the two cuts ({s},V\{s}) and (V\{t},{t}) are min-cuts. Hence, an equilibrium price-vector can be found using the following scheme:

There is an algorithm that solves this problem in weakly polynomial time.

Generalizations and extensions

Graphical markets

Kakade, Kearns and Ortiz [17] studied a generalized Arrow-Debreu market in which agents are located on a graph, trade may occur only between neighboring agents, and all the local markets must clear. They proved a general existence theorem for graphical equilibria, and an algorithm for computing graphucak equilibria which runs in time polynomial in the number of consumers when the graph is a tree. Their algorithms work also for agents with non-linear utilities.

Online computation

Gao, Peysakhovich and Kroer [35] presented an algorithm for online computation of market equilibrium.

See also

Further reading

References

  1. Codenotti, Bruno; Pemmaraju, Sriram; Varadarajan, Kasturi (December 1, 2004). "The computation of market equilibria". SIGACT News. 35 (4): 23–37. doi:10.1145/1054916.1054927. ISSN   0163-5700.
  2. 1 2 3 4 5 Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). "Chapter 5: Combinatorial Algorithms for Market Equilibria / Vijay V. Vazirani". Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN   0-521-87282-0.
  3. Scarf, Herbert E. (1967). "On the Computation of Equilibrium Prices". Cowles Foundation Discussion Papers.
  4. Scarf, Herbert E. (January 1, 1982), Chapter 21 The computation of equilibrium prices: An exposition, Handbook of Mathematical Economics, vol. 2, Elsevier, pp. 1007–1061, doi:10.1016/S1573-4382(82)02016-5, ISBN   978-0-444-86127-6 , retrieved August 14, 2025
  5. O. H. Merrill (1972). Applications and Extensions of an algorithm that computes fixed points of certain upper semi-continuous point to set mappings. PhD thesis.
  6. Christos Papadimitriou (1994). "On the complexity of the parity argument and other inefficient proofs of existence" (PDF). Journal of Computer and System Sciences. 48 (3): 498–532. doi:10.1016/S0022-0000(05)80063-7. Archived from the original (PDF) on March 4, 2016. Retrieved March 8, 2008.
  7. Codenotti, Bruno; Saberi, Amin; Varadarajan, Kasturi; Ye, Yinyu (January 22, 2006). "Leontief economies encode nonzero sum two-player games". Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm. SODA '06. USA: Society for Industrial and Applied Mathematics: 659–667. doi:10.1145/1109557.1109629. ISBN   978-0-89871-605-4.
  8. 1 2 3 4 Devanur, N. R.; Kannan, R. (October 1, 2008). "Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents". 2008 49th Annual IEEE Symposium on Foundations of Computer Science. pp. 45–53. doi:10.1109/FOCS.2008.30. ISBN   978-0-7695-3436-7. S2CID   13992175.
  9. Chen, X.; Dai, D.; Du, Y.; Teng, S. (October 1, 2009). "Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities". 2009 50th Annual IEEE Symposium on Foundations of Computer Science. pp. 273–282. arXiv: 0904.0644 . doi:10.1109/FOCS.2009.29. ISBN   978-1-4244-5116-6. S2CID   580788.
  10. 1 2 Chen, Xi; Teng, Shang-Hua (2009). "Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria". In Dong, Yingfei; Du, Ding-Zhu; Ibarra, Oscar (eds.). Algorithms and Computation. Lecture Notes in Computer Science. Vol. 5878. Berlin, Heidelberg: Springer. pp. 647–656. arXiv: 0907.4130 . doi:10.1007/978-3-642-10631-6_66. ISBN   978-3-642-10631-6. S2CID   7817966.
  11. 1 2 3 Chaudhury, Bhaskar Ray; Garg, Jugal; McGlaughlin, Peter; Mehta, Ruta (August 1, 2020). "Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chores". arXiv: 2008.00285 [cs.GT].
  12. 1 2 3 Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra (June 19, 2017). "Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria". Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2017. New York, NY, USA: Association for Computing Machinery. pp. 890–901. doi:10.1145/3055399.3055474. ISBN   978-1-4503-4528-6.
  13. Etessami, Kousha; Yannakakis, Mihalis (January 2010). "On the Complexity of Nash Equilibria and Other Fixed Points". SIAM Journal on Computing. 39 (6): 2531–2597. doi:10.1137/080720826. ISSN   0097-5397.
  14. Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V. (May 31, 2014). "Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions". Proceedings of the forty-sixth annual ACM symposium on Theory of computing. STOC '14. New York, NY, USA: Association for Computing Machinery: 525–534. doi:10.1145/2591796.2591863. ISBN   978-1-4503-2710-7.
  15. Curtis Eaves, B. (1985), Manne, Alan S. (ed.), "Finite solution of pure trade markets with Cobb-Douglas utilities", Economic Equilibrium: Model Formulation and Solution, Mathematical Programming Studies, vol. 23, Berlin, Heidelberg: Springer, pp. 226–239, doi:10.1007/bfb0121035, ISBN   978-3-642-00917-4 , retrieved August 15, 2025
  16. 1 2 Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel (May 19, 2002). "On the complexity of equilibria". Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. STOC '02. New York, NY, USA: Association for Computing Machinery. pp. 67–71. doi:10.1145/509907.509920. ISBN   978-1-58113-495-7.
  17. 1 2 Kakade, Sham M.; Kearns, Michael; Ortiz, Luis E. (2004). "Graphical Economics" . In Shawe-Taylor, John; Singer, Yoram (eds.). Learning Theory. Lecture Notes in Computer Science. Vol. 3120. Berlin, Heidelberg: Springer. pp. 17–32. doi:10.1007/978-3-540-27819-1_2. ISBN   978-3-540-27819-1.
  18. Newman, D. J.; Primak, M. E. (December 1, 1992). "Complexity of circumscribed and inscribed ellipsoid methods for solving equilibrium economical models" . Applied Mathematics and Computation. 52 (2): 223–231. doi:10.1016/0096-3003(92)90079-G. ISSN   0096-3003.
  19. Codenotti, Bruno; Varadarajan, Kasturi (2004). "Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities". In Díaz, Josep; Karhumäki, Juhani; Lepistö, Arto; Sannella, Donald (eds.). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 3142. Berlin, Heidelberg: Springer. pp. 371–382. doi:10.1007/978-3-540-27836-8_33. ISBN   978-3-540-27836-8.
  20. Codenotti, Bruno; McCune, Benton; Penumatcha, Sriram; Varadarajan, Kasturi (2005). "Market Equilibrium for CES Exchange Economies: Existence, Multiplicity, and Computation" . In Sarukkai, Sundar; Sen, Sandeep (eds.). FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science. Vol. 3821. Berlin, Heidelberg: Springer. pp. 505–516. doi:10.1007/11590156_41. ISBN   978-3-540-32419-5.
  21. Codenotti, Bruno; Pemmaraju, Sriram; Varadarajan, Kasturi (January 23, 2005). "On the polynomial time computation of equilibria for certain exchange economies". Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '05. USA: Society for Industrial and Applied Mathematics: 72–81. ISBN   978-0-89871-585-9.
  22. Chen, Ning; Deng, Xiaotie; Sun, Xiaoming; Yao, Andrew Chi-Chih (2004). "Fisher Equilibrium Price with a Class of Concave Utility Functions". In Albers, Susanne; Radzik, Tomasz (eds.). Algorithms – ESA 2004. Lecture Notes in Computer Science. Vol. 3221. Berlin, Heidelberg: Springer. pp. 169–179. doi:10.1007/978-3-540-30140-0_17. ISBN   978-3-540-30140-0.
  23. Jain, Kamal (January 2007). "A Polynomial Time Algorithm for Computing an Arrow–Debreu Market Equilibrium for Linear Utilities". SIAM Journal on Computing. 37 (1): 303–318. doi:10.1137/S0097539705447384. ISSN   0097-5397.
  24. Ye, Yinyu (January 1, 2008). "A path to the Arrow–Debreu competitive market equilibrium". Mathematical Programming. 111 (1): 315–348. doi:10.1007/s10107-006-0065-5. ISSN   1436-4646.
  25. Codenotti, Bruno; Varadarajan, Kasturi (March 10, 2005). Market Equilibrium in Exchange Economies with Some Families of Concave Utility Functions (Report). University Library of Munich, Germany.
  26. Devanur, Nikhil R.; Papadimitriou, Christos H.; Saberi, Amin; Vazirani, Vijay V. (November 5, 2008). "Market equilibrium via a primal--dual algorithm for a convex program" . Journal of the ACM. 55 (5): 22:1–22:18. doi:10.1145/1411509.1411512. ISSN   0004-5411. S2CID   11836728.
  27. Orlin, James B. (June 5, 2010). "Improved algorithms for computing fisher's market clearing prices". Proceedings of the forty-second ACM symposium on Theory of computing. STOC '10. Cambridge, Massachusetts, USA: Association for Computing Machinery. pp. 291–300. doi:10.1145/1806689.1806731. hdl: 1721.1/68009 . ISBN   978-1-4503-0050-6. S2CID   8235905.
  28. Bogomolnaia, Anna; Moulin, Hervé; Sandomirskiy, Fedor; Yanovskaia, Elena (March 1, 2019). "Dividing bads under additive utilities". Social Choice and Welfare. 52 (3): 395–417. doi: 10.1007/s00355-018-1157-x . ISSN   1432-217X.
  29. Bogomolnaia, Anna; Moulin, Hervé; Sandomirskiy, Fedor; Yanovskaya, Elena (2017). "Competitive Division of a Mixed Manna". Econometrica. 85 (6): 1847–1871. arXiv: 1702.00616 . doi:10.3982/ECTA14564. ISSN   1468-0262. S2CID   17081755.
  30. Brânzei, Simina; Sandomirskiy, Fedor (July 3, 2019). "Algorithms for Competitive Division of Chores". arXiv: 1907.01766 [cs.GT].
  31. Garg, Jugal; McGlaughlin, Peter (May 5, 2020). "Computing Competitive Equilibria with Mixed Manna". Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. AAMAS '20. Auckland, New Zealand: International Foundation for Autonomous Agents and Multiagent Systems: 420–428. ISBN   978-1-4503-7518-4.
  32. Chaudhury, Bhaskar Ray; Garg, Jugal; McGlaughlin, Peter; Mehta, Ruta (January 1, 2021), "Competitive Allocation of a Mixed Manna", Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, Society for Industrial and Applied Mathematics, pp. 1405–1424, arXiv: 2008.02753 , doi: 10.1137/1.9781611976465.85 , ISBN   978-1-61197-646-5
  33. Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise (1998). "A New Algorithm to Find a Point in Every Cell Defined by a Family of Polynomials" . In Caviness, Bob F.; Johnson, Jeremy R. (eds.). Quantifier Elimination and Cylindrical Algebraic Decomposition. Texts and Monographs in Symbolic Computation. Vienna: Springer. pp. 341–350. doi:10.1007/978-3-7091-9459-1_17. ISBN   978-3-7091-9459-1.
  34. Eisenberg, E. (1961). "Aggregation of Utility Functions". Management Science. 7 (4): 337–350. doi:10.1287/mnsc.7.4.337. Archived from the original on September 23, 2017.
  35. Gao, Yuan; Peysakhovich, Alex; Kroer, Christian (2021). "Online Market Equilibrium with Application to Fair Division". Advances in Neural Information Processing Systems. 34. Curran Associates, Inc.: 27305–27318. arXiv: 2103.12936 .
  36. Codenotti, Bruno; Pemmaraju, Sriram; Varadarajan, Kasturi (December 1, 2004). "The computation of market equilibria" . SIGACT News. 35 (4): 23–37. doi:10.1145/1054916.1054927. ISSN   0163-5700.
  37. Garg, Jugal; Tao, Yixin; Végh, László A. (January 2025), "Approximating Competitive Equilibrium by Nash Welfare" , Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, Society for Industrial and Applied Mathematics, pp. 2538–2559, doi:10.1137/1.9781611978322.83, ISBN   978-1-61197-832-2 , retrieved July 25, 2025
  38. Wu, Fang; Zhang, Li (June 11, 2007). "Proportional response dynamics leads to market equilibrium". Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. STOC '07. New York, NY, USA: Association for Computing Machinery. pp. 354–363. doi:10.1145/1250790.1250844. ISBN   978-1-59593-631-8.
  39. Cheung, Yun Kuen; Cole, Richard; Tao, Yixin (June 3, 2025), Proportional Response Dynamics in Gross Substitutes Markets, arXiv: 2506.02852