Title: Multiagent Learning in Large Anonymous Games

Abstract: Designers of distributed systems are frequently unable to determine how an agent in the system should behave, because optimal behavior depends on the user’s preferences and the actions of others. Game theoretic analysis can show that equilibria exist with desirable properties where agents use certain types of strategies, but without a detailed understanding of the agents in a particular system it is often impossible say exactly what game is being played, much less what equilibrium will occur.

A natural approach is to have agents use a learning algorithm. Many multiagent learning algorithms have been proposed including simple strategy update procedures such as fictitious play, multiagent versions of Q-learning, and no-regret algorithms. However, many algorithms are unsuitable for distributed systems because they rely on having impractical amounts of information or converge too slowly. Despite these problems, distributed systems have a number of features that help make learning easier. First, they are often large. This means that the decisions any single agent makes have a very small effect on other agents. Second, they are often anonymous. It doesn't matter which agents play each strategy, only how many. I will show that these features allow a simple learning algorithm to find equilibria in an interesting class of games, those where best-reply dynamics converge.

This talk is based on joint work with Eric Friedman and Joe Halpern that appeared at AAMAS '09.