Title

Approximate Solutions of Walrasian Equilibrium Inequalities with Bounded Marginal Utilities of Income

Authors

Donald J. Brown

Document Type

Discussion Paper

Publication Date

8-1-2014

CFDP Number

1955R

CFDP Revision Date

2014-10-01

CFDP Pages

12

Abstract

Recently Cherchye et al. (2011) reformulated the Walrasian equilibrium inequalities, introduced by Brown and Matzkin (1996), as an integer programming problem and proved that solving the Walrasian equilibrium inequalities is NP-hard. Brown and Shannon (2002) derived an equivalent system of equilibrium inequalities, i.e., the dual Walrasian equilibrium inequalities. That is, the Walrasian equilibrium inequalities are solvable iff the dual Walrasian equilibrium inequalities are solvable. We show that solving the dual Walrsian equilibrium inequalities is equivalent to solving a NP-hard minimization problem. Approximation theorems are polynomial time algorithms for computing approximate solutions of NP-hard minimization problems. The primary contribution of this paper is an approximation theorem for the equivalent NP-hard minimization problem. In this theorem, we derive explicit bounds, where the degree of approximation is determined by observable market data.

This document is currently not available here.

Share

COinS