There has been a recent renewed interest in Game Theory in many areas of Computer Science, notably when confronted with settings where self-interested parties interact. Notable examples can be found in electronic marketplaces and networked computer systems. In the AI community, Game Theory has emerged as one of the dominant formalisms for studying strategic and cooperative interaction in systems of autonomous agents. To act optimally in such scenarios, agents must take into account how other agents are likely to act. Game Theory provides the mathematical foundations to study such systems, namely by providing various solution concepts, which prescribe how agents ought to act when other agents’ actions are bound to affect their utilities.

Prescribing how agents should act in a given scenario (game) is only one side of the coin. Someone has to design the game (the rules of the marketplace, network protocols, etc.) and this task often falls into the lap of computer scientists. Whereas we cannot force self-interested agents to behave in a specific manner, we can give them incentives to behave in a desirable manner. Mechanism design studies the design of the game (or mechanism) so that self-interested agents behave in a way that leads to good outcomes.

The rapidly emerging field of Computational Game Theory and Mechanism Design complements traditional (mathematical) Game Theory and Mechanism Design by addressing related computational issues, providing algorithms e.g. to design mechanisms, prescribe agent’s actions, compute solutions, etc.

In this course we will cover the basic concepts of Game Theory and Mechanism Design, with an emphasis on their computational/algorithmic aspects.

Game Theory

Utility Theory, Games in Normal-Form, Pareto optimality, Best response and Nash equilibrium, Mixed Strategies, Maxmin and Minmax, Correlated Equilibrium, Perfect-Information Extensive-Form Games, Subgame Perfection, Backward Induction, Imperfect-Information Extensive-Form Games, Perfect Recall, Repeated Games, Infinitely Repeated Games, Bayesian Games.

Mechanism Design

Social Choice, Voting, Voting Paradoxes, Arrow''''''''s Theorem, Muller-Satterthwaite Theorem, Mechanisms with money, VCG mechanism, Auctions, Mechanisms without Money.

Yoav Shoham and Kevin Leyton-Brown , Essentials of Game Theory: A Concise Multidisciplinary Introduction, Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers, 2008.

Yoav Shoham and Kevin Leyton-Brown, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press, 2009.

Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay V. Vazirani (Eds.), Algorithmic Game Theory, Cambridge University Press, 2007.

JAVA programming.