Congestion games with mixed objectives

被引：0
作者：
Matthias Feldotto
Lennart Leder
Alexander Skopalik
机构：
[1] Paderborn University,
来源：
Journal of Combinatorial Optimization | 2018年 / 36卷
关键词：
Congestion games; Bottleneck congestion games; Pure Nash equilibrium; Existence; Convergence; Complexity; Approximation;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the (non-)existence of pure Nash equilibria (PNE), the convergence of improvement dynamics, the quality of equilibria and show the complexity of the decision problem. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.
引用
收藏
页码：1145 / 1167
页数：22
相关论文
共 39 条
  • [1] Ackermann H(2009)Pure nash equilibria in player-specific and weighted congestion games Theor Comput Sci 410 1552-1563
  • [2] Röglin H(2008)On the impact of combinatorial structure on congestion games J ACM 55 25:1-25:22
  • [3] Vöcking B(2008)Complexity of pure nash Equilibria in player-specific network congestion games Internet Math 5 323-342
  • [4] Ackermann H(2007)Bottleneck routing games in communication networks IEEE J Sel Areas Commun 25 1173-1179
  • [5] Röglin H(2015)Approximate pure Nash equilibria in weighted congestion games: existence, efficient computation, and structure ACM Trans Econ Comput 3 1-2
  • [6] Vöcking B(2011)Convergence to approximate nash equilibria in congestion games Games Econ Behav 71 315-327
  • [7] Ackermann H(2012)Bottleneck links, variable demand, and the tragedy of the commons Networks 60 194-203
  • [8] Skopalik A(2008)On the complexity of pure-strategy Nash equilibria in congestion and local-effect games Math Oper Res 33 851-868
  • [9] Banner R(1980)The directed subgraph homeomorphism problem Theor Comput Sci 10 111-121
  • [10] Orda A(2005)Selfish unsplittable flows Theor Comput Sci 348 226-239
1234