Computer Science – Computer Science and Game Theory
Scientific paper
2012-04-18
Computer Science
Computer Science and Game Theory
Scientific paper
In resource buying games a set of players jointly buys a subset of a finite resource set E (e.g., machines, edges, or nodes in a digraph). The cost of a resource e depends on the number (or load) of players using e, and has to be paid completely by the players before it becomes available. Each player i needs at least one set of a predefined family S_i in 2^E to be available. Thus, resource buying games can be seen as a variant of congestion games in which the load-dependent costs of the resources can be shared arbitrarily among the players. A strategy of player i in resource buying games is a tuple consisting of one of i's desired configurations S_i together with a payment vector p_i in R^E_+ indicating how much i is willing to contribute towards the purchase of the chosen resources. In this paper, we study the existence and computational complexity of pure Nash equilibria (PNE, for short) of resource buying games. In contrast to classical congestion games for which equilibria are guaranteed to exist, the existence of equilibria in resource buying games strongly depends on the underlying structure of the S_i's and the behavior of the cost functions. We show that for marginally non-increasing cost functions, matroids are exactly the right structure to consider, and that resource buying games with marginally non-decreasing cost functions always admit a PNE.
Harks Tobias
Peis Britta
No associations
LandOfFree
Resource Buying Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Resource Buying Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Resource Buying Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-412026