Stability in Systems with Self-Interested Agents

Wednesday, July 24, 2013, 9:00am – 1:00pm
Presented by Maria Polukarov
Located in Main Amphitheatre – Science bldg.
In track Tutorials

Multi-agent systems have emerged as one of the central areas of research and development in artificial intelligence, due to their wide applicability, in domains as diverse as industrial process control and electronic commerce. A multi-agent system is one composed of multiple interacting software components (aka agents), which may be cooperative or self- interested. The latter case is traditionally modelled as a non-cooperative game, where players strategically optimise their own utility functions.
This tutorial will begin by briefly introducing the students to some basic game-theoretic concepts, and will lead them to an understanding of what a stable outcome of a game is, and how agents can be made to achieve one. In particular, we will focus on the concept of a pure strategy Nash equilibrium (PSNE), in which each agent plays a certain strategy, and no one has an incentive to unilaterally change it. Such outcomes are highly desirable, since, from a system-wide perspective, they imply that a system has a deterministic stable state. This is necessary in a range of control problems where randomised strategies are not appropriate (e.g., in industrial processing or transport applications). Also, unlike mixed strategy and correlated equilibria, PSNE do not rely on the assumption that agents have the capacity to accurately randomise their actions according to an equilibrium prescription.
We will introduce some important classes of non-cooperative games with pure strategy equilibria, putting the emphasis on computational aspects of achieving such stable outcomes (including centralised algorithms and natural decentralised dynamics). The main focus will be on congestion (potential) games and some of their recent generalisations. Finally, we will discuss how equilibrium dynamics traditionally studied in these settings can be applied in other domains (e.g., voting games).