ﻻ يوجد ملخص باللغة العربية
We study strategic games on weighted directed graphs, in which the payoff of a player is defined as the sum of the weights on the edges from players who chose the same strategy, augmented by a fixed non-negative 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, as a consequence, a (pure) Nash equlibrium 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, while open chains of simple cycles correspond to multiple independent rings topology from the recommendation G.8032v2 on the 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 the problem of determining the existence of a Nash equilibrium or of a strong equilibrium in these games is NP-complete already for unweighted graphs and with no bonuses assumed. This implies that the same problems for polymatrix games are strongly NP-hard.
We study natural strategic games on directed graphs, which capture the idea of coordination in the absence of globally common strategies. We show that these games do not need to have a pure Nash equilibrium and that the problem of determining their e
We introduce natural strategic games on graphs, which capture the idea of coordination in a local setting. We study the existence of equilibria that are resilient to coalitional deviations of unbounded and bounded size (i.e., strong equilibria and k-
We study strategic games on weighted directed graphs, where the payoff of a player is defined as the sum of the weights on the edges from players who chose the same strategy augmented by a fixed non-negative bonus for picking a given strategy. These
We consider polymatrix coordination games with individual preferences where every player corresponds to a node in a graph who plays with each neighbor a separate bimatrix game with non-negative symmetric payoffs. In this paper, we study $alpha$-appro
This study investigates simple games. A fundamental research question in this field is to determine necessary and sufficient conditions for a simple game to be a weighted majority game. Taylor and Zwicker (1992) showed that a simple game is non-weigh