Sharing non-anonymous costs of multiple resources optimally
From MaRDI portal
Abstract: In cost sharing games, the existence and efficiency of pure Nash equilibria fundamentally depends on the method that is used to share the resources' costs. We consider a general class of resource allocation problems in which a set of resources is used by a heterogeneous set of selfish users. The cost of a resource is a (non-decreasing) function of the set of its users. Under the assumption that the costs of the resources are shared by uniform cost sharing protocols, i.e., protocols that use only local information of the resource's cost structure and its users to determine the cost shares, we exactly quantify the inefficiency of the resulting pure Nash equilibria. Specifically, we show tight bounds on prices of stability and anarchy for games with only submodular and only supermodular cost functions, respectively, and an asymptotically tight bound for games with arbitrary set-functions. While all our upper bounds are attained for the well-known Shapley cost sharing protocol, our lower bounds hold for arbitrary uniform cost sharing protocols and are even valid for games with anonymous costs, i.e., games in which the cost of each resource only depends on the cardinality of the set of its users.
Recommendations
Cites work
- A class of games possessing pure-strategy Nash equilibria
- Algorithms, games, and the internet
- Atomic resource sharing in noncooperative networks
- Congestion games with player-specific payoff functions
- Designing network protocols for good equilibria
- scientific article; zbMATH DE number 2079324 (Why is no real title available?)
- scientific article; zbMATH DE number 3078997 (Why is no real title available?)
- Network cost-sharing without anonymity
- On weighted Shapley values
- Optimal cost sharing for resource selection games
- Optimal cost-sharing in weighted congestion games
- Potential games are \textit{necessary} to ensure pure Nash equilibria in cost sharing games
- Potential, Value, and Consistency
- Restoring Pure Equilibria to Weighted Congestion Games
- Selfish unsplittable flows
- Sharing non-anonymous costs of multiple resources optimally
- The complexity of pure Nash equilibria
- The Price of Stability for Network Design with Fair Cost Allocation
- Worst-case equilibria
Cited in
(14)- Designing cost-sharing methods for Bayesian games
- Equilibrium inefficiency in resource buying games with load-dependent costs
- Network cost-sharing without anonymity
- Sharing the cost more efficiently
- Sharing non-anonymous costs of multiple resources optimally
- Optimal cost-sharing in general resource selection games
- Tight bounds for cost-sharing in weighted congestion games
- scientific article; zbMATH DE number 2080891 (Why is no real title available?)
- Efficient black-box reductions for separable cost sharing
- Optimal cost sharing for resource selection games
- A Characterization of Undirected Graphs Admitting Optimal Cost Shares
- Cost-sharing in generalised selfish routing
- On the Price of Anarchy of cost-sharing in real-time scheduling systems
- Cost sharing mechanisms for fair pricing of resource usage
This page was built for publication: Sharing non-anonymous costs of multiple resources optimally
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947026)
