Existence of Multiagent Equilibria with Limited Agents
CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
Pagination or Media Count:
Multiagent learning is a necessary 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. The authors look at the general effects limitations can have on agent behavior, and define a natural extension of equilibria that accounts for these limitations. They 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 limitations. The authors 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 that their theoretical analysis of equilibria under limitations is relevant.
- Operations Research
- Computer Programming and Software