首页    期刊浏览 2024年09月07日 星期六
登录注册

文章基本信息

  • 标题:Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games
  • 本地全文:下载
  • 作者:Avrim Blum ; Eyal Even-Dar ; Katrina Ligett
  • 期刊名称:Theory of Computing
  • 印刷版ISSN:1557-2862
  • 电子版ISSN:1557-2862
  • 出版年度:2010
  • 卷号:6
  • 出版社:University of Chicago
  • 摘要:

    There has been substantial work developing simple, efficient regret-minimizing algorithms for a wide class of repeated decision-making problems including online routing. These are adaptive strategies an individual can use that give strong guarantees on performance even in adversarially-changing environments. There has also been substantial work on analyzing properties of Nash equilibria in routing games. In this paper, we consider the question: if each player in a routing 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.

  • 关键词:regret minimization, Nash equilibria, routing games
国家哲学社会科学文献中心版权所有