论文标题
动态网络拥堵游戏
Dynamic network congestion games
论文作者
论文摘要
拥堵游戏是一种在游戏理论中研究的古典游戏类型，其中n个玩家选择了一种资源，而他们的个人成本随着其他选择相同资源的数量而增加。在网络拥堵游戏（NCGS）中，资源对应于图中的简单路径，例如表示从源到目标的路由选项。在本文中，我们介绍了一种NCG的变体，称为动态NCGS：在这种情况下，玩家同步进行过渡，他们动态选择了下一个过渡，并且他们的费用取决于同时使用同一过渡的玩家数量。 从复杂的角度来看，我们在动态NCG中研究游戏理论的标准概念：社交Optima，Nash Equilibria和子游戏中的完美平衡。我们的贡献如下：在PSPACE和NP-HARD中存在具有社会成本的战略状况。 （纯）NASH平衡始终存在于动态NCG中；可以在expspace中决定具有有限成本的NASH平衡，并且可以在双重指数时间内计算见证策略概况。可以在2个空间中确定具有有限成本的子游戏的完美平衡的存在，并且可以在三重指数时间内计算见证策略概况。
Congestion games are a classical type of games studied in game theory, in which n players choose a resource, and their individual cost increases with the number of other players choosing the same resource. In network congestion games (NCGs), the resources correspond to simple paths in a graph, e.g. representing routing options from a source to a target. In this paper, we introduce a variant of NCGs, referred to as dynamic NCGs: in this setting, players take transitions synchronously, they select their next transitions dynamically, and they are charged a cost that depends on the number of players simultaneously using the same transition. We study, from a complexity perspective, standard concepts of game theory in dynamic NCGs: social optima, Nash equilibria, and subgame perfect equilibria. Our contributions are the following: the existence of a strategy profile with social cost bounded by a constant is in PSPACE and NP-hard. (Pure) Nash equilibria always exist in dynamic NCGs; the existence of a Nash equilibrium with bounded cost can be decided in EXPSPACE, and computing a witnessing strategy profile can be done in doubly-exponential time. The existence of a subgame perfect equilibrium with bounded cost can be decided in 2EXPSPACE, and a witnessing strategy profile can be computed in triply-exponential time.
