Nikhil R. Devanur, V. Vazirani

Jun 9, 2003

Citations

5

Citations

Journal

Journal name not available for this finding

Abstract

Although the study of market equilibria has occupied a central place within mathematical economics for over a century, polynomial time algorithms for such issues have started emerging only recently [6, 5, 8]. However, it is worth noting that whereas the traditional theory of market equilibria was built around tools from the fields of analysis and topology, we are attempting to build an algorithmic theory using discrete techniques, and traditional models and notions may not be amenable to such an extension. Indeed, once the case of linear utility functions was solved [5], handling more complex utility functions required modifying the traditional model [8]. The modification is small, though fundamental, so that the resulting model also appears to be quite basic. Under this model, called the spending constraint model, utilities are specified not as a function of the amount of good obtained, but as a function of the amount of budget spent on that good. The model is a natural one, since people typically do have an estimate, either implicit or explicit, on how much they are willing to spend on each good. [8] gives a polynomial time algorithm for the special case of decreasing step functions in this model. Two questions arise naturally: For more general utility functions in this model, can existence of equilibrium prices be established using traditional tools? If so, can they be computed or approximated efficiently by either extending or using the algorithm of [8]? In this paper, we provide affirmative answers to both questions for the case of continuous and decreasing functions. Additionally, we show that this model supports unique equilibrium prices, unlike the traditional model (a proof of uniqueness for decreasing step functions was given in [8]). Note that models yielding unique equilibrium prices have been considered desirable since this is another indication of stability in markets [2, 4]. The model proposed in [8] can be thought of as the spending constraint extension of Fisher’s setting (see Section 2). In this paper, we define the spending constraint extension

Text copied to clipboard

copied to clipboard