Journal article
An experimental study of different approaches to solve the market equilibrium problem
The ACM journal of experimental algorithmics, Vol.12, pp.1-21
06/2008
DOI: 10.1145/1227161.1402295
Abstract
Over the last few years, the problem of computing market equilibrium prices for exchange economies has received much attention in the theoretical computer science community. Such activity led to a flurry of polynomial time algorithms for various restricted, yet significant, settings. The most important restrictions arise either when the traders' utility functions satisfy a property known as gross substitutability or when the initial endowments are proportional (the Fisher model). In this paper, we experimentally compare the performance of some of these recent algorithms against that of the most used software packages. In particular, we evaluate the following approaches: (1) the solver PATH, available under GAMS/MPSGE, a popular tool for computing market equilibrium prices; (2) a discrete version of a simple iterative price update scheme called tâtonnement; (3) a discrete version of the welfare adjustment process; (4) convex feasibility programs that characterize the equilibrium in some special cases. We analyze the performance of these approaches on models of exchange economies where the consumers are equipped with utility functions, which are widely used in real world applications. The outcomes of our experiments consistently show that many market settings allow for an efficient computation of the equilibrium, well beyond the restrictions under which the theory provides polynomial time guarantees. For some of the approaches, we also identify models where they are are prone to failure.
Details
- Title: Subtitle
- An experimental study of different approaches to solve the market equilibrium problem
- Creators
- Bruno Codenotti - IIT-CNR, Pisa, ItalyBenton Mccune - University of IowaSriram Pemmaraju - University of IowaRajiv Raman - University of IowaKasturi Varadarajan - University of Iowa
- Resource Type
- Journal article
- Publication Details
- The ACM journal of experimental algorithmics, Vol.12, pp.1-21
- DOI
- 10.1145/1227161.1402295
- ISSN
- 1084-6654
- eISSN
- 1084-6654
- Grant note
- DOI: 10.13039/100000001, name: National Science Foundation, award: CCR-0237431
- Language
- English
- Date published
- 06/2008
- Academic Unit
- Computer Science
- Record Identifier
- 9984259496902771
Metrics
1 Record Views