his paper considers the tradeoff between divisibility and the hardness of approximating equilibrium prices. Tight bounds are obtained for smooth Fisher markets that obey a relaxed weak gross substitutes property (WGS). A smooth market is one in which small changes in prices cause only proportionately small changes in demand, which we capture by a parameter k. Specifically, assuming that the total wealth is at least r times the total number of goods, this paper gives a polynomial time algorithm to compute prices achieving a (1 - O(k/r)) - approximation and shows that it is NP-hard to do better. A second contribution of this paper is a new consideration of how to measure the quality of an approximation to equilibrium prices. Our approach takes the notion of compensatory payments from welfare economics and applies it to indivisible markets. This allows the dissatisfaction, or discontent, of individual agents to be combined in a natural way. In addition, an important observation is that in the indivisible setting, standard utility functions, such as CES, need not obey the standard WGS property.

This paper considers the tradeoff between divisibility and the hardness of approximating
equilibrium prices. Tight bounds are obtained for smooth Fisher markets that obey a relaxed
weak gross substitutes property (WGS). A smooth market is one in which small changes in
prices cause only proportionately small changes in demand, which we capture by a parameter
k. Specifically, assuming that the total wealth is at least r times the total number of goods,
this paper gives a polynomial time algorithm to compute prices achieving a (1 ? O(k/r)) -
approximation and shows that it is NP-hard to do better.

A second contribution of this paper is a new consideration of how to measure the quality of an approximation to equilibrium prices. Our approach takes the notion of compensatory payments from welfare economics and applies it to indivisible markets. This allows the dissatisfaction, or discontent, of individual agents to be combined in a natural way. In addition, an important observation is that in the indivisible setting, standard utility functions, such as CES, need not obey the standard WGS property.