Teoria dos Jogos Algorítmica - 1º Semestre 2017
- Prof: Rafael C. S. Schouery
- rafael@ic.unicamp.br
- Sala 74 - Instituto de Computação
- Aulas: Terças e Quintas, às 14:00 (Sala 352 - IC3)
- Atendimento: Terças, às 16:00, sala 74
- Oferecida como Tópicos em Teoria da Computação - MC918A/MO829A
Informações
- Plano de Desenvolvimento da Disciplina
- Planilha de Notas atualizada
- Início: 02/03 (quinta-feira)
- Não teremos aula em 13/04 (quinta-feira)
- Não teremos aula em 15/06 (quinta-feira)
Listas
- Lista 1 - Entregar na aula do dia 28/03
- Lista 2 - Entregar na aula do dia 18/04
- Lista 3 - Entregar na aula do dia 02/05
- Lista 4 - Entregar na aula do dia 23/05
- Lista 5 - Entregar na aula do dia 13/06 adiamento
- Lista 6 - Entregar na aula do dia 29/06
Seminários e Resumo
Os seminários serão individuais e com duração de quarenta 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 18/05/17.
Abaixo está a lista dos conteúdos sugeridos (posteriormente, serão adicionados os alunos e as datas dos seminários):
- Learning, Regret Minimization, and Equilibria (Cap 4 - Nisan et al.)
Graphical Games (Cap 7 - Nisan et al.)- Eric Inui- Computationally Efficient Approximation Mechanisms (Cap 12 - Nisan et al.)
- Routing Games (Cap 18 - Nisan et al.)
- Incentives in Peer-to-Peer Systems (Cap 23 - Nisan et al.)
- Manipulation-Resistant Reputation Systems (Cap 27 - Nisan et al.)
- Sponsored Search Auctions (Cap 28 - Nisan et al.)
Computational Evolutionay Game Theory (Cap 29 - Nisan et al.)- Gabriel Henriques Siqueira- The Lovely but Lonely Vickrey Auction (Cap 1 - Cramton, Shoham and Steinberg. Combinatorial Auctions, The MIT Press, 2010)
- R. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1), 1981
- S. Dobzinski and N. Nisan (2010) “Mechanisms for Multi-Unit Auctions”, Journal of Artificial Intelligence Research, Volume 37, pages 85-98, 2010
Noam Nisan, Michael Schapira, Greg Valiant, Aviv Zohar “Best-Response Mechanisms”, Innovations in Computer Science - ICS 2011, pages 155-165, 2011- Sergio Zumpano Arnosti- Shahar Dobzinski, Noam Nisan, Michael Schapira, Truthful randomized mechanisms for combinatorial auctions, Journal of Computer and System Sciences, Volume 78, Issue 1, 2012, Pages 15-25
Ron Lavi, Noam Nisan, Online ascending auctions for gradually expiring items, Journal of Economic Theory, Volume 156, March 2015, Pages 45-76- Hugo DjemaaDavid Kempe, Jon M. Kleinberg, Éva Tardos: Maximizing the Spread of Influence through a Social Network. Theory of Computing 11: 105-147 (2015)- Kleber Andrade Oliveira- Gagan Goel, Mohammad Reza Khani, and Renato Paes Leme. 2015. Core-competitive Auctions. In Proceedings of the Sixteenth ACM Conference on Economics and Computation (EC ‘15). ACM, New York, NY, USA, 149-166.
- Artigos de periódicos como ACM Trans. Economics and Comput., J. Economic Theory, Games and Economic Behavior, etc
- Artigos de conferências como SAGT, EC, FOCS, STOC, SODA, ICALP, etc
No seminário não é necessário apresentar todo o conteúdo nem todos os detalhes do capítulo/artigo. 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 ou fazer uma apresentação muito rasa.
Os resumos devem ser entregues até o dia 29/06 em PDF pelo email rafael@ic.unicamp.br e devem conter o conteúdo apresentado no seminário de forma resumida. Porém, é necessário descrever corretamente o problema, a notação utilizada e provar lemas e teoremas relevantes. Faça também uma introdução e um abstract. O limite é de 4 páginas por resumo.
Ordem de Apresentação
- Sergio Ricardo Rodolfo de Sa (06/06) - Y. Zhou, Y. Li, G. Sun, D. Jin, L. Su and L. Zeng, “Game Theory Based Bandwidth Allocation Scheme for Network Virtualization,” IEEE Global Telecommunications Conference, 2010, pp. 1-5. - Slides Resumo
- Hugo Alexis Benjamin Djemaa (08/06) - Ron Lavi, Noam Nisan, Online ascending auctions for gradually expiring items, Journal of Economic Theory, Volume 156, March 2015, Pages 45-76 - Slides Resumo
- Yulle Glébbyo Felipe Borges (08/06) - Nadine Hajj and Mariette Awad, “A Game Theory Approach to Demand Side Management in Smart Grids”, Intelligent Systems, pp 807-819, 2014 - Slides Resumo
- Leonardo Yvens Schwarzstein (13/06) - Leilões aplicados a compartilhamento dinâmico de viagens [1][2] - Slides Resumo
- Giancarlo Maricato Di Bella (13/06) - Bayesian Games (Cap 6 - Shoham e Leyton-Brown)
- Gabriel Henriques Siqueira (20/06) - Computational Evolutionay Game Theory (Cap 29 - Nisan et al.) - Resumo
- Kleber Andrade Oliveira (20/06) - David Kempe, Jon M. Kleinberg, Éva Tardos: Maximizing the Spread of Influence through a Social Network. Theory of Computing 11: 105-147 (2015) - Slides Resumo
- Felipe Lemes Galvão (22/06) - Moran Feldman, Liane Lewin-Eytan, and Joseph (Seffi) Naor. 2015. Hedonic Clustering Games. ACM Trans. Parallel Comput. 2, 1, Article 4 (May 2015), 48 pages. - Slides Resumo
- Fábio Harada Kubo (22/06) - Cryptography and Game Theory (Cap 8 - Nisan et al.) - Slides - Slides Resumo
- Sergio Zumpano Arnosti (27/06) - Noam Nisan, Michael Schapira, Greg Valiant, Aviv Zohar “Best-Response Mechanisms”, Innovations in Computer Science - ICS 2011, pages 155-165, 2011 - Slides Resumo
- Eric Inui (27/06) - Graphical Games (Cap 7 - Nisan et al.) - Slides Resumo
- Antonio José Pinheiro Prado (29/06) - Peters and Gell-Mann, “Evaluating gambles using dynamics”, Chaos: An Interdisciplinary Journal of Nonlinear Science. 26(2) - Slides Resumo
- Francisco Jhonatas Melo da Silva (29/06) - Renato Paes Leme, Vasilis Syrgkanis, and Éva Tardos. 2012. The curse of simultaneity. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS ‘12). pages 60-67, 2012 - Slides Resumo
Links Úteis
- CS364A: Algorithmic Game Theory (Fall 2013) - Stanford - aulas e notas de aula de Tim Roughgarden
- Game Theory Online - aulas de Matt Jackson, Yoav Shoham, and Kevin Leyton-Brown
- Turing’s Invisible Hand - blog sobre Teoria dos Jogos Algorítmica
- Golden Balls - £100,000 Split Or Steal? 14/03/08 - programa de TV com Teoria dos Jogos
- Infinite Chess - um pouco sobre xadrez, estratégias dominantes e jogos na forma extensiva
- Facebook Doesn’t Make as Much Money as It Could—On Purpose - Uso do VCG no leilão de anúncios do Facebook novo!
- Make Me a Match: A New Freakonomics Radio Episode - Entrevista com o Al Roth novo!
- Arrow’s Impossibility Theorem - Infinite Series novo!
Slides (as versões handout podem ter algumas falhas)
- Regras da Disciplina
- Parte 1 - Jogos e Soluções - handout
- Parte 2 - Complexidade computacional para TJA - handout
- Parte 3 - Jogos de Balanceamento de Carga - handout
- Parte 4 - Formação de Redes - handout
- Parte 5 - Projeto de Mecanismos - handout
- Parte 6 - Leilões - handout
- Parte 7 - Mecanismos sem dinheiro - handout
- Parte 8 - Compartilhamento de Custos - handout
Programa da disciplina
- Introdução a jogos e conceitos básicos de solução de jogos
- Jogos na forma extensiva
- Complexidade computacional e teoria dos jogos
- Jogos de formação de redes
- Jogos de balanceamento de carga
- Teoria da escolha social
- Mecanismos sem dinheiro
- Leilões
- Mecanismo VCG
- Jogos cooperativos e compartilhamento de custos
Bibliografia (com links para os livros)
- Rafael C. S. Schouery, Orlando Lee, Flávio K. Miyazawa, and Eduardo C. Xavier. Tópicos da teoria dos jogos em computação. 30º Colóquio Brasileiro de Matemática - Instituto de Matemática Pura e Aplicada. Editora do IMPA, 2015.
- Noam Nisan, Tim Roughgarden, Eva Tardos, e Vijay V. Vazirani, editores. Algorithmic Game Theory, Cambridge University Press, 2007. (Errata)
- Shoham, Yoav, and Kevin Leyton-Brown. Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008.
- 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.
- David Easley, Jon Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.