On approximate pure Nash equilibria in weighted congestion games with polynomial latencies

Ioannis Caragiannis () and Angelo Fanelli ()
Additional contact information
Ioannis Caragiannis: University of Patras, Department of Computer Engineering and Informatics [Patras] - University of Patras
Angelo Fanelli: CREM - Centre de recherche en économie et management - UNICAEN - Université de Caen Normandie - NU - Normandie Université - UR - Université de Rennes - CNRS - Centre National de la Recherche Scientifique

Working Papers from HAL

Abstract: We consider the problem of the existence of natural improvement dynamics leading to approximate pure Nash equilibria, with a reasonable small approximation, and the problem of bounding the efficiency of such equilibria in the fundamental framework of weighted congestion game with polynomial latencies of degree at most $\d \geq 1$.\\ In this work, by exploiting a simple technique, we firstly show that the game always admits a $\d$-approximate potential function. This implies that every sequence of $\d$-approximate improvement moves by the players always leads the game to a $\d$-approximate pure Nash equilibrium. As a corollary, we also obtain that, under mild assumptions on the structure of the players' strategies, the game always admits a constant approximate potential function. Secondly, by using a simple potential function argument, we are able to show that in the game there always exists a $(\d+\delta)$-approximate pure Nash equilibrium, with $\delta\in [0,1]$, whose cost is $2/(1+\delta)$ times the cost of any optimal state.

Date: 2019-02
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:wpaper:hal-02089351

Access Statistics for this paper

More papers in Working Papers from HAL
Bibliographic data for series maintained by CCSD ().