View source for Arrow–Debreu exchange market


{{Distinguish|Exchange (organized 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 <math>m</math> divisible products.
* A set of <math>n</math> agents.
* Each agent <math>i=1,\dots,n</math>, has an ''endowment'' <math>e_i</math>, which is a set of products.

Each product <math>j</math> has a price <math>p_j</math>; 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 <math>x = x_1,\dots,x_m</math>, where <math>x_j</math> is the quantity of product <math>j</math>. So the price of a bundle <math>x</math> is <math>p\cdot x =\sum_{j=1}^m p_j\cdot x_j</math>.

Given a price-vector, the ''budget'' of an agent is the total price of his endowment, <math>p\cdot e_i</math>.

A bundle is ''affordable'' for a buyer if the price of that bundle is at most the buyer's budget. I.e, a bundle <math>x</math> is affordable for buyer <math>i</math> if <math>p\cdot x\leq p\cdot e_i</math>.

Each buyer has a [[Preference (economics)|preference relation]] over bundles, which can be represented by a utility function. The utility function of buyer <math>i</math> is denoted by <math>u_i</math>.  The ''demand set'' of a buyer is the set of affordable bundles that maximize the buyer's utility among all affordable bundles, i.e.:

<math>\text{Demand}_i(p) := \arg\max_{p\cdot x\leq p\cdot e_i} u_i(x)</math>.

A '''[[competitive equilibrium]]''' (CE) is a price-vector <math>p_1,\dots,p_m</math>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<ref>{{Cite journal |last1=Kakade |first1=Sham M. |last2=Kearns |first2=Michael |last3=Ortiz |first3=Luis E. |date=2004 |editor-last=Shawe-Taylor |editor-first=John |editor2-last=Singer |editor2-first=Yoram |title=Graphical Economics |url=https://link.springer.com/chapter/10.1007/978-3-540-27819-1_2 |journal=Learning Theory |series=Lecture Notes in Computer Science |language=en |location=Berlin, Heidelberg |publisher=Springer |volume=3120 |pages=17–32 |doi=10.1007/978-3-540-27819-1_2 |isbn=978-3-540-27819-1}}</ref> 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<ref name=":0">{{Cite journal |last=Jain |first=Kamal |date=January 2007 |title=A Polynomial Time Algorithm for Computing an Arrow–Debreu Market Equilibrium for Linear Utilities |url=http://epubs.siam.org/doi/10.1137/S0097539705447384 |journal=SIAM Journal on Computing |language=en |volume=37 |issue=1 |pages=303–318 |doi=10.1137/S0097539705447384 |issn=0097-5397}}</ref> 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 [[Logarithmically convex function|log-convex]].  

Based on Jain's algorithm, Ye<ref>{{Cite journal |last=Ye |first=Yinyu |date=2005 |editor-last=Megiddo |editor-first=Nimrod |editor2-last=Xu |editor2-first=Yinfeng |editor3-last=Zhu |editor3-first=Binhai |title=Computing the Arrow-Debreu Competitive Market Equilibrium and Its Extensions |url=https://link.springer.com/chapter/10.1007/11496199_2 |journal=Algorithmic Applications in Management |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=3–5 |doi=10.1007/11496199_2 |isbn=978-3-540-32440-9}}</ref> developed a more practical [[interior-point method]] for finding a CE. 

Devanur and Kannan<ref name=":02">{{Cite book |last1=Devanur |first1=N. R. |title=2008 49th Annual IEEE Symposium on Foundations of Computer Science |last2=Kannan |first2=R. |date=2008-10-01 |isbn=978-0-7695-3436-7 |pages=45–53 |chapter=Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents |doi=10.1109/FOCS.2008.30 |chapter-url=https://ieeexplore.ieee.org/document/4690939 |s2cid=13992175}}</ref> gave algorithms for exchange markets with [[Concave function|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<ref>{{Cite book |last1=Chen |first1=X. |title=2009 50th Annual IEEE Symposium on Foundations of Computer Science |last2=Dai |first2=D. |last3=Du |first3=Y. |last4=Teng |first4=S. |date=2009-10-01 |isbn=978-1-4244-5116-6 |pages=273–282 |chapter=Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities |doi=10.1109/FOCS.2009.29 |chapter-url=https://ieeexplore.ieee.org/document/5438624 |arxiv=0904.0644 |s2cid=580788}}</ref> 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<ref>{{Cite journal |last1=Codenotti |first1=Bruno |last2=McCune |first2=Benton |last3=Penumatcha |first3=Sriram |last4=Varadarajan |first4=Kasturi |date=2005 |editor-last=Sarukkai |editor-first=Sundar |editor2-last=Sen |editor2-first=Sandeep |title=Market Equilibrium for CES Exchange Economies: Existence, Multiplicity, and Computation |url=https://link.springer.com/chapter/10.1007/11590156_41 |journal=FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science |series=Lecture Notes in Computer Science |language=en |location=Berlin, Heidelberg |publisher=Springer |volume=3821 |pages=505–516 |doi=10.1007/11590156_41 |isbn=978-3-540-32419-5}}</ref> gave an algorithm for Arrow-Debreu markes with [[Constant elasticity of substitution|CES utilities]] where the elasticity of substitution is at least 1/2.

Chaudhury, Garg, McGlaughlin and Mehta<ref name=":1">{{cite arXiv |eprint=2008.00285 |class=cs.GT |first1=Bhaskar Ray |last1=Chaudhury |first2=Jugal |last2=Garg |title=Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chores |date=2020-08-01 |last3=McGlaughlin |first3=Peter |last4=Mehta |first4=Ruta}}</ref> 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<ref>{{Cite journal |last=Newman |first=D. J. |last2=Primak |first2=M. E. |date=1992-12-01 |title=Complexity of circumscribed and inscribed ellipsoid methods for solving equilibrium economical models |url=https://www.sciencedirect.com/science/article/pii/009630039290079G |journal=Applied Mathematics and Computation |volume=52 |issue=2 |pages=223–231 |doi=10.1016/0096-3003(92)90079-G |issn=0096-3003}}</ref> 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.<ref name=":0" />

== References ==
{{Reflist}}


[[Category:Financial models]]
[[Category:Market (economics)]]
[[Category:General equilibrium theory]]