Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR07-017 | 8th March 2007 00:00

Indivisible Markets with Good Approximate Equilibrium Prices

RSS-Feed




Revision #1
Authors: Richard Cole, Ashish Rastogi
Accepted on: 8th March 2007 00:00
Downloads: 1055
Keywords: 


Abstract:

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.


Paper:

TR07-017 | 18th January 2007 00:00

Indivisible Markets with Good Approximate EquilibriumPrices





TR07-017
Authors: Ashish Rastogi, Richard Cole
Publication: 7th March 2007 23:57
Downloads: 1222
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint