Extensions of the spending constraint model: existence and uniqueness of equilibria [Extended Abstract]
Nikhil R. Devanur, V. Vazirani
Jun 9, 2003
Citations
5
Citations
Journal
Journal name not available for this finding
Full text
Semantic Scholar
Key Takeaway Key Takeaway: The spending constraint model supports unique equilibrium prices for continuous and decreasing functions, enabling efficient computation and approximation of market equilibria using discrete techniques.
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