Information, Prices, Markets, and Local Algorithms

更广泛的影响我们寻求更好地理解经济活动中潜在价格决定的信息传递。经济活动可以被看作是由复杂的交换链或市场组成的，货币和价格是必不可少的润滑剂。我们的工作假设和动机是，一系列或多或少简单的程序构成了实际经济参与者行为的基础。因此，这项工作的目标是更好地理解在每个价格上独立运行但实现协调结果的价格调节机制。本文的研究主要包括两个部分：1。通过展示导致价格迅速向均衡值收敛的简单分布式算法，来解释为什么市场经济中的价格变化可能有效地起作用。考虑路网中价格（通行费）的设置，部分是由路线和道路网络驱动的。在这两个领域中，重点将放在收敛式算法上。在这些方法中，每个价格都是独立调整的。局部算法是特别有趣的；在这些算法中，价格调整仅基于相应的定价者可获得的信息。这种方法的主要障碍是1978年Saari和Simon的下界，这似乎表明这种算法对信息的要求过高。本工作中使用的方法通过使用可变速率更新绕过了这个下限。以下是将要调查的问题摘要。市场价格连续市场：开发快速、收敛的本地算法，使用基于超额需求的更新。离散市场：商品的不可分割性和价格的离散性对这种算法的影响是什么？随时间变化的市场：如何将时间纳入模型，这如何影响控制算法的特性？生产：将生产纳入模型如何影响计算算法的特性？作为网络的市场：把交易关系看作一个图表有用吗？这种基于本地变量更新的方法在支持异步价格更新和生成动态算法（即能够有效响应外部更改，例如实用程序或资源中的更改）方面显示出潜力。网络价格。在这里，当充分了解用户实用程序时，情况就相当好理解了。在这项工作中，重点将放在这些未知或变化的情况上。这项工作的问题是：什么时候才能根据拥堵中表现出来的用户行为有效地设置通行费？局部控制算法也是一个主要的兴趣，尽管更多的全局算法，对应于一个单一的网络所有者，也将被考虑。这项工作将检查各种其他问题，包括：用户流量类型：例如弹性与非弹性流量，可分割与不可分割的需求（需求是单个用户的流量）。交通质量的度量：流量率与交通延误率。网络机制：特别是缓冲的使用。

Broader impact We seek a better understanding of the information transfer underlying price determinationin 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 operateindependently 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 distributedalgorithms 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 inwhich each price is adjusted independently. Local algorithms are of particular interest; these are algorithmsin which the price adjustment is based only on information available to the corresponding price setter. Aprime obstacle to such methods is the 1978 lower bound of Saari and Simon which seemingly shows that suchalgorithms have unduly high information requirements. The approach used in this work sidesteps that lowerbound, by using variable rate updates. The following is a summary of the issues that will be investigated.I. MARKET PRICESContinuous 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 suchalgorithms?Markets over Time: How can time be incorporated into the model, and how does this affect the propertiesof the tatonnement algorithms?Production: How does incorporating production into the model affects the properties of tatonnementalgorithms?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 asynchronousprice 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 userutilities. In this work, the focus will be on the situation when these are unknown or changing. This workasks: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 toa 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 (ademand is a single user's traffic).Measures of traffic quality: rates of flow versus transit delays.Network mechanisms: In particular, the use of buffering.