The Impact of Network Topology on Pure Nash Equilibria in Graphical Games

Bistra Dilkina, Carla P. Gomes, Ashish Sabharwal

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

Subjects: 1.8 Game Playing; 7.1 Multi-Agent Systems

Submitted: Apr 25, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.