conference paper
On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games
Maximilian
Drees
author
Matthias
Feldotto
author 140520000-0003-1348-6516
Sören
Riechers
author
Alexander
Skopalik
author 40384
63
department
541
department
SFB 901
project
SFB 901 - Subprojekt A3
project
SFB 901 - Subproject C4
project
SFB 901 - Project Area A
project
SFB 901 - Project Area C
project
In \emph{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 improve her utility by more than some fixed factor $\alpha$ 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 \geq \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 ${\sf NP}$-hard. We also show that the $\alpha$-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.
https://ris.uni-paderborn.de/download/271/1475/271-chp_3A10.1007_2F978-3-662-48433-3_14.pdf
application/pdf
2015
Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT)
1507.0290810.1007/978-3-662-48433-3_14
178-189
Drees, M., Feldotto, M., Riechers, S., & Skopalik, A. (2015). On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games. In <i>Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT)</i> (pp. 178–189). <a href="https://doi.org/10.1007/978-3-662-48433-3_14">https://doi.org/10.1007/978-3-662-48433-3_14</a>
M. Drees, M. Feldotto, S. Riechers, A. Skopalik, in: Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT), 2015, pp. 178–189.
M. Drees, M. Feldotto, S. Riechers, and A. Skopalik, “On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games,” in <i>Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT)</i>, 2015, pp. 178–189.
Drees, Maximilian, Matthias Feldotto, Sören Riechers, and Alexander Skopalik. “On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games.” In <i>Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT)</i>, 178–89. Lecture Notes in Computer Science, 2015. <a href="https://doi.org/10.1007/978-3-662-48433-3_14">https://doi.org/10.1007/978-3-662-48433-3_14</a>.
@inproceedings{Drees_Feldotto_Riechers_Skopalik_2015, series={Lecture Notes in Computer Science}, title={On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games}, DOI={<a href="https://doi.org/10.1007/978-3-662-48433-3_14">10.1007/978-3-662-48433-3_14</a>}, booktitle={Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT)}, author={Drees, Maximilian and Feldotto, Matthias and Riechers, Sören and Skopalik, Alexander}, year={2015}, pages={178–189}, collection={Lecture Notes in Computer Science} }
Drees M, Feldotto M, Riechers S, Skopalik A. On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games. In: <i>Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT)</i>. Lecture Notes in Computer Science. ; 2015:178-189. doi:<a href="https://doi.org/10.1007/978-3-662-48433-3_14">10.1007/978-3-662-48433-3_14</a>
Drees, Maximilian, et al. “On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games.” <i>Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT)</i>, 2015, pp. 178–89, doi:<a href="https://doi.org/10.1007/978-3-662-48433-3_14">10.1007/978-3-662-48433-3_14</a>.
2712017-10-17T12:41:45Z2019-01-03T13:13:34Z