Dynamics of Distributed Updating in Fisher Markets
Dynamics of Distributed Updating in Fisher Markets
复制标题
渔市分布式更新动态
DOI：
10.1145/3219166.3219189
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Yixin Tao
中科院分区：
文献类型：
--
作者：
Yun Kuen Cheung;R. Cole;Yixin Tao
算法博弈论的一个主要目标是从算法和复杂性的角度证明均衡概念的合理性。一种吸引人的方法是确定快速收敛到均衡的自然分布式算法。本文建立了买方具有CES效用函数的Fisher市场中比例响应的两个推广的新的收敛结果。起点分别是这类市场的一个新凸公式和一个新凸凹公式。这两个推广对应于应用于这些公式的适当的镜像下降算法。我们的几个新结果是强Bregman凸性和强Bregman凸凹函数的新概念的结果，以及相关的线性收敛速度，这可能是独立的兴趣。在其他结果中，我们分析了有阻尼项的广义比例响应，并证明了在一个Fisher市场中，买家的效用函数覆盖了CES效用的全部谱，而不是线性效用和Leontief效用的极值，我们得到了一个线性收敛速度；当考虑这些效用时，我们得到了一个经验的$O(1/T)$收敛速度。
A major goal in Algorithmic Game Theory is to justify equilibrium concepts from an algorithmic and complexity perspective. One appealing approach is to identify natural distributed algorithms that converge quickly to an equilibrium. This paper established new convergence results for two generalizations of proportional response in Fisher markets with buyers having CES utility functions. The starting points are respectively a new convex and a new convex-concave formulation of such markets. The two generalizations correspond to suitable mirror descent algorithms applied to these formulations. Several of our new results are a consequence of new notions of strong Bregman convexity and of strong Bregman convex-concave functions, and associated linear rates of convergence, which may be of independent interest. Among other results, we analyze a damped generalized proportional response and show a linear rate of convergence in a Fisher market with buyers whose utility functions cover the full spectrum of CES utilities aside the extremes of linear and Leontief utilities; when these utilities are included, we obtain an empirical $O(1/T)$ rate of convergence.