Resource buying games
From MaRDI portal
Publication:487012
DOI10.1007/S00453-014-9876-6zbMATH Open1303.91050arXiv1204.4111OpenAlexW2102728684MaRDI QIDQ487012FDOQ487012
Publication date: 19 January 2015
Published in: Algorithmica (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1204.4111
Recommendations
Applications of game theory (91A80) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Combinatorial aspects of matroids and geometric lattices (05B35) Games involving graphs (91A43)
Cites Work
- A class of games possessing pure-strategy Nash equilibria
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On the existence of pure Nash equilibria in weighted congestion games
- On the impact of combinatorial structure on congestion games
- The complexity of pure Nash equilibria
- Pure Nash equilibria in player-specific and weighted congestion games
- Strong equilibrium in cost sharing connection games
- Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games
- Non-cooperative tree creation
- Title not available (Why is that?)
- Non-cooperative facility location and covering games
- On the Complexity of Pareto-optimal Nash and Strong Equilibria
- On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games
- Strategic cooperation in cost sharing games
- Strategic multiway cut and multicut games
- Terminal Backup, 3D Matching, and Covering Cubic Graphs
- Price of stability in survivable network design
- Exact and approximate equilibria for optimal group network formation
Cited In (10)
- A Unified Framework for Pricing in Nonconvex Resource Allocation Games
- Equilibrium inefficiency in resource buying games with load-dependent costs
- A Characterization of Undirected Graphs Admitting Optimal Cost Shares
- Efficiency of Equilibria in Uniform Matroid Congestion Games
- Generalizations of weighted matroid congestion games: pure Nash equilibrium, sensitivity analysis, and discrete convex function
- Resource location games
- Efficient Black-Box Reductions for Separable Cost Sharing
- Title not available (Why is that?)
- Arbitrary profit sharing in federated learning utility games
- Uniqueness of Equilibria in Atomic Splittable Polymatroid Congestion 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)
