ECCC-Report TR07-017https://eccc.weizmann.ac.il/report/2007/017Comments and Revisions published for TR07-017en-usThu, 08 Mar 2007 00:00:00 +0200
Revision 1
| Indivisible Markets with Good Approximate Equilibrium Prices |
Richard Cole,
Ashish Rastogi
https://eccc.weizmann.ac.il/report/2007/017#revision1his 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.
Thu, 08 Mar 2007 00:00:00 +0200https://eccc.weizmann.ac.il/report/2007/017#revision1
Paper TR07-017
| Indivisible Markets with Good Approximate EquilibriumPrices |
Ashish Rastogi,
Richard Cole
https://eccc.weizmann.ac.il/report/2007/017This 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.
Wed, 07 Mar 2007 23:57:07 +0200https://eccc.weizmann.ac.il/report/2007/017