Koller AAAI 2002

Citation

D Vickrey and D Koller. Multi-agent algorithms for solving Graphical Games 18th Ntl conference on Artificial Intelligence, AAAI Press, 2002

Online version

AAAI 2002

Summary

This paper presents a multi-agent algorithm approach to solve Graphical Games. Graphical games is a special type of problem in game theory where there is structure between the players in the game i.e. the interaction between the players is sparse. Solving for an equilibrium strategy profile for these players can be computationally expensive. Also there is a requirement that a central agent be aware of the relevant payoff information which then calculates the equilibrium strategy profile.

In this paper they try to solve a version of the problem where it is ok to have approximate equilibriums. They present two algorithms for this task.

• Hill Climbing approach
• Constraint Satisfaction approach - Cost minimization

They describe these two methods and then experimentally validate their claims. They use the Road game Road Game to run experiments on their algorothms. They find that :

• Both algorithms scale linearly with the number of nodes
• The algorithms find good approximate equilibria in a reasonable amount of time,
• Cost minimization has a lower variance in running time but can get expensive when grid size is large.

Method

They use the Hill climbing method and the Constraint Satisfaction method to find an equililbrium profile for the graphical game.