Loading...
Please wait, while we are loading the content...
Similar Documents
Restoring Pure Equilibria to Weighted Congestion Games
| Content Provider | CiteSeerX |
|---|---|
| Author | Kollias, Konstantinos Roughgarden, Tim |
| Abstract | Congestion games model several interesting applications, including routing and network formation games, and also possess attractive theoretical properties, including the existence of and convergence of natural dynamics to a pure Nash equilibrium. Weighted variants of congestion games that rely on sharing costs proportional to players’ weights do not generally have pure-strategy Nash equilibria. We propose a new way of assigning costs to players with weights in congestion games that recovers the important properties of the unweighted model. This method is derived from the Shapley value, and it always induces a game with a (weighted) potential function. For the special cases of weighted network cost-sharing and weighted routing games with Shapley value-based cost shares, we prove tight bounds on the price of stability and price of anarchy, respectively. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Several Interesting Application Important Property Shapley Value-based Cost Share Pure Nash Equilibrium Network Formation Game Natural Dynamic Weighted Network Cost-sharing Congestion Game Pure Equilibrium Tight Bound Potential Function Unweighted Model Player Weight New Way Weighted Variant Weighted Congestion Game Shapley Value Pure-strategy Nash Equilibrium Posse Attractive Theoretical Property |
| Content Type | Text |
