Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games

DOI10.1287/moor.2014.0651zbMath1310.91013arXiv1402.3610OpenAlexW2110243058MaRDI QIDQ5247620

Adam Wierman, Jason R. Marden, Ragavendran Gopalakrishnan

Publication date: 24 April 2015

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.3610

zbMATH Keywords

game theoryNash equilibriumShapley valuecost sharingmarginal contribution

Mathematics Subject Classification ID

Noncooperative games (91A10) Cooperative games (91A12) Applications of game theory (91A80) Other game-theoretic models (91A40) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items (19)

A survey of static and dynamic potential games ⋮ Cost-Sharing in Generalised Selfish Routing ⋮ Tight Bounds for Cost-Sharing in Weighted Congestion Games ⋮ Weighted and near weighted potential games with application to game theoretic control ⋮ Potential differential games ⋮ Shapley value-based payment calculation for energy exchange between micro- and utility grids ⋮ Sharing Non-anonymous Costs of Multiple Resources Optimally ⋮ Cost-sharing strategy for carbon emission reduction and sales effort: a Nash game with government subsidy ⋮ Optimal Cost-Sharing in General Resource Selection Games ⋮ Dynamic potential games: the discrete-time stochastic case ⋮ Designing cost-sharing methods for Bayesian games ⋮ Congestion games with priority-based scheduling ⋮ Designing Networks with Good Equilibria under Uncertainty ⋮ A Characterization of Undirected Graphs Admitting Optimal Cost Shares ⋮ Value of Information in Bayesian Routing Games ⋮ On the Price of Anarchy of cost-sharing in real-time scheduling systems ⋮ Topological price of anarchy bounds for clustering games on networks ⋮ The Buck-Passing Game ⋮ Equilibria in Multiclass and Multidimensional Atomic Congestion Games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Revisiting log-linear learning: asynchrony, completeness and payoff-based implementation
• Decompositions and potentials for normal form games
• An efficient and almost budget balanced cost sharing method
• The statistical mechanics of strategic interaction
• A Shapley value representation of potential games
• State based potential games
• Cost sharing in a job scheduling problem
• A class of games possessing pure-strategy Nash equilibria
• COST SHARING IN NETWORKS: SOME OPEN QUESTIONS
• Computing Shapley Value in Supermodular Coalitional Games
• Designing Network Protocols for Good Equilibria
• How bad is selfish routing?
• The Price of Stability for Network Design with Fair Cost Allocation
• Quantifying inefficiency in cost-sharing mechanisms
• On the Price of Stability for Undirected Network Design
• Near-optimal network design with selfish agents
• A Game Theoretic Approach for Efficient Graph Coloring
• On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations
• Potential, Value, and Consistency
• Minimum cost spanning tree games
• On the Complexity of Cooperative Solution Concepts
• Conjectural Equilibrium in Multiuser Power Control Games
• Joint Strategy Fictitious Play With Inertia for Potential Games
• Optimal Cost Sharing for Resource Selection Games
• The price of selfish behavior in bilateral network formation
• The Price of Selfishness in Network Coding
• Distributed Welfare Games
• Overcoming the Limitations of Utility Design for Multiagent Systems
• Is Shapley Cost Sharing Optimal?
• Efficiency Loss in a Network Resource Allocation Game
• Computing and Combinatorics
• Sharing the cost of multicast transmissions
• Strategyproof sharing of submodular costs: budget balance versus efficiency

This page was built for publication: Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games