Computer Science Department
School of Computer Science, Carnegie Mellon University


Existence of Multiagent Equilibria with Limited Agents

Michael Bowling, Manuela Veloso

January 2002

Keywords: Multiagent learning, reinforcement learning, multiagent systems, slimited agents, Nash equilibria

Multiagent learning is a neccessary yet challenging problem as multiagent systems become more prevalent and environments become more dynamic. Much of the groundbreaking work in this area draws on notable results from the game theory community. Nash Equilibria, in particular, is a very important concept to multiagent learning. Learners that directly learn equilibria obviously rely on their existence. Learners that instead seek to play optimally with respect to the other players also depend upon equilibria since equilibria are, and are the only, learning fixed points. From another perspective, agents with limitations are real and common, both agents with undesired physical limitations as well as self-imposed rational limitations. This paper explores the interactions of these two important concepts, examining whether equilibria continue to exist when agents have limitations. We look at the general effects limitations can have on agent behavior, and define a natural extention of equilibria that accounts for these limitations. We show that existence cannot be guaranteed in general, but prove existence under certain classes of domains and agent limitations. These results have wide applicability as they are not tied to any particular learning algorithm or specific instance of agent limtations. We then present empirical results from a specific multiagent learner applied to a specific instance of limited agents. These results demonstrate that learning with limitations is possible, and our theoretical analysis of equilibria under limitations is relevant.

17 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by