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

DOI10.1007/978-3-662-48433-3_14zbMATH Open1358.91071arXiv1507.02908OpenAlexW3102653315MaRDI QIDQ3449591FDOQ3449591

Authors: Maximilian Drees, Matthias Feldotto, Sören Riechers, Alexander Skopalik 

Publication date: 4 November 2015

Published in: Algorithmic Game Theory (Search for Journal in Brave)

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 $alph{a}_{d}elta$ (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 $alphageqalph{a}_{d}elta$, but not for $alpha<alph{a}_{d}elta$. We give both upper and lower bounds on this threshold $alph{a}_{d}elta$ and show that the corresponding decision problem is $sfNP$-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.

Full work available at URL: https://arxiv.org/abs/1507.02908

Recommendations

• Optimal Nash equilibria for bandwidth allocation
• Generalized Nash bargaining solution for bandwidth allocation
• A game-theoretic analysis of bandwidth allocation under a user-grouping constraint
• Approximate pure Nash equilibria in weighted congestion games
• Nonlinear game models for large-scale network bandwidth management
• Complexity of pure Nash equilibria in player-specific network congestion games
• On approximate pure Nash equilibria in weighted congestion games with polynomial latencies
• On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10) (n)-person games, (n>2) (91A06) Games involving graphs (91A43)

Cites Work

• A class of games possessing pure-strategy Nash equilibria
• Potential games
• Congestion games with player-specific payoff functions
• Title not available (Why is that?)
• The complexity of pure Nash equilibria
• The price of anarchy of finite congestion games
• Intrinsic robustness of the price of anarchy
• The price of routing unsplittable flow
• Convergence to approximate Nash equilibria in congestion games
• Pure Nash equilibria in player-specific and weighted congestion games
• Network design with weighted players
• Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games
• On the performance of approximate equilibria in congestion games
• Congestion Games with Player-Specific Constants
• On the complexity of pure-strategy Nash equilibria in congestion and local-effect games
• Complexity of pure Nash equilibria in player-specific network congestion games
• Weighted congestion games: price of anarchy, universal worst-case examples, and tightness
• Assignment games with conflicts: robust price of anarchy and convergence results via semi-smoothness
• Scheduling shared continuous resources on many-cores
• Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria
• Approximate Pure Nash Equilibria in Weighted Congestion Games
• On the existence of pure Nash equilibria in weighted congestion games
• Exact price of anarchy for polynomial congestion games
• Congestion games with variable demands
• On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games
• Budget-Restricted Utility Games with Ordered Strategic Decisions
• Title not available (Why is that?)

Cited In (6)

• On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games
• Nonlinear game models for large-scale network bandwidth management
• A common generalization of budget games and congestion games
• Pure Nash equilibria in restricted budget games
• Pure Nash equilibria in weighted matroid congestion games with non-additive aggregation and beyond
• A common generalization of budget games and congestion games

This page was built for publication: On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449591)