Information, Prices, Markets, and Local Algorithms

更广泛的影响我们寻求更好地理解经济活动中潜在的价格决定的信息传递。经济活动可以被视为由复杂的交易所或市场链组成，对这些链来说，货币和价格是必不可少的润滑剂。我们的工作假设和动机是，在实际经济中，参与者的行动是由一系列或多或少简单的程序构成的。因此，这项工作的目标是更好地理解价格调整机制，这些机制独立地对每种价格进行操作，但取得协调一致的结果。这项拟议的研究有两个主要部分。i.通过展示简单的分布式算法来解释为什么市场经济中的价格变化可能会有效地发挥作用。ii.考虑网络中的价格(收费)设置，部分原因是路线和公路网。这两个领域的内部优点都将集中在纹身风格的算法上。在这些方法中，每个价格都是独立调整的。当地的算法是特别有意义的；这些算法的价格调整只基于相应的价格制定者可获得的信息。这种方法的障碍是Saari和Simon 1978年的下界，这似乎表明这种算法对信息的要求过高。这项工作中使用的方法通过使用可变速率更新来避开下限。以下是将要研究的问题的摘要I.市场价格连续市场：使用基于过剩需求的更新来开发快速、收敛的本地算法。离散市场：商品的不可分割性和价格的离散性对这样的算法有什么影响？随着时间的推移，市场：如何将时间合并到模型中，以及这如何影响分割算法的特性？生产：将生产纳入模型中如何影响布局算法的特性？网络市场：将交易关系视为图形是否有用？这种基于局部可变更新的方法显示了实现异步扩展、更新、更新的潜力并产生动态算法(即，可以有效地响应外部变化的算法，例如在公用事业或资源方面)。在这里，当充分了解用户实用程序时，情况就相当好地理解了。在这部作品中，重点将放在这些未知或变化的情况上。这项工作的任务是：什么时候可以根据拥塞表现出来的用户行为有效地设置通行费？局部纹身算法再次是一个主要的兴趣，尽管也将考虑与单个网络所有者相对应的更全局的算法。这项工作将研究各种其他问题，包括：用户流量的类型：例如弹性流量和非弹性流量，以及可拆分和不可拆分的需求(ademand是单个用户的流量)。流量质量的测量：流量速率与传输延迟。网络机制：特别是缓冲的使用。

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.