Text

Coordination Games on Weighted Directed Graphs

We study strategic games on weighted directed graphs, where each player’s payoff is defined as the sum of the weights on the edges from players who chose the same strategy, augmented by a fixed nonnegative integer bonus for picking a given strategy. These games capture the idea of coordination in the absence of globally common strategies. We identify natural classes of graphs for which finite improvement or coalition-improvement paths of polynomial length always exist, and consequently a (pure) Nash equilibrium or a strong equilibrium can be found in polynomial time. The considered classes of graphs are typical in network topologies: simple cycles correspond to the token ring local area networks, whereas open chains of simple cycles correspond to multiple independent rings topology from the recommendation G.8032v2 on Ethernet ring protection switching. For simple cycles, these results are optimal in the sense that without the imposed conditions on the weights and bonuses, a Nash equilibrium may not even exist. Finally, we prove that determining the existence of a Nash equilibrium or of a strong equilibrium is NP-complete already for unweighted graphs, with no bonuses assumed. This implies that the same problems for polymatrix games are strongly NP-hard.

Ketersediaan

Informasi Detail

Judul Seri

MATHEMATICS OF OPERATIONS RESEARCH; Vol.47 No.2 May 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 995-1025

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

COMPUTATIONAL COMPLEXITY
NONCOOPERATIVE GAMES
COORDINATION GAMES
NESH EQULIBRIUM
STRONG EQUILIBRIUM

Info Detail Spesifik

https://doi.org/10.1287/moor.2021.1159

Pernyataan Tanggungjawab

Krzysztof R. Apt, Sunil Simon, Dominik Wojtczak

Versi lain/terkait

Lampiran Berkas

Komentar