Information, Prices, Markets, and Local Algorithms

New York University, New York NY

Investigators

Abstract

Broader impact We seek a better understanding of the information transfer underlying price determination in economic activity. Economic activity can be seen as comprising complex chains of exchanges, or markets, for which money and prices are the essential lubricant. Our working assumption and motivation is that a collection of more or less simple procedures underlie the actions of participants in the actual economy. Accordingly, the goal of this work is to better understand price adjustment mechanisms that operate independently on each price yet achieve a coordinated outcome. The proposed research has two main parts. I. To explain why price changes in market economies might work effectively by showing simple distributed algorithms that cause prices to converge quickly toward equilibrium values. II. To consider price (toll) setting in networks, motivated in part by routing and road networks. Intelectual merit In both areas, the focus will be on tatonnement-style algorithms. These are methods in which each price is adjusted independently. Local algorithms are of particular interest; these are algorithms in which the price adjustment is based only on information available to the corresponding price setter. A prime obstacle to such methods is the 1978 lower bound of Saari and Simon which seemingly shows that such algorithms have unduly high information requirements. The approach used in this work sidesteps that lower bound, by using variable rate updates. The following is a summary of the issues that will be investigated. I. MARKET PRICES Continuous Markets: Develop fast, convergent, local algorithms, using updates based on excess demand. Discrete Markets: What is the effect of indivisibility of goods and discreteness of prices on such algorithms? Markets over Time: How can time be incorporated into the model, and how does this affect the properties of the tatonnement algorithms? Production: How does incorporating production into the model affects the properties of tatonnement algorithms? Markets as Networks: Is it useful to view trading relationships as a graph? This approach based on local, variable updates shows potential with regard both to enabling asynchronous price updates, and yielding a dynamic algorithm (that is one that can respond effectively to external changes, such as in utilities or resources). II. NETWORK PRICES. Here, the situation is fairly well understood when there is full knowledge of user utilities. In this work, the focus will be on the situation when these are unknown or changing. This work asks: When can tolls be set effectively based on user behavior as manifested in congestion? Local tatonnement algorithms are again a main interest, although more global algorithms, corresponding to a single network owner, will also be considered. This work will examine a variety of other issues including: Types of user traffic: e.g. elastic versus inelastic traffic, and splittable versus unsplittable demands (a demand is a single user's traffic). Measures of traffic quality: rates of flow versus transit delays. Network mechanisms: In particular, the use of buffering.