Resource buying games
| Speaker: | Levent Tunçel |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
In resource buying games, the players jointly buy a subset of a given resource set (e.g., machines, edges, etc.). Just like in classical congestion games, each player has a predefined family of subsets of the resources from which she needs at least one to be available (e.g., the machines on which the player's job can be processed, or the paths connecting two player-specific terminals in a graph). However, a resource is only available if the sum of payments of all players covers the (load-dependent) cost of that resource. Thus, in these games a strategy of a player is a tuple consisting of one of her resource sets together with a payment vector indicating how much she is willing to contribute towards the purchase of each resource. During the talk, we study the existence and computability of pure Nash equilibria (PNEs) in resource buying games. While there exists very simple connection games (e.g. those where each player wants to connect two terminals) without PNE, we will see that almost everything is fine as soon as we consider games in which each players strategy set is the base set of a matroid.