Learning and Adaptation in Multiagent Systems

The goal of a self-interested agent within a multi-agent system is to maximize its utility over time. In a situation of strategic interdependence, where the actions of one agent may affect the utilities of other agents, the optimal behavior of an agent must be conditioned on the expected behaviors of the other agents in the system. Standard game theory assumes that the rationality and prefer-ences of all the agents is common knowledge: each agent is then able to compute the set of pos-sible equilibria, and if there is a unique equilib-rium, choose a best-response to the actions that the other agents will all play. Real agents acting within a multiagent system face multiple problems: the agents may have in-complete information about the preferences and rationality of the other agents in the game, com-puting the equilibria can be computationally complex, and there might be many equilibria from which to choose. An alternative explana-tion of the emergence of a stable equilibrium is that it arises as the long-run outcome of a re-peated game, in which bounded-rational agents adapt their strategies as they learn about the other agents in the system. We review some possible models of learning for games, and then show the pros and cons of using learning in a particular game, the Compensation Mechanism, a mechanism for the efficient coordination of ac-tions within a multiagent system