The course is a graduate-level introduction to game theory, and to its applications to system design and system control.
The course starts with a brief introduction to multi-player games, presenting the classical definition of Nash equilibria, and proving their existence under general conditions.
Next, we consider 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. We consider in particular repeated zero-sum games played over graphs. In these games, at each round, the players simultaneously and independently select moves; the moves jointly determine the transition to the successor state. These games are widely used in control and verification, as model of the behavior of a system subject to control actions (player 1) and nondeterminism and unpredictable events (player 2). We will show how to solve these games for a variety of goals, including reachability (reaching a control goal), safety (ensuring the system behavior never leaves a safe operating region), and average cost/reward.
We then move to non-zero-sum games, where players can have different goals, and we study the problem of mechanism design: how to make up the rules of the game to ensure that the players, while playing for their own benefit, achieve some globally desirable behavior. We will look at applications in auctions and network control.
Finally, we will briefly discuss some applications of games to emerging application areas, from reputation systems, to electronic commerce.
Tentative Weekly Schedule
- Introduction, proof of existence of Nash equilibria
- Evolutionary equilibria, Bayesian games
- Repeated games over graphs: the deterministic, turn-based setting. Safety and reachability.
- Simple stochastic models: Markov Chains and Markov decision processes.
- Fixpoint theory
- Practical techniques for Markov decision processes.
- Simultaneous and stochastic games: safety, reachability
- Discounted games
- Mechanism design: general results, and some applications
- Games in new application areas