* 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.