An impossibility theorem for price-adjustment mechanisms

We show that there is no discrete-time price-adjustment mechanism (any process that at each period looks at the history of prices and excess demands and updates the prices) such that for any market (a set of goods and consumers with endowments and strictly concave utilities) the price-adjustment mechanism will achieve excess demands that are at most an epsilon fraction of the total supply within a number of periods that is polynomial in the number of goods and 1/epsilon. This holds even if one restricts markets so that excess demand functions are differentiable with derivatives bounded by a small constant. For the convergence time to the actual price equilibrium, we show by a different method a stronger result: Even in the case of three goods with a unique price equilibrium, there is no function of epsilon that bounds the number of periods needed by a price-adjustment mechanism to arrive at a set of prices that is epsilon-close to the equilibrium.