---
_id: '453'
abstract:
- lang: eng
  text: In this paper we study the potential function in congestion games. We consider
    both games with non-decreasing cost functions as well as games with non-increasing
    utility functions. We show that the value of the potential function $\Phi(\sf
    s)$ of any outcome $\sf s$ of a congestion game approximates the optimum potential
    value $\Phi(\sf s^*)$ by a factor $\Psi_{\mathcal{F}}$ which only depends on the
    set of cost/utility functions $\mathcal{F}$, and an additive term which is bounded
    by the sum of the total possible improvements of the players in the outcome $\sf
    s$. The significance of this result is twofold. On the one hand it provides \emph{Price-of-Anarchy}-like
    results with respect to the potential function. On the other hand, we show that
    these approximations can be used to compute $(1+\varepsilon)\cdot\Psi_{\mathcal{F}}$-approximate
    pure Nash equilibria for congestion games with non-decreasing cost functions.
    For the special case of polynomial cost functions, this significantly improves
    the guarantees from Caragiannis et al. [FOCS 2011]. Moreover, our machinery provides
    the first guarantees for general latency functions.
author:
- first_name: Matthias
  full_name: Feldotto, Matthias
  id: '14052'
  last_name: Feldotto
  orcid: 0000-0003-1348-6516
- first_name: Martin
  full_name: Gairing, Martin
  last_name: Gairing
- first_name: Alexander
  full_name: Skopalik, Alexander
  id: '40384'
  last_name: Skopalik
citation:
  ama: 'Feldotto M, Gairing M, Skopalik A. Bounding the Potential Function in Congestion
    Games and Approximate Pure Nash Equilibria. In: <i>Proceedings of the 10th International
    Conference on Web and Internet Economics (WINE)</i>. LNCS. ; 2014:30-43. doi:<a
    href="https://doi.org/10.1007/978-3-319-13129-0_3">10.1007/978-3-319-13129-0_3</a>'
  apa: Feldotto, M., Gairing, M., &#38; Skopalik, A. (2014). Bounding the Potential
    Function in Congestion Games and Approximate Pure Nash Equilibria. In <i>Proceedings
    of the 10th International Conference on Web and Internet Economics (WINE)</i>
    (pp. 30–43). <a href="https://doi.org/10.1007/978-3-319-13129-0_3">https://doi.org/10.1007/978-3-319-13129-0_3</a>
  bibtex: '@inproceedings{Feldotto_Gairing_Skopalik_2014, series={LNCS}, title={Bounding
    the Potential Function in Congestion Games and Approximate Pure Nash Equilibria},
    DOI={<a href="https://doi.org/10.1007/978-3-319-13129-0_3">10.1007/978-3-319-13129-0_3</a>},
    booktitle={Proceedings of the 10th International Conference on Web and Internet
    Economics (WINE)}, author={Feldotto, Matthias and Gairing, Martin and Skopalik,
    Alexander}, year={2014}, pages={30–43}, collection={LNCS} }'
  chicago: Feldotto, Matthias, Martin Gairing, and Alexander Skopalik. “Bounding the
    Potential Function in Congestion Games and Approximate Pure Nash Equilibria.”
    In <i>Proceedings of the 10th International Conference on Web and Internet Economics
    (WINE)</i>, 30–43. LNCS, 2014. <a href="https://doi.org/10.1007/978-3-319-13129-0_3">https://doi.org/10.1007/978-3-319-13129-0_3</a>.
  ieee: M. Feldotto, M. Gairing, and A. Skopalik, “Bounding the Potential Function
    in Congestion Games and Approximate Pure Nash Equilibria,” in <i>Proceedings of
    the 10th International Conference on Web and Internet Economics (WINE)</i>, 2014,
    pp. 30–43.
  mla: Feldotto, Matthias, et al. “Bounding the Potential Function in Congestion Games
    and Approximate Pure Nash Equilibria.” <i>Proceedings of the 10th International
    Conference on Web and Internet Economics (WINE)</i>, 2014, pp. 30–43, doi:<a href="https://doi.org/10.1007/978-3-319-13129-0_3">10.1007/978-3-319-13129-0_3</a>.
  short: 'M. Feldotto, M. Gairing, A. Skopalik, in: Proceedings of the 10th International
    Conference on Web and Internet Economics (WINE), 2014, pp. 30–43.'
date_created: 2017-10-17T12:42:20Z
date_updated: 2022-01-06T07:01:09Z
ddc:
- '040'
department:
- _id: '63'
- _id: '541'
doi: 10.1007/978-3-319-13129-0_3
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-16T11:24:11Z
  date_updated: 2018-03-16T11:24:11Z
  file_id: '1342'
  file_name: 453-WINE14FGS.pdf
  file_size: 324307
  relation: main_file
  success: 1
file_date_updated: 2018-03-16T11:24:11Z
has_accepted_license: '1'
page: 30-43
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Teilprojekt A
- _id: '7'
  name: SFB 901 - Subprojekt A3
publication: Proceedings of the 10th International Conference on Web and Internet
  Economics (WINE)
series_title: LNCS
status: public
title: Bounding the Potential Function in Congestion Games and Approximate Pure Nash
  Equilibria
type: conference
user_id: '14052'
year: '2014'
...