We consider the problem of computing approximate Nash equilibria in monotone congestion games (a class of games generalizing network congestion games) with polynomially decreasing cost functions. In particular, we consider the case in which each resource j has a cost cj and the cost that each player incurs when using j is given by cj/ xβ for some constant β> 0 , where x is the number of players using j. Observe that, for β= 1 , we obtain the fundamental Shapley cost sharing method. We design a parametric distributed algorithm for computing α-approximate Nash equilibria. The complexity of this algorithm depends on α, being polynomial for α= Ω(pβ) , for every fixed β> 0 , with p being the number of players. Our algorithm provides the first non-trivial approximability results for this class of games and achieves an almost tight performance for network games in directed graphs. For the case of ring networks, we show that an approximate equilibrium can be polynomially computed for every fixed α> 1. On the negative side, we prove that the problem of computing a Nash equilibrium in Shapley network cost sharing games is PLS-complete even in undirected graphs, where previous hardness results where known only in the directed case.

Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions

Monaco G.;Moscardelli L.
2021-01-01

Abstract

We consider the problem of computing approximate Nash equilibria in monotone congestion games (a class of games generalizing network congestion games) with polynomially decreasing cost functions. In particular, we consider the case in which each resource j has a cost cj and the cost that each player incurs when using j is given by cj/ xβ for some constant β> 0 , where x is the number of players using j. Observe that, for β= 1 , we obtain the fundamental Shapley cost sharing method. We design a parametric distributed algorithm for computing α-approximate Nash equilibria. The complexity of this algorithm depends on α, being polynomial for α= Ω(pβ) , for every fixed β> 0 , with p being the number of players. Our algorithm provides the first non-trivial approximability results for this class of games and achieves an almost tight performance for network games in directed graphs. For the case of ring networks, we show that an approximate equilibrium can be polynomially computed for every fixed α> 1. On the negative side, we prove that the problem of computing a Nash equilibrium in Shapley network cost sharing games is PLS-complete even in undirected graphs, where previous hardness results where known only in the directed case.
File in questo prodotto:
File Dimensione Formato  
Bilò2021_Article_ComputingApproximateNashEquili.pdf

Solo gestori archivio

Descrizione: Article
Tipologia: PDF editoriale
Dimensione 524.47 kB
Formato Adobe PDF
524.47 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11564/759080
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact