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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Graphical games are a useful framework for modeling the interactions of(selfish) agents who are connected via an underlying topology and whosebehaviors influence each other. They have wide applications ranging fromcomputer science to economics and biology. Yet, even though a player's payoffonly depends on the actions of their direct neighbors in graphical games,computing the Nash equilibria and making statements about the convergence timeof "natural" local dynamics in particular can be highly challenging. In thiswork, we present a novel approach for classifying complexity of Nash equilibriain graphical games by establishing a connection to local graph algorithms, asubfield of distributed computing. In particular, we make the observation thatthe equilibria of graphical games are equivalent to locally verifiablelabelings (LVL) in graphs; vertex labelings which are verifiable with aconstant-round local algorithm. This connection allows us to derive novel lowerbounds on the convergence time to equilibrium of best-response dynamics ingraphical games. Since we establish that distributed convergence can sometimesbe provably slow, we also introduce and give bounds on an intuitive notion of"time-constrained" inefficiency of best responses. We exemplify how our resultscan be used in the implementation of mechanisms that ensure convergence of bestresponses to a Nash equilibrium. Our results thus also give insight into theconvergence of strategy-proof algorithms for graphical games, which is stillnot well understood.

Classifying Convergence Complexity of Nash Equilibria in Graphical Games Using Distributed Computing Theory