Fast-converging tatonnement algorithms for one-time and ongoing market problems
Fast-converging tatonnement algorithms for one-time and ongoing market problems
复制标题
针对一次性和持续市场问题的快速收敛塔顿算法
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
L. Fleischer
中科院分区：
文献类型：
--
作者：
R. Cole;L. Fleischer
为什么市场会趋向并保持在均衡价格附近？为了从算法的角度阐明这个问题，本文形式化了持续市场的设置，与经典的市场场景形成对比，我们称之为一次性市场。持续市场允许以非均衡价格进行交易，正如它的名字所暗示的那样，它会持续一段时间。因此，它似乎是一个更合理的实际市场模型。对于这两种市场设置，本文定义并分析了一种简单的补偿算法的变体，该算法与之前的算法在三个重要方面有所不同，这些算法已经接受了渐近分析：一种商品的价格更新仅取决于该商品的价格、需求和供应，而不依赖于其他信息；每种商品的价格更新是分布式和异步的；算法从一个任意的起点起作用（分析也成立）。我们的算法引入了一个新的自然更新规则。我们表明，在满足弱总替代性质的广泛市场中，这一更新规则导致了向均衡价格的快速收敛。这是第一次分析计算和信息分布式算法，证明多项式收敛。我们的分析确定了市场特征的三个参数，这些参数决定了我们协议的趋同速度。这些参数大致是：1。每种商品的需求变动相对于其价格变动的零碎比率的界限。2. 每一种商品的需求变动率相对于财富的变动率的分界。3. 市场与费雪市场的接近程度（买者一开始只带钱）。我们给出了两种协议。第一种类型假设只有第一个参数的全局知识（上界）。对于该协议，我们还根据这些参数为一次性市场提供了一个匹配的下界。我们的第二个协议仅针对一次性市场进行分析，它没有假设任何全局知识。
Why might markets tend toward and remain near equilibrium prices? In an effort to shed light on this question from an algorithmic perspective, this paper formalizes the setting of Ongoing Markets, by contrast with the classic market scenario, which we term One-Time Markets. The Ongoing Market allows trade at non-equilibrium prices, and, as its name suggests, continues over time. As such, it appears to be a more plausible model of actual markets. For both market settings, this paper defines and analyzes variants of a simple tatonnement algorithm that differs from previous algorithms that have been subject to asymptotic analysis in three significant respects: the price update for a good depends only on the price, demand, and supply for that good, and on no other information; the price update for each good occurs distributively and asynchronously; the algorithms work (and the analyses hold) from an arbitrary starting point. Our algorithm introduces a new and natural update rule. We show that this update rule leads to fast convergence toward equilibrium prices in a broad class of markets that satisfy the weak gross substitutes property. These are the first analyses for computationally and informationally distributed algorithms that demonstrate polynomial convergence. Our analysis identifies three parameters characterizing the markets, which govern the rate of convergence of our protocols. These parameters are, broadly speaking: 1. A bound on the fractional rate of change of demand for each good with respect to fractional changes in its price. 2. A bound on the fractional rate of change of demand for each good with respect to fractional changes in wealth. 3. The closeness of the market to a Fisher market (a market with buyers starting with money alone). We give two types of protocols. The first type assumes global knowledge of only (an upper bound on) the first parameter. For this protocol, we also provide a matching lower bound in terms of these parameters for the One-Time Market. Our second protocol, which is analyzed for the One-Time Market alone, assumes no global knowledge whatsoever.