MC758 - Teoria dos Jogos Algorítmica

Créditos: 4
Horas semanais de atividades teóricas: 4
Oferecimento: A critério da unidade de ensino
 
Pré-Requisitos
MC558
Ementa

Jogos e conceitos básicos de soluções. Teoria dos Jogos e Complexidade Computacional. Ineficiência de equilíbrios. Mecanismos e Leilões. Compartilhamento de Custos.

Programa

1. Conceitos básicos de solução de jogos.

    (a) Definição de jogo.

    (b) Resposta ótima.

     (c) Equilíbrio de Nash.

     (d) Estratégia Mista.

2. Complexidade computacional e Teoria dos Jogos.

    (a) Representação sucinta de jogos.

    (b) Complexidade de encontrar um equilíbrio de Nash.

3. Ineficiência de equilíbrios. Sugestão de exemplos:

    (a) Jogos de formacão de redes.

    (b) Jogos de balanceamento de carga.

4. Mecanismos e Leilões:

    (a) Escolha Social e Teorema de Arrow.

    (b) Mecanismos.

     (c) Leilões.

5. Compartilhamento de Custos:

     (a) Jogos cooperativos.

     (b) Núcleo de um jogo cooperativo.

     (c) Valor de Shapley.
 

Bibliografia
1. Rafael C. S. Schouery, Orlando Lee, Flavio K. Miyazawa, and Eduardo C. Xavier. Topicos da teoria dos jogos em computação. 30º Coloquio Brasileiro de Matematica - Instituto de Matematica Pura e Aplicada. Editora do IMPA, 2015.
2. Noam Nisan, Tim Roughgarden, Eva Tardos, e Vijay V. Vazirani, editores. Algorithmic Game Theory, Cambridge University Press, 2007.
3. Shoham, Yoav, and Kevin Leyton-Brown. Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008.
4. Flavio Keidi Miyazawa, Introdução a Teoria dos Jogos Algor tmica, ch. 8, pp. 365-417, XXIX Jornada de Atualização em Informatica da SBC, 2010, pp. 365-417.
5. Drew Fudenberg e Jean Tirole. Game Theory. MIT Press, 1991.
6. Peter Cramton, Yoav Shoham e Richard Steinberg, editores. Combinatorial Auctions. MIT Press, 2006.