---
res:
bibo_abstract:
- 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.
bibo_authorlist:
- foaf_Person:
foaf_givenName: Maximilian
foaf_name: Drees, Maximilian
foaf_surname: Drees
- foaf_Person:
foaf_givenName: Matthias
foaf_name: Feldotto, Matthias
foaf_surname: Feldotto
foaf_workInfoHomepage: http://www.librecat.org/personId=14052
orcid: 0000-0003-1348-6516
- foaf_Person:
foaf_givenName: Sören
foaf_name: Riechers, Sören
foaf_surname: Riechers
- foaf_Person:
foaf_givenName: Alexander
foaf_name: Skopalik, Alexander
foaf_surname: Skopalik
foaf_workInfoHomepage: http://www.librecat.org/personId=40384
bibo_doi: 10.1007/978-3-662-48433-3_14
dct_date: 2015^xs_gYear
dct_title: On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth
Allocation Games@
...