IIT Home Page CNR Home Page

Computation of Market Equilibria via the Excess Demand Function

We consider the computation of equilibria for exchange economies. The general problem is unlikely to admit efficient algorithms. We develop and adapt a number of tools which allow us to take advantage of the structure of equilibria, when the market satisfies a property, called weak gross substitutability, which guarantees that the equilibria form a convex set. Using these tools we derive two polynomial time algorithms: the first one is a simple and efficient discrete version of the t?atonnement process, while the second one is based on the Ellipsoid method, and achieves a better dependence on the approximation parameter. Our approach does not make use of the specific form of the utility functions of the individual traders, and it is thus more general than previous work.


Autori IIT:

Tipo: TR Rapporti tecnici
Area di disciplina: Information Technology and Communication Systems
IIT TR-26/2010