Resource buying games
From MaRDI portal
Publication:487012
Abstract: 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.
Recommendations
Cites work
- A class of games possessing pure-strategy Nash equilibria
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Efficient computation of approximate pure Nash equilibria in congestion games
- Exact and approximate equilibria for optimal group network formation
- Near-optimal network design with selfish agents
- Non-cooperative facility location and covering games
- Non-cooperative tree creation
- On the complexity of Pareto-optimal Nash and strong equilibria
- On the complexity of pure-strategy Nash equilibria in congestion and local-effect games
- On the existence of pure Nash equilibria in weighted congestion games
- On the impact of combinatorial structure on congestion games
- Price of stability in survivable network design
- Pure Nash equilibria in player-specific and weighted congestion games
- Strategic cooperation in cost sharing games
- Strategic multiway cut and multicut games
- Strong equilibrium in cost sharing connection games
- Terminal backup, 3D matching, and covering cubic graphs
- The complexity of pure Nash equilibria
Cited in
(14)- Efficiency of equilibria in uniform matroid congestion games
- Resource pricing games on graphs: existence of Nash equilibria
- Uniqueness of equilibria in atomic splittable polymatroid congestion games
- Arbitrary profit sharing in federated learning utility games
- Efficient black-box reductions for separable cost sharing
- Efficient black-box reductions for separable cost sharing
- Equilibrium inefficiency in resource buying games with load-dependent costs
- A Unified Framework for Pricing in Nonconvex Resource Allocation Games
- Competitive Cost Sharing with Economies of Scale
- A Characterization of Undirected Graphs Admitting Optimal Cost Shares
- Competitive cost sharing with economies of scale
- Resource location games
- Generalizations of weighted matroid congestion games: pure Nash equilibrium, sensitivity analysis, and discrete convex function
- Resource buying games
This page was built for publication: Resource buying games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q487012)
