2005/05/22 by Bruno Codenotti, Benton McCune, Kasturi Varadarajan · 2 citations
Economics, Econometrics and Finance · Decision Sciences · #Economic theories and models #Game Theory and Applications #Economic Theory and Policy
paper · doi:10.1145/1060590.1060601
openalex publication_date 2005/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We consider the problem of computing market equilibria and show three results. (i) For exchange economies satisfying weak gross substitutability we analyze a simple discrete version of tâtonnement, and prove that it converges to an approximate equilibrium in polynomial time. This is the first polynomial-time approximation scheme based on a simple tâtonnement process. It was only recently shown, using vastly more sophisticated techniques, that an approximate equilibrium for this class of economies is computable in polynomial time. (ii) For Fisher’s model, we extend the frontier of tractability by developing a polynomial-time algorithm that applies well beyond the homothetic case and the gross substitutes case. (iii) For production economies, we obtain the first polynomial-time algorithms for computing an approximate equilibrium when the consumers ’ side of the economy satisfies weak gross substitutability and the producers’ side is restricted to positive production.