A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games

DOI10.1007/S00224-017-9826-1zbMATH Open1394.91015arXiv1110.5439OpenAlexW1616868910MaRDI QIDQ722221FDOQ722221

Authors: Vittorio Bilò 

Publication date: 23 July 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: We present a general technique, based on a primal-dual formulation, for analyzing the quality of self-emerging solutions in weighted congestion games. With respect to traditional combinatorial approaches, the primal-dual schema has at least three advantages: first, it provides an analytic tool which can always be used to prove tight upper bounds for all the cases in which we are able to characterize exactly the polyhedron of the solutions under analysis; secondly, in each such a case the complementary slackness conditions give us an hint on how to construct matching lower bounding instances; thirdly, proofs become simpler and easy to check. For the sake of exposition, we first apply our technique to the problems of bounding the prices of anarchy and stability of exact and approximate pure Nash equilibria, as well as the approximation ratio of the solutions achieved after a one-round walk starting from the empty strategy profile, in the case of affine latency functions and we show how all the known upper bounds for these measures (and some of their generalizations) can be easily reobtained under a unified approach. Then, we use the technique to attack the more challenging setting of polynomial latency functions. In particular, we obtain the first known upper bounds on the price of stability of pure Nash equilibria and on the approximation ratio of the solutions achieved after a one-round walk starting from the empty strategy profile for unweighted players in the cases of quadratic and cubic latency functions. We believe that our technique, thanks to its versatility, may prove to be a powerful tool also in several other applications.

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

Recommendations

• A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games
• The price of stability of weighted congestion games
• The price of stability of weighted congestion games
• A unifying approximate potential for weighted congestion games
• A unifying approximate potential for weighted congestion games

zbMATH Keywords

congestion games(approximate) Nash equilibriaprice of anarchy and stabilityperformance of one-round walksprimal-dual analysis

Mathematics Subject Classification ID

Noncooperative games (91A10) (n)-person games, (n>2) (91A06)

Cites Work

• Worst-case equilibria
• A class of games possessing pure-strategy Nash equilibria
• The Price of Stability for Network Design with Fair Cost Allocation
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Title not available (Why is that?)
• On the existence of pure Nash equilibria in weighted congestion games
• The price of anarchy of finite congestion games
• Tight bounds for selfish and greedy load balancing
• Online bipartite matching with random arrivals
• Algorithms – ESA 2005
• Approximation and Online Algorithms
• On the performance of approximate equilibria in congestion games
• The curse of simultaneity
• The price of routing unsplittable flow
• Some anomalies of farsighted strategic behavior
• A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games
• On the performance of mildly greedy players in cut games
• Convergence and approximation in potential games
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Performance of one-round walks in linear congestion games
• Strong and Pareto Price of Anarchy in Congestion Games
• Selfish load balancing and atomic congestion games
• Stackelberg strategies for atomic congestion games
• Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs
• Algorithms for pure Nash equilibria in weighted congestion games
• Characterizing the existence of potential functions in weighted congestion games
• Oblivious algorithms for the maximum directed cut problem
• On the Robustness of the Approximate Price of Anarchy in Generalized Congestion Games
• On Linear Congestion Games with Altruistic Social Context
• On lookahead equilibria in congestion games
• Exact price of anarchy for polynomial congestion games
• Taxes for linear atomic congestion games
• On Stackelberg Strategies in Affine Congestion Games
• A theoretical examination of practical game playing: lookahead search
• Price of stability in polynomial congestion games
• Wavelength management in WDM rings to maximize the number of connections

Cited In (10)

• The Price of Stability of Weighted Congestion Games
• Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses
• Congestion games with priority-based scheduling
• Project games
• The sequential price of anarchy for affine congestion games with few players
• A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games
• On the robustness of the approximate price of anarchy in generalized congestion games
• On Stackelberg strategies in affine congestion games
• Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship
• The price of anarchy of affine congestion games with similar strategies

This page was built for publication: A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games

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