• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Proceedings of the 12th ACM conference on electronic commerce. >Distributed Algorithms via Gradient Descent for Fisher Markets
【24h】

Distributed Algorithms via Gradient Descent for Fisher Markets

机译：费希尔市场通过梯度下降的分布式算法

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Designing distributed algorithms that converge quickly to an equilibrium is one of the foremost research goals in algorithmic game theory, and convex programs have played a crucial role in the design of algorithms for Fisher markets. In this paper we shed new light on both aspects for Fisher markets with linear and spending constraint utilities. We show fast convergence of the Proportional Response dynamics recently introduced by Wu and Zhang [WZ07]. The convergence is obtained from a new perspective: we show that the Proportional Response dynamics is equivalent to a gradient descent algorithm (with respect to a Bregman divergence instead of euclidean distance) on a convex program that captures the equilibria for linear utilities. We further show that the convex program program easily extends to the case of spending constraint utilities, thus resolving an open question raised by [VazlO]. This also gives a way to extend the Proportional Response dynamics to spending constraint utilties. We also prove a technical result that is interesting in its own right: that the gradient descent algorithm based on a Bregman divergence converges with rate O(1/t) under a condition that is weaker than having Lipschitz continuous gradient (which is the usual assumption in the optimization literature for obtaining the same rate).
机译：设计快速收敛到平衡的分布式算法是算法博弈论的首要研究目标之一，凸程序在Fisher市场算法的设计中起着至关重要的作用。在本文中，我们通过线性和支出约束效用为费希尔市场的两个方面提供了新的思路。我们展示了Wu和Zhang [WZ07]最近引入的比例响应动力学的快速收敛。从一个新的角度获得了收敛性：我们证明了在捕获线性效用均衡的凸程序上，比例响应动力学等效于梯度下降算法（相对于布雷格曼散度而不是欧氏距离）。我们进一步表明，凸程序程序很容易扩展到支出约束工具的情况，从而解决了[VazlO]提出的一个开放性问题。这也提供了一种将比例响应动力学扩展到支出约束工具的方法。我们还证明了其本身有趣的技术结果：基于Bregman发散的梯度下降算法在比Lipschitz连续梯度弱的条件下以速率O（1 / t）收敛（这是通常的假设）在优化文献中获得相同的费率）。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号