Teoria de Jogos Computacional (2017/2018) - Departamento de Informática
Descrição

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.

Objectivos

Os objetivos da UC são:

  • Introduzir o aluno à noção de jogo, aos seus variados conceitos de solução, bem como a outras noções e ferramentas básicas da Teoria de Jogos, bem como às principais áreas de aplicação em que podem ser utilizadas;
  • Formalizar a noção de pensamento estratégico e escolha racional usando as ferramentas da Teoria de Jogos, e fornecer conhecimento sobre a adopção da Teoria de Jogos no desenho de aplicações.
  • Estabelecer as ligações entre a Teoria de Jogos, Ciências da Computação e Economia, com ênfase nos aspectos computacionais.
  • Introduzir temas contemporâneos na interseção da Teoria de Jogos, Ciências da Computação e Economia.
Programa

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.

Bibliografia Principal

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.

Requisitos Prévios

Programação em JAVA

Esforço do Aluno
  Horas por crédito 28
  Horas p/ semana Semanas Horas
Aulas práticas e laboratoriais 2 13 26.0
Aulas teóricas 2 13 26.0
Avaliação   4.0
Estudo   54.0
Projectos e trabalhos   58.0
Total de Horas 168
ECTS 6.0