...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Theory of Computing >Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games
【24h】

Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games

机译：没有遗憾的情况下进行选路：选路游戏中使后悔最小化算法收敛到Nash均衡

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

There has been substantial work developing simple, efficient regret-minimizing algorithms for a wide class of repeated decision-makingproblems including online routing. These are adaptive strategies anindividual can use that give strong guarantees on performanceeven in adversarially-changing environments. There has also beensubstantial work on analyzing properties of Nash equilibria in routinggames. In this paper, we consider the question: if each player in arouting game uses a regret-minimizing strategy, will behavior converge to a Nash equilibrium? In general games the answer to this question is known to be no in a strong sense, but routing games have substantially more structure.In this paper we show that in the Wardrop setting of multicommodity flowand infinitesimal agents, behavior will approach Nash equilibrium(on most days, the cost of the flow will be close to the costof the cheapest paths possible given that flow) at a rate that dependspolynomially on the players' regret bounds and the maximum slope of anylatency function. We also show that Price of Anarchy results may beapplied to these approximate equilibria, and also consider thefinite-size (non-infinitesimal) load-balancing model of Azar (1998).Our nonatomic results also apply to the more general classof congestion games.
机译：针对包括在线路由在内的各种重复决策问题，开发简单，有效的后悔最少算法的工作量很大。这些是个人可以使用的自适应策略，即使在对抗性不断变化的环境中也可以为性能提供强有力的保证。在路由游戏中分析纳什均衡的性质方面也进行了大量工作。在本文中，我们考虑的问题是：如果引起骚扰的每个玩家都使用最小化后悔的策略，行为会收敛到纳什均衡吗？在一般游戏中，这个问题的答案不是很强，但路由游戏具有更大的结构。本文证明了在多商品流和无穷小代理人的Wardrop设置中，行为将达到Nash平衡（在大多数情况下在几天之内，流量的成本将接近于最便宜路径的成本（在给定流量的情况下），其速率取决于玩家的后悔界限和任意延迟函数的最大斜率。我们还表明，无政府状态的价格结果可能适用于这些近似均衡，并且还考虑了Azar（1998）的有限大小（非无限小）负载平衡模型。我们的非原子性结果也适用于更一般的拥塞游戏。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号