English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In \emph{bandwidth allocation games} (BAGs), the strategy of a playerconsists of various demands on different resources. The player's utility is atmost the sum of these demands, provided they are fully satisfied. Everyresource has a limited capacity and if it is exceeded by the total demand, ithas to be split between the players. Since these games generally do not havepure Nash equilibria, we consider approximate pure Nash equilibria, in which noplayer can improve her utility by more than some fixed factor $\alpha$ throughunilateral strategy changes. There is a threshold $\alpha_\delta$ (where$\delta$ is a parameter that limits the demand of each player on a specificresource) such that $\alpha$-approximate pure Nash equilibria always exist for$\alpha \geq \alpha_\delta$, but not for $\alpha < \alpha_\delta$. We give bothupper and lower bounds on this threshold $\alpha_\delta$ and show that thecorresponding decision problem is ${\sf NP}$-hard. We also show that the$\alpha$-approximate price of anarchy for BAGs is $\alpha+1$. For a restrictedversion of the game, where demands of players only differ slightly from eachother (e.g. symmetric games), we show that approximate Nash equilibria can bereached (and thus also be computed) in polynomial time using the best-responsedynamic. Finally, we show that a broader class of utility-maximization games(which includes BAGs) converges quickly towards states whose social welfare isclose to the optimum.

On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games