The course is a graduate-level introduction to game theory, and to its applications to system design and system control.
The course starts by considering zero-sum games, which are two-player games where the players have opposite goals, so that a gain for a player is an equal loss for the other. These games are widely used in control and verification. Control problems can often be cast as a game between the controller, which has a choice of control actions (represented as controller moves), and the system, which has a choice of possible behaviors (represented as system moves). In verification, games are used to analyze the relationship between components of a system. The main problem considered, in this first part of the course, is the computation of winning strategies in the games. We will also introduce similarity notions that enable us to compare games.
From zero-sum games, the course then moves to multi-player games, where the goals of the players are not necessarily contrasting. These games are used to model a variety of interaction in system an economics, among which resource sharing in networks and multi-user systems and auctions. In considering these games, our emphasis shifts from the computation of winning strategies to the structural characteristics of the games. In particular, we consider the problem of mechanism design: how to design games to obtain a desired emergent behavior from the players. In other words, the goal is to set the rules of the games, so that what is an optimal strategy for each player, has also a desirable societal outcome. Auctions, and bandwith sharing over a network, are two cases where mechanism design can be used to ensure fair allocation of resources.
Finally, the course concludes with an exploration of current topics in game theory, as applied to reputation systems, interaction over the web, electronic auctions, and more.