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:
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.
Kakade, Kearns and Ortiz 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.
Jain 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 developed a more practical interior-point method for finding a CE.
Devanur and Kannan gave algorithms for exchange markets with concave utility functions, where all resources are goods (the utilities are positive):
Codenotti, McCune, Penumatcha and Varadarajan 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 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.
Newman and Primak 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.
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.