Dynamic resource allocation games

Guy , Avni and Thomas A., Henzinger and Orna, Kupferman (2016) Dynamic resource allocation games. In: SAGT: Symposium on Algorithmic Game Theory, September 19-21, 2016 , Liverpool, United Kingdom .

[img] Text
sagt-cr.pdf - Accepted Version
Available under License All rights reserved.
Download (237Kb)
Official URL: http://link.springer.com/chapter/10.1007%2F978-3-6...


In resource 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 study dynamic resource 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.

Item Type: Conference or Workshop Item (Paper)
Additional Information: The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-53354-3_13.
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
Research Group: Henzinger Group
Depositing User: Guy Avni
Date Deposited: 25 Oct 2016 07:13
Last Modified: 04 May 2017 11:16
URI: https://repository.ist.ac.at/id/eprint/645

Actions (login required)

View Item View Item