CS 698I: Relational Structures in Games

Units: 3-0-0-0 (9)

Pre-requisites: CS345. A background in game theory is not required.

Course Description

Game theory, a field which originated in the intersection of mathematics and economics offers models to analyse strategic interaction of rational agents. Game theoretic models are often used as tools in the analysis of multi-agent systems in computer science. From the perspective of computer science and artificial intelligence, representation and computational complexity of various game models is a pertinent issue. Representing multiplayer games using many of the standard game theoretic models studied in economics (like strategic games) is problematic for various reasons. The parameters needed to represent games in such models usually grows exponentially with the number of players. Such game models also abstract the underlying structure present in the multiplayer game, which typically plays a crucial role in the algorithmic analysis. Thus representations which are compact and those that naturally model the underlying structure of multiplayer games are important. The main goal of this course is to study the representational and algorithmic aspects of models of multiplayer interaction. This includes game theoretic models as well as those studied in social choice theory. We will primarily study topics and address questions at the interface of theoretical computer science and economics. The topics include the following.

1. Basics of game theory - models and solution concepts
   1. Strategic form games, pure and mixed strategies
   2. Extensive games with perfect information
   3. Dominance and equilibrium
2. Models with compact representations
   1. Graphical games
   2. Polymatrix games
   3. Coalition formation games
   4. Coordination games
3. Algorithmic analysis
   1. Hardness in computation of equilibria
   2. Efficient computation via structural restrictions
   3. Algorithmic analysis of various fair division models

References

1. Algorithmic Game Theory - N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani. Cambridge University Press (PDF available on publisher's website)
2. Twenty Lectures on Algorithmic Game Theory - T. Roughgarden. Cambridge University Press
3. Handbook of Computational Social Choice - F. Brandt, V. Conitzer, U. Endriss, J. Lang and A.D. Procaccia. Cambridge University Press
4. A Course in Game Theory - M.J. Osborne and A. Rubinstein, MIT Press (PDF available on Rubinstein's homepage)
5. Various research papers