Arrow–Debreu exchange market

In theoretical economics, an Arrow–Debreu exchange market is a special case of the Arrow–Debreu model in which there is no production - there is only an exchange of already-existing goods. An Arrow–Debreu exchange market has the following ingredients:

  • A set of divisible products.
  • A set of agents.
  • Each agent , has an endowment , which is a set of products.

Each product has a price ; the prices are determined by methods described below. The price of a bundle of products is the sum of the prices of the products in the bundle. A bundle is represented by a vector , where is the quantity of product . So the price of a bundle is .

Given a price-vector, the budget of an agent is the total price of his endowment, .

A bundle is affordable for a buyer if the price of that bundle is at most the buyer's budget. I.e, a bundle is affordable for buyer if .

Each buyer has a preference relation over bundles, which can be represented by a utility function. The utility function of buyer is denoted by . The demand set of a buyer is the set of affordable bundles that maximize the buyer's utility among all affordable bundles, i.e.:

.

A competitive equilibrium (CE) is a price-vector in which it is possible to allocate, to each agent, a bundle from his demand-set, such that the total allocation exactly equals the supply of products. The corresponding prices are called market-clearing prices. A CE always exists, even in the more general Arrow–Debreu model. The main challenge is to find a CE.

Computing an equilibrium

edit

Approximate CE

edit

Kakade, Kearns and Ortiz[1] gave algorithms for approximate CE in a generalized Arrow-Debreu market in which agents are located on a graph and trade may occur only between neighboring agents. They considered non-linear utilities.

Exact CE

edit

Jain[2] presented the first polynomial-time algorithm for computing an exact CE when all agents have linear utilities. His algorithm is based on solving a convex program using the ellipsoid method and simultaneous diophantine approximation. He also proved that the set of assignments at equilibrium is convex, and the equilibrium prices themselves are log-convex.

Based on Jain's algorithm, Ye[3] developed a more practical interior-point method for finding a CE.

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

  • When the utilities are SPLC (Separable Piecewise-Linear Concave) and either n or m is a constant, their algorithm is polynomial in the other parameter. The technique is decomposing the space of possible prices into cells using a constant number of hyperplanes, so that in each cell, each buyer’s threshold marginal utility is known. When both n and m are variable, it was left open whether a polytime algorithm exists. Later, Chen, Dai, Du and Teng[5] proved that, with SPLC utilities, computing a CE is PPAD-hard. Their proof shows also that this market-equilibrium problem does not have an FPTAS unless PPAD is contained in P.
  • When the utilities are PLC (Piecewise-Linear Concave, but not necessarily separable) and m is constant, their algorithm is polynomial in n. But when both m and n are variable, finding a CE is PPAD-hard even for Leontief utilities, which are a special case of PLC utilities (when n is constant but m is variable, it was left open whether a polytime algorithm exists).

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

Chaudhury, Garg, McGlaughlin and Mehta[7] prove that, when the products are bads, computing an equilibrium is PPAD-hard even when utilities are linear, and even under a certain condition that guarantees CE existence.

CE for markets with production

edit

Newman and Primak[8] studied two variants of the ellipsoid method for finding an approximate CE in an Arrow-Debreu market with production, when all agents have linear utilities. They proved that the inscribed ellipsoid method is more computationally efficient than the circumscribed ellipsoid method.

edit

A Fisher market is a simpler market in which agents are only buyers - not sellers. Each agent comes with a pre-specified budget, and can use it to buy goods at the given price.

In a Fisher market, increasing prices always decreases the agents' demand, as they can buy less with their fixed budget. However, in an Arrow-Debreu exchange market, increasing prices also increases the agents' budgets, which means that the demand is not a monotone function of the prices. This makes computing a CE in an Arrow-Debreu exchange market much more challenging.[2]

References

edit
  1. ^ Kakade, Sham M.; Kearns, Michael; Ortiz, Luis E. (2004). Shawe-Taylor, John; Singer, Yoram (eds.). "Graphical Economics". Learning Theory. Lecture Notes in Computer Science. 3120. Berlin, Heidelberg: Springer: 17–32. doi:10.1007/978-3-540-27819-1_2. ISBN 978-3-540-27819-1.
  2. ^ a b 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.
  3. ^ Ye, Yinyu (2005). Megiddo, Nimrod; Xu, Yinfeng; Zhu, Binhai (eds.). "Computing the Arrow-Debreu Competitive Market Equilibrium and Its Extensions". Algorithmic Applications in Management. Berlin, Heidelberg: Springer: 3–5. doi:10.1007/11496199_2. ISBN 978-3-540-32440-9.
  4. ^ Devanur, N. R.; Kannan, R. (2008-10-01). "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.
  5. ^ Chen, X.; Dai, D.; Du, Y.; Teng, S. (2009-10-01). "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.
  6. ^ Codenotti, Bruno; McCune, Benton; Penumatcha, Sriram; Varadarajan, Kasturi (2005). Sarukkai, Sundar; Sen, Sandeep (eds.). "Market Equilibrium for CES Exchange Economies: Existence, Multiplicity, and Computation". FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science. 3821. Berlin, Heidelberg: Springer: 505–516. doi:10.1007/11590156_41. ISBN 978-3-540-32419-5.
  7. ^ Chaudhury, Bhaskar Ray; Garg, Jugal; McGlaughlin, Peter; Mehta, Ruta (2020-08-01). "Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chores". arXiv:2008.00285 [cs.GT].
  8. ^ Newman, D. J.; Primak, M. E. (1992-12-01). "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.