Name
Title | ||
|---|---|---|
On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games |
Abstract | ||
|---|---|---|
In bandwidth allocation games (BAGs), the strategy of a player consists of various demands on different resources. The player's utility is at most the sum of these demands, provided they are fully satisfied. Every resource has a limited capacity and if it is exceeded by the total demand, it has to be split between the players. Since these games generally do not have pure Nash equilibria, we consider approximate pure Nash equilibria, in which no player can prove her utility by more than some fixed factor a through unilateral strategy changes. There is a threshold alpha(delta) (where delta is a parameter that limits the demand of each player on a specific resource) such that alpha-approximate pure Nash equilibria always exist for alpha >= alpha(delta), but not for alpha < alpha(delta). We give both upper and lower bounds on this threshold alpha(delta) and show that the corresponding decision problem is N P-hard. We also show that the cx-approximate price of anarchy for BAGs is alpha +1. For a restricted version of the game, where demands of players only differ slightly from each other (e.g. symmetric games), we show that approximate Nash equilibria can be reached (and thus also be computed) in polynomial time using the best-response dynamic. Finally, we show that a broader class of utility-maximization games (which includes BAGs) converges quickly towards states whose social welfare is close to the optimum. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-48433-3_14 | ALGORITHMIC GAME THEORY, SAGT 2015 |
Field | DocType | Volume |
Mathematical economics,Congestion game,Mathematical optimization,Bandwidth allocation,Potential game,Upper and lower bounds,Price of anarchy,Time complexity,Nash equilibrium,Mathematics | Journal | 9347 |
ISSN | Citations | PageRank |
0302-9743 | 2 | 0.42 |
References | Authors | |
22 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maximilian Drees | 1 | 7 | 1.89 |
| Matthias Feldotto | 2 | 14 | 5.50 |
| Sören Riechers | 3 | 15 | 5.12 |
| Alexander Skopalik | 4 | 247 | 20.62 |