MC758A/MO758A - Teoria dos Jogos Algorítmica - 1º Semestre 2018
-
Prof: Rafael C. S. Schouery
- rafael@ic.unicamp.br
- Sala 74 - Instituto de Computação
-
Aulas: Terças e Sextas na 352 (IC3,5), às 16:00
Informações
- Notas Finais
- Notas dos Seminários
- Plano de Desenvolvimento da Disciplina
- Início: 27/02 (terça-feira)
- Não teremos aula em 30/03 (feriado)
- Não teremos aula em 01/05 (feriado)
- Não teremos aula em 08/05 (avaliação de cursos)
- Não teremos aula em 01/06 (feriado)
Listas
- Lista 1 - Entregar na aula do dia 20/03
- Lista 2 - Entregar na aula do dia 27/03
- Lista 3 - Entregar na aula do dia 10/04
- Lista 4 - Entregar na aula do dia 20/04
- Lista 5 - Entregar na aula do dia 01/05
- Lista 6 - Entregar na aula do dia 22/05
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/18.
Abaixo está a lista dos conteúdos sugeridos:
Learning, Regret Minimization, and Equilibria (Cap 4 - Nisan et al.)Wellington- Computationally Efficient Approximation Mechanisms (Cap 12 - Nisan et al.)
Routing Games (Cap 18 - Nisan et al.)JuliaSponsored Search Auctions (Cap 28 - Nisan et al.)ErikFurther solution concepts for normal-form games (Seção 3.4 do livro Multiagent Systems)DiegoRicher Representations: Beyond the Normal and Extensive Forms (Cap 6 - Multiagent Systems)LucasAlgoritmo de Lemke-Howson para encontrar um equilíbrio (Capítulo 4 de Multiagent Systems ou Capítulo 2 e 3 de Nisan et al.)Julen- Protocols for Multiagent Resource Allocation: Auctions (Cap 11 do Multiagent Systems)
- Combinatorial Algorithms for Market Equilibria (Cap 5 - Nisan et al.)
- Incentives and Pricing in Communications Networks (Cap 22 - Nisan et al.)
Cascading Behavior in Networks: Algorothmic and Economic Issues (Cap 24 - Nisan et al.)Pedro- Algun capítulo do livro Combinatorial Auctions (com conteúdo que não tenha sido abordado no curso)
- Feldman M., Snappir Y., Tamir T. (2017) The Efficiency of Best-Response Dynamics. In: Bilò V., Flammini M. (eds) Algorithmic Game Theory. SAGT 2017. Lecture Notes in Computer Science, vol 10504. Springer, Cham
Chauhan A., Lenzner P., Melnichenko A., Molitor L. (2017) Selfish Network Creation with Non-uniform Edge Cost. In: Bilò V., Flammini M. (eds) Algorithmic Game Theory. SAGT 2017. Lecture Notes in Computer Science, vol 10504. Springer, ChamKlairton- Michal Feldman, Amos Fiat, and Alan Roytman. 2017. Makespan Minimization via Posted Prices. In Proceedings of the 2017 ACM Conference on Economics and Computation (EC ‘17). ACM, New York, NY, USA, 405-422.
- Azar Y., Feldman M., Gravin N., Roytman A. (2017) Liquid Price of Anarchy. In: Bilò V., Flammini M. (eds) Algorithmic Game Theory. SAGT 2017. Lecture Notes in Computer Science, vol 10504. Springer, Cham
- Shahar Dobzinski and Shahar Ovadia. 2017. Combinatorial Cost Sharing. In Proceedings of the 2017 ACM Conference on Economics and Computation (EC ‘17). ACM, New York, NY, USA, 387-404.
- Yakov Babichenko, Yuval Emek, Michal Feldman, Boaz Patt-Shamir, Ron Peretz, and Rann Smorodinsky. 2017. Stable Secretaries. In Proceedings of the 2017 ACM Conference on Economics and Computation (EC ‘17). ACM, New York, NY, USA, 243-244.
- Gupta, A., Könemann, J., Leonardi, S., Ravi, R., Schäfer, G. Math. Program. (2015) 152: 147.
K. R. Apt, B. de Keijzer, M. Rahn, G. Schäfer and S. Simon. Coordination games on graphs. International Journal of Game Theory, 46(3):851-877, 2017Jadder- 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
- 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
- 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 (coluna simples) por resumo.
Ordem de Apresentação
- Pedro - 08/06 - Cascading Behavior in Networks: Algorothmic and Economic Issues resumo slides
- Julia - 12/06 - Routing Games resumo slides
- Erik - 12/06 - Sponsored Search Auctions resumo slides
- Alonso - 15/06 - Jogos Combinatórios resumo slides
- Klairton - 15/06 - Selfish Network Creation with Non-uniform Edge Cost resumo slides
- Julen - 19/06 - Algoritmo de Lemke-Howson para encontrar um equilíbrio
- Hugo - 19/06 - Tree Nash Equilibria in the Network Creation Game resumo slides
- Lucas - 22/06 - Richer Representations: Beyond the Normal and Extensive Forms resumo slides
- Raphael - 22/06
- Italos - 26/06 - Fractional hedonic games resumo slides
- Jadder - 26/06 - Coordination games on graphs resumo slides
- Wellington - 29/06 - Learning, Regret Minimization, and Equilibria (Cap 4 - Nisan et al.) resumo slides
- Diego - 29/06 - Further solution concepts for normal-form games resumo slides
Links Úteis/Interessantes
- 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
- Make Me a Match: A New Freakonomics Radio Episode - Entrevista com o Al Roth
- Arrow’s Impossibility Theorem - Infinite Series
Slides
- 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
- Parte Final
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.