A Unifying Approximate Potential for Weighted Congestion Games
Giannakopoulos Y, Poças D (2020)
Publication Type: Conference contribution, Original article
Publication year: 2020
Journal
Publisher: Springer Science and Business Media Deutschland GmbH
Book Volume: 12283 LNCS
Pages Range: 99-113
Conference Proceedings Title: Proceedings of the 13th Symposium on Algorithmic Game Theory (SAGT)
Event location: Augsburg
ISBN: 9783030579791
DOI: 10.1007/978-3-030-57980-7_7
Open Access Link: https://arxiv.org/abs/2005.10101
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.
Authors with CRIS profile
Involved external institutions
How to cite
APA:
Giannakopoulos, Y., & Poças, D. (2020). A Unifying Approximate Potential for Weighted Congestion Games. In Tobias Harks, Max Klimm (Eds.), Proceedings of the 13th Symposium on Algorithmic Game Theory (SAGT) (pp. 99-113). Augsburg, DE: Springer Science and Business Media Deutschland GmbH.
MLA:
Giannakopoulos, Yiannis, and Diogo Poças. "A Unifying Approximate Potential for Weighted Congestion Games." Proceedings of the 13th International Symposium on Algorithmic Game Theory, SAGT 2020, Augsburg Ed. Tobias Harks, Max Klimm, Springer Science and Business Media Deutschland GmbH, 2020. 99-113.
BibTeX: Download