Teoria dos Jogos Algorítmica - 2º Semestre 2014
- Prof: Rafael C. S. Schouery - rafael@ic.unicamp.br
- Aulas: Segundas e Quartas, às 14:00 - Sala IC 352 (IC 3.5)
- Atendimento: Quartas, às 16:00, na sala do Prof. Flávio Keidi Miyazawa
- Oferecida como Tópicos em Teoria da Computação - MC918B/MO829B
Importante: Enviar um email para rafael@ic.unicamp.br avisando a participação no atendimento com pelo menos 24 horas de antecedência.
Seminários
Os seminários serão individuais e com duração de uma hora e trinta minutos. Os slides deverão ser exportados para pdf.
Os alunos serão avaliados por:
- Domínio do conteúdo apresentado
- Qualidade da apresentação oral
- Qualidade dos slides
Cada aluno deve enviar um email para rafael@ic.unicamp.br informando o conteúdo que irá apresentar até o dia 10/11/14.
Abaixo está a lista dos conteúdos escolhidos, as datas e quem irá apresentar o conteúdo.
- Gabriel Militão Vinhas Lopes (26/11): Nim e o Teorema de Sprague-Grundy
- Helen Mae Koike Fornazier (01/12): Manipulation-Resistant Reputation Systems
- André Luís de Lannoy Coimbra Tavares (03/12): Cost Sharing
- Marcos Massayuki Kobuchi (10/12): Incentives in Peer-to-Peer Systems
- Vinícius Pimentel Couto (15/12): Learning, Regret Minimization, and Equilibria
Não é necessário apresentar todo o conteúdo nem todos os detalhes do capítulo. O importante é que os outros alunos consigam entender o conteúdo passado e como isso se relaciona com o conteúdo estudado durante o curso. Porém, tome cuidado para não remover coisas demais e terminar a apresentação muito antes do tempo planejado.
Listas
- Lista 1 - Entregar na aula do dia 15/09
- Lista 2 - Entregar na aula do dia 24/09
- Lista 3 - Entregar na aula do dia 08/10 (gabarito)
- Lista 4 - Entregar na aula do dia 20/10
- Lista 5 - Entregar na aula do dia 05/11
- Lista 6 - Entregar na aula do dia 17/11 Nova data!
Slides (as versões handout podem ter algumas falhas)
- Regras da Disciplina - handout
- Parte 1 - Noções de Equilíbrio - handout
- Parte 2 - Complexidade Computacional - handout
- Parte 3 - Jogos de Balanceamento de Cargas - handout
- Parte 4 - Jogos de Formação de Redes - handout
- Parte 5 - Jogos de Roteamento - handout
- Parte 6 - Projeto de Mecanismos - handout
- Parte 7 - Projeto de Mecanismos sem Dinheiro - handout
- Parte 8 - Leilões Combinatórios - handout
- Parte Final - handout
Calendário
- Início: 01/09/2014
- Término: 23/12/2014
- Prova: 15/10/2014
- Exame (Graduação): 19/01/2015
- Não teremos aula em 08/12 - Não haverá atividades segundo a DAC
Ementa:
- Introdução a jogos e conceitos básicos de soluções
- Complexidade computacional de encontrar equilíbrios de Nash
- Teoria da Escolha Social
- Projeto de Mecanismos
- Leilões combinatórios
- Leilões em buscas patrocinadas
- Jogos de formação de redes
- Jogos de balanceamento de carga
- Ineficiência de equilíbrios (preço da estabilidade e da anarquia)
Bibliografia:
- Noam Nisan, Tim Roughgarden, Eva Tardos, e Vijay V. Vazirani, editores. Algorithmic Game Theory, Cambridge University Press, 2007. (Errata)
- Flávio Keidi Miyazawa, Introdução à Teoria dos Jogos Algorítmica, ch. 8, pp. 365-417, XXIX Jornada de Atualização em Informática da SBC, 2010, pp. 365-417.
- Drew Fudenberg e Jean Tirole. Game Theory. MIT Press, 1991.
- Peter Cramton, Yoav Shoham e Richard Steinberg, editores. Combinatorial Auctions. MIT Press, 2006.