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