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

DOI10.1007/978-3-662-48433-3_14MaRDI QIDQ3449591zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 5485547 (Why is no real title available?)
• scientific article; zbMATH DE number 1792100 (Why is no real title available?)
• A class of games possessing pure-strategy Nash equilibria
• Approximate pure Nash equilibria in weighted congestion games
• Assignment games with conflicts: robust price of anarchy and convergence results via semi-smoothness
• Bounding the potential function in congestion games and approximate pure Nash equilibria
• Budget-restricted utility games with ordered strategic decisions
• Complexity of pure Nash equilibria in player-specific network congestion games
• Congestion Games with Player-Specific Constants
• Congestion games with player-specific payoff functions
• Congestion games with variable demands
• Convergence to approximate Nash equilibria in congestion games
• Efficient computation of approximate pure Nash equilibria in congestion games
• Exact price of anarchy for polynomial congestion games
• Intrinsic robustness of the price of anarchy
• Network design with weighted players
• On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games
• On the complexity of pure-strategy Nash equilibria in congestion and local-effect games
• On the existence of pure Nash equilibria in weighted congestion games
• On the performance of approximate equilibria in congestion games
• Potential games
• Pure Nash equilibria in player-specific and weighted congestion games
• Scheduling shared continuous resources on many-cores
• The complexity of pure Nash equilibria
• The price of anarchy of finite congestion games
• The price of routing unsplittable flow
• Weighted congestion games: price of anarchy, universal worst-case examples, and tightness

Cited in

(7)

• Pure Nash equilibria in weighted matroid congestion games with non-additive aggregation and beyond
• Nonlinear game models for large-scale network bandwidth management
• On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games
• Complexity and approximability of optimal resource allocation and Nash equilibrium over networks
• A common generalization of budget games and congestion games
• A common generalization of budget games and congestion games
• Pure Nash equilibria in restricted budget 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)