Dynamic Resource Allocation Games
Dynamic Resource Allocation Games
复制标题
动态资源分配博弈
DOI：
10.1007/978-3-662-53354-3_13
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
O. Kupferman
中科院分区：
文献类型：
--
作者：
Guy Avni;T. Henzinger;O. Kupferman
在资源分配博弈中，自私的参与者共享实现其目标所需的资源。使用资源的成本取决于资源的负载。在传统环境中，玩家同时一次性做出选择。也就是说，玩家的策略是资源的子集。我们介绍并研究动态资源分配博弈。在这种设置下，游戏分阶段进行。在每个阶段，每个玩家选择一种资源。调度程序规定玩家在一个阶段中进行的顺序，可能会安排多个玩家同时进行。当每个玩家收集到一组实现其目标的资源时，游戏结束。每个玩家的成本取决于这个集合以及其中资源的负载——我们考虑拥塞游戏和成本分摊游戏。我们认为动态设置对于实践中的许多应用来说是合适的设置。我们研究动态资源分配博弈的稳定性，其中适当的稳定性概念是子博弈完美均衡，研究由于自私行为而导致的低效率，还研究动态环境特有的问题，例如对资源选择顺序的约束或找到实现稳定性的调度程序的问题。
Inresource allocation games, selfish players share resources that are needed in order to fulfill their objectives. The cost of using a resource depends on the load on it. In the traditional setting, the players make their choices concurrently and in one-shot. That is, a strategy for a player is a subset of the resources. We introduce and studydynamicresource allocation games. In this setting, the game proceeds in phases. In each phase each player chooses one resource. A scheduler dictates the order in which the players proceed in a phase, possibly scheduling several players to proceed concurrently. The game ends when each player has collected a set of resources that fulfills his objective. The cost for each player then depends on this set as well as on the load on the resources in it – we consider both congestion and cost-sharing games. We argue that the dynamic setting is the suitable setting for many applications in practice. We study the stability of dynamic resource allocation games, where the appropriate notion of stability is that of subgame perfect equilibrium, study the inefficiency incurred due to selfish behavior, and also study problems that are particular to the dynamic setting, like constraints on the order in which resources can be chosen or the problem of finding a scheduler that achieves stability.