English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We consider the problem of computing approximate Nash equilibria in monotone congestion games with polynomially decreasing cost functions. This class of games generalizes the one of network congestion games, while polynomially decreasing cost functions also include the fundamental Shapley cost sharing value. We design an algorithm that, given a parameter $$\\gamma >1$$ and a subroutine able to compute $$\\rho $$-approximate best-responses, outputs a $$\\gamma 1/p+\\rho $$-approximate Nash equilibrium, where p is the number of players. The computational complexity of the algorithm heavily depends on the choice of $$\\gamma $$. In particular, when $$\\gamma \\in O1$$, the complexity is quasi-polynomial, while when $$\\gamma \\in \\varOmega p^\\epsilon $$, for a fixed constant $$\\epsilon >0$$, it becomes polynomial. 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. On the negative side, we also show 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