Arrow–Debreu exchange market explained

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:

m

divisible products.

n

agents.

i=1,...,n

, has an endowment

ei

, which is a set of products.

Each product

j

has a price

pj

; 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

x=x1,...,xm

, where

xj

is the quantity of product

j

. So the price of a bundle

x

is

px

m
=\sum
j=1

pjxj

.

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

pei

.

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

x

is affordable for buyer

i

if

px\leqpei

.

Each buyer has a preference relation over bundles, which can be represented by a utility function. The utility function of buyer

i

is denoted by

ui

. The demand set of a buyer is the set of affordable bundles that maximize the buyer's utility among all affordable bundles, i.e.:

Demandi(p):=

\argmax
px\leqpei

ui(x)

.

A competitive equilibrium (CE) is a price-vector

p1,...,pm

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

Approximate CE

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

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

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

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.

Related models

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.

Notes and References

  1. Kakade . Sham M. . Kearns . Michael . Ortiz . Luis E. . 2004 . Shawe-Taylor . John . Singer . Yoram . Graphical Economics . Learning Theory . Lecture Notes in Computer Science . en . Berlin, Heidelberg . Springer . 3120 . 17–32 . 10.1007/978-3-540-27819-1_2 . 978-3-540-27819-1.
  2. Jain . Kamal . January 2007 . A Polynomial Time Algorithm for Computing an Arrow–Debreu Market Equilibrium for Linear Utilities . SIAM Journal on Computing . en . 37 . 1 . 303–318 . 10.1137/S0097539705447384 . 0097-5397.
  3. Ye . Yinyu . 2005 . Megiddo . Nimrod . Xu . Yinfeng . Zhu . Binhai . Computing the Arrow-Debreu Competitive Market Equilibrium and Its Extensions . Algorithmic Applications in Management . en . Berlin, Heidelberg . Springer . 3–5 . 10.1007/11496199_2 . 978-3-540-32440-9.
  4. Book: Devanur . N. R. . 2008 49th Annual IEEE Symposium on Foundations of Computer Science . Kannan . R. . 2008-10-01 . 978-0-7695-3436-7 . 45–53 . Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents . 10.1109/FOCS.2008.30 . https://ieeexplore.ieee.org/document/4690939 . 13992175.
  5. Book: Chen . X. . 2009 50th Annual IEEE Symposium on Foundations of Computer Science . Dai . D. . Du . Y. . Teng . S. . 2009-10-01 . 978-1-4244-5116-6 . 273–282 . Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities . 10.1109/FOCS.2009.29 . https://ieeexplore.ieee.org/document/5438624 . 0904.0644 . 580788.
  6. Codenotti . Bruno . McCune . Benton . Penumatcha . Sriram . Varadarajan . Kasturi . 2005 . Sarukkai . Sundar . Sen . Sandeep . 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 . en . Berlin, Heidelberg . Springer . 3821 . 505–516 . 10.1007/11590156_41 . 978-3-540-32419-5.
  7. 2008.00285 . cs.GT . Bhaskar Ray . Chaudhury . Jugal . Garg . Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chores . 2020-08-01 . McGlaughlin . Peter . Mehta . Ruta.
  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 . 10.1016/0096-3003(92)90079-G . 0096-3003.