Revision #1 Authors: Richard Cole, Ashish Rastogi

Accepted on: 8th March 2007 00:00

Downloads: 2728

Keywords:

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.

TR07-017 Authors: Ashish Rastogi, Richard Cole

Publication: 7th March 2007 23:57

Downloads: 2976

Keywords:

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.