Coordination Games on Graphs
- Speaker(s)
- Krzysztof Apt
- Affiliation
- Centrum Wiskunde & Informatica, Amsterdam, i Instytut Informatyki, UW
- Date
- Oct. 21, 2021, 10:15 a.m.
- Room
- room 4050
- Seminar
- Seminar Games, Mechanisms, and Social Networks
For the past five years we have been studying a natural class of
coordination games. In these games the players are nodes in a
(possibly directed), each with a finite set of strategies, and the
payoff of each player defined as the number of his neighbours who
selected the same strategy. These games capture the idea of
coordination in the absence of globally common strategies.
In [1] we investigated games on undirected graphs. Such games always
have (pure) Nash equilibria and the focus of this work was on
identifying classes of graphs for which strong equilibria exist.
More recently, see [2], we considered games on directed weighted
graphs in presence of bonuses. For such graphs the payoff 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. In these games Nash equilibria do not need to
exist. However, for several natural classes of graphs, including
cycles, open chains of cycles, DAGs, and cliques, finite improvement
or coalition-improvement paths of polynomial length always exist. As
a consequence, a (pure) Nash equilibrium or a strong equilibrium in
them can be found in polynomial time.
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 no bonuses.
References:
[1] K.R. Apt, B. de Keijzer, M. Rahn, G. Schäfer, and S. Simon,
Coordination Games on Graphs. International Journal on Game Theory 46(3),
https://link.springer.com/article/10.1007%2Fs00182-016-0560-8 , pp.
851-877, 2017.
[2] K. R. Apt, S. Simon, D. Wojtczak,
Coordination Games on Weighted Directed Graphs. Mathematics of
Operations Research, 2021.
https://drive.google.com/file/d/1LRBg5bMuz4W5Ll7tjzKD3RRjx_NVyNy-/view?usp=sharing