A unifying approximate potential for weighted congestion games

DOI10.1007/978-3-030-57980-7_7zbMATH Open1503.91023arXiv2005.10101OpenAlexW3091537962MaRDI QIDQ2109950FDOQ2109950

Authors: Yiannis Giannakopoulos, Diogo Poças 

Publication date: 21 December 2022

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

Abstract: We provide a unifying, black-box tool for establishing existence of approximate equilibria in weighted congestion games and, at the same time, bounding their Price of Stability. Our framework can handle resources with general costs--including, in particular, decreasing ones--and is formulated in terms of a set of parameters which are determined via elementary analytic properties of the cost functions. We demonstrate the power of our tool by applying it to recover the recent result of Caragiannis and Fanelli [ICALP'19] for polynomial congestion games; improve upon the bounds for fair cost sharing games by Chen and Roughgarden [Theory Comput. Syst., 2009]; and derive new bounds for nondecreasing concave costs. An interesting feature of our framework is that it can be readily applied to mixtures of different families of cost functions; for example, we provide bounds for games whose resources are conical combinations of polynomial and concave costs. In the core of our analysis lies the use of a unifying approximate potential function which is simple and general enough to be applicable to arbitrary congestion games, but at the same time powerful enough to produce state-of-the-art bounds across a range of different cost functions.

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

Recommendations

• A unifying approximate potential for weighted congestion games
• The price of stability of weighted congestion games
• The price of stability of weighted congestion games
• Approximate pure Nash equilibria in weighted congestion games
• On approximate pure Nash equilibria in weighted congestion games with polynomial latencies

zbMATH Keywords

potential gamesprice of stabilityapproximate equilibriaatomic congestion games

Mathematics Subject Classification ID

Games with infinitely many players (91A07) Potential and congestion games (91A14)

Cites Work

• Algorithmic Game Theory
• Worst-case equilibria
• Selfish Routing in Capacitated Networks
• A class of games possessing pure-strategy Nash equilibria
• Hermite and convexity
• Potential games
• The Price of Stability for Network Design with Fair Cost Allocation
• Selfish unsplittable flows
• On the existence of pure Nash equilibria in weighted congestion games
• Selfish load balancing
• Network design with weighted players
• Strong equilibria in games with the lexicographical improvement property
• Algorithms, games, and the internet
• Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games
• Atomic resource sharing in noncooperative networks
• On the performance of approximate equilibria in congestion games
• On the complexity of pure-strategy Nash equilibria in congestion and local-effect games
• On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations
• The structure and complexity of Nash equilibria for a selfish routing game
• Improved lower bounds on the price of stability of undirected network design games
• Approximate Pure Nash Equilibria in Weighted Congestion Games
• A unifying approximate potential for weighted congestion games
• Algorithms for pure Nash equilibria in weighted congestion games
• On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies
• A network pricing game for selfish traffic
• The Price of Stability of Weighted Congestion Games
• Twenty Lectures on Algorithmic Game Theory
• The price of stability for undirected broadcast network design with fair cost allocation is constant
• On the Price of Stability of Undirected Multicast Games

Cited In (9)

• On the performance of approximate equilibria in congestion games
• Weighted congestion games with separable preferences
• Congestion models and weighted Bayesian potential games
• Title not available (Why is that?)
• Characterizing the existence of potential functions in weighted congestion games
• Characterizing the existence of potential functions in weighted congestion games
• A common generalization of budget games and congestion games
• Restoring Pure Equilibria to Weighted Congestion Games
• A unifying approximate potential for weighted congestion games

This page was built for publication: A unifying approximate potential for weighted congestion games

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