The impact of network topology on pure Nash equilibria in graphical games

摘要: Graphical games capture some of the key aspects relevant to study and design multi-agent systems. It is often interest find conditions under which a game stable, i.e., players have reached consensus on their actions. In this paper, we characterize how different topologies interaction network affect probability existence pure Nash equilibrium in graphical with random payoffs. We show that for tree unbounded diameter vanishes as number grows large. On positive side, define several families graphs at least 1-1/e even goes infinity. also empirically adding small connection "shortcuts" can increase Nash.