Information, Prices, Markets, and Local Algorithms

更广泛的影响我们寻求更好地理解经济活动中价格决定背后的信息传递。经济活动可以被看作是由复杂的交换链或市场组成的，货币和价格是其中必不可少的润滑剂。我们的工作假设和动机是，在实际经济中，参与者的行为是由一系列或多或少简单的程序构成的。因此，这项工作的目标是更好地了解价格调整机制，独立运作的每一个价格，但实现协调的结果。本研究主要分为两个部分。为了解释为什么市场经济中的价格变化可能有效地工作，通过显示简单的分布式算法，使价格迅速收敛到均衡值。考虑网络中的价格（收费）设置，部分原因是路由和道路网络。智力优势在这两个领域，重点将是tatonnement风格的算法。这些方法中，每一个价格都是独立调整的。本地算法是特别感兴趣的;这些算法中的价格调整是仅基于相应的价格制定者可用的信息。一个主要的障碍，这种方法是1978年的下限Saari和西蒙这似乎表明，suchalgorithms有过高的信息要求.在这项工作中使用的方法回避了下限，通过使用可变速率更新。以下是将要调查的问题摘要。市场价格连续市场：开发快速，收敛，本地算法，使用基于超额需求的更新。离散市场：商品的不可分割性和价格的离散性对suchalgorithms有什么影响？市场随时间变化：如何将时间纳入模型，以及这如何影响tatonnement算法的属性？生产：将生产纳入模型如何影响tatonnementalgorithms的属性？网络市场：将交易关系视为图表有用吗？这种基于局部变量更新的方法显示出在实现可重构计算更新和产生动态算法（可以有效地响应外部变化，例如公用事业或资源）方面的潜力。网络价格。在这里，当完全了解用户实用程序时，情况就相当好理解了。在这项工作中，重点将放在这些未知或变化的情况下。这就提出了一个问题：什么时候可以根据拥堵中表现出来的用户行为有效地设置通行费？本地tatonnement算法再次主要的兴趣，虽然更多的全球算法，对应于一个单一的网络所有者，也将被考虑。这项工作将研究各种其他问题，包括：用户流量的类型：例如弹性与非弹性流量，可分割与不可分割的需求（需求是一个单一的用户的流量）。流量质量的措施：流量与传输延迟的速率。网络机制：特别是使用缓冲。

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.