MC918/MO829Tópicos em Teoria da Computação
Teoria dos Jogos Algorítmica
Rafael C. S. [email protected]
Universidade Estadual de Campinas
2º semestre/2014
Avaliação
• 1 Prova
• Listas de exercícios
• 1 Apresentação de Seminário
2
Avaliação
• 1 Prova
• Listas de exercícios
• 1 Apresentação de Seminário
2
Avaliação
• 1 Prova
• Listas de exercícios
• 1 Apresentação de Seminário
2
Avaliação
• 1 Prova
• Listas de exercícios
• 1 Apresentação de Seminário
2
Cálculo da Média
• P : nota da prova• L : média simples das notas das listas• S : nota do seminário• α ∈ [0, 1] : nota adicional de participação
Média = max{P + L+ S
3+ α, 10.0
}
3
Cálculo da Média
• P : nota da prova
• L : média simples das notas das listas• S : nota do seminário• α ∈ [0, 1] : nota adicional de participação
Média = max{P + L+ S
3+ α, 10.0
}
3
Cálculo da Média
• P : nota da prova• L : média simples das notas das listas
• S : nota do seminário• α ∈ [0, 1] : nota adicional de participação
Média = max{P + L+ S
3+ α, 10.0
}
3
Cálculo da Média
• P : nota da prova• L : média simples das notas das listas• S : nota do seminário
• α ∈ [0, 1] : nota adicional de participação
Média = max{P + L+ S
3+ α, 10.0
}
3
Cálculo da Média
• P : nota da prova• L : média simples das notas das listas• S : nota do seminário• α ∈ [0, 1] : nota adicional de participação
Média = max{P + L+ S
3+ α, 10.0
}
3
Cálculo da Média
• P : nota da prova• L : média simples das notas das listas• S : nota do seminário• α ∈ [0, 1] : nota adicional de participação
Média = max{P + L+ S
3+ α, 10.0
}
3
Calendário
• Início: 01/09/2014
• Prova: 15/10/2014
• Término: 22/12/2014
• Exame (Graduação): 19/01/2015
Não teremos aula em:• 22/10 - Congresso de Iniciação Científica
• 27/10 - Dia do servidor público
• 08/12 - Não haverá atividades segundo a DAC
4
Calendário
• Início: 01/09/2014
• Prova: 15/10/2014
• Término: 22/12/2014
• Exame (Graduação): 19/01/2015
Não teremos aula em:• 22/10 - Congresso de Iniciação Científica
• 27/10 - Dia do servidor público
• 08/12 - Não haverá atividades segundo a DAC
4
Calendário
• Início: 01/09/2014
• Prova: 15/10/2014
• Término: 22/12/2014
• Exame (Graduação): 19/01/2015
Não teremos aula em:• 22/10 - Congresso de Iniciação Científica
• 27/10 - Dia do servidor público
• 08/12 - Não haverá atividades segundo a DAC
4
Calendário
• Início: 01/09/2014
• Prova: 15/10/2014
• Término: 22/12/2014
• Exame (Graduação): 19/01/2015
Não teremos aula em:• 22/10 - Congresso de Iniciação Científica
• 27/10 - Dia do servidor público
• 08/12 - Não haverá atividades segundo a DAC
4
Calendário
• Início: 01/09/2014
• Prova: 15/10/2014
• Término: 22/12/2014
• Exame (Graduação): 19/01/2015
Não teremos aula em:• 22/10 - Congresso de Iniciação Científica
• 27/10 - Dia do servidor público
• 08/12 - Não haverá atividades segundo a DAC
4
Calendário
• Início: 01/09/2014
• Prova: 15/10/2014
• Término: 22/12/2014
• Exame (Graduação): 19/01/2015
Não teremos aula em:
• 22/10 - Congresso de Iniciação Científica
• 27/10 - Dia do servidor público
• 08/12 - Não haverá atividades segundo a DAC
4
Calendário
• Início: 01/09/2014
• Prova: 15/10/2014
• Término: 22/12/2014
• Exame (Graduação): 19/01/2015
Não teremos aula em:• 22/10 - Congresso de Iniciação Científica
• 27/10 - Dia do servidor público
• 08/12 - Não haverá atividades segundo a DAC
4
Calendário
• Início: 01/09/2014
• Prova: 15/10/2014
• Término: 22/12/2014
• Exame (Graduação): 19/01/2015
Não teremos aula em:• 22/10 - Congresso de Iniciação Científica
• 27/10 - Dia do servidor público
• 08/12 - Não haverá atividades segundo a DAC
4
Calendário
• Início: 01/09/2014
• Prova: 15/10/2014
• Término: 22/12/2014
• Exame (Graduação): 19/01/2015
Não teremos aula em:• 22/10 - Congresso de Iniciação Científica
• 27/10 - Dia do servidor público
• 08/12 - Não haverá atividades segundo a DAC
4
Regras da Disciplina
• Perguntas podem/devem ser feitas durante as aulas
• A prova é individual e sem consulta
• As listas podem ser discutidas em grupo:
▶ Cada aluno escreve a sua própria resposta para osexercícios
▶ E deve identificar na lista com quem discutiu osexercícios
• Em caso de cola, as devidas providências serãotomadas
5
Regras da Disciplina
• Perguntas podem/devem ser feitas durante as aulas
• A prova é individual e sem consulta
• As listas podem ser discutidas em grupo:
▶ Cada aluno escreve a sua própria resposta para osexercícios
▶ E deve identificar na lista com quem discutiu osexercícios
• Em caso de cola, as devidas providências serãotomadas
5
Regras da Disciplina
• Perguntas podem/devem ser feitas durante as aulas
• A prova é individual e sem consulta
• As listas podem ser discutidas em grupo:
▶ Cada aluno escreve a sua própria resposta para osexercícios
▶ E deve identificar na lista com quem discutiu osexercícios
• Em caso de cola, as devidas providências serãotomadas
5
Regras da Disciplina
• Perguntas podem/devem ser feitas durante as aulas
• A prova é individual e sem consulta
• As listas podem ser discutidas em grupo:
▶ Cada aluno escreve a sua própria resposta para osexercícios
▶ E deve identificar na lista com quem discutiu osexercícios
• Em caso de cola, as devidas providências serãotomadas
5
Regras da Disciplina
• Perguntas podem/devem ser feitas durante as aulas
• A prova é individual e sem consulta
• As listas podem ser discutidas em grupo:
▶ Cada aluno escreve a sua própria resposta para osexercícios
▶ E deve identificar na lista com quem discutiu osexercícios
• Em caso de cola, as devidas providências serãotomadas
5
Regras da Disciplina
• Perguntas podem/devem ser feitas durante as aulas
• A prova é individual e sem consulta
• As listas podem ser discutidas em grupo:
▶ Cada aluno escreve a sua própria resposta para osexercícios
▶ E deve identificar na lista com quem discutiu osexercícios
• Em caso de cola, as devidas providências serãotomadas
5
Regras da Disciplina
• Perguntas podem/devem ser feitas durante as aulas
• A prova é individual e sem consulta
• As listas podem ser discutidas em grupo:
▶ Cada aluno escreve a sua própria resposta para osexercícios
▶ E deve identificar na lista com quem discutiu osexercícios
• Em caso de cola, as devidas providências serãotomadas
5
Atendimento
• Quartas-feiras, 16h
• Sala do Prof. Flávio Keidi Miyazawa
Enviar email para [email protected] avisando aparticipação pelo menos 24 horas antes!
6
Atendimento
• Quartas-feiras, 16h• Sala do Prof. Flávio Keidi Miyazawa
Enviar email para [email protected] avisando aparticipação pelo menos 24 horas antes!
6
Atendimento
• Quartas-feiras, 16h• Sala do Prof. Flávio Keidi Miyazawa
Enviar email para [email protected] avisando aparticipação pelo menos 24 horas antes!
6
Página da disciplina
http://ic.unicamp.br/∼schouery/cursos/agt2014/
• Slides
• Regras
• Avisos
• E outros...
7
Página da disciplina
http://ic.unicamp.br/∼schouery/cursos/agt2014/
• Slides
• Regras
• Avisos
• E outros...
7
Página da disciplina
http://ic.unicamp.br/∼schouery/cursos/agt2014/
• Slides
• Regras
• Avisos
• E outros...
7
Página da disciplina
http://ic.unicamp.br/∼schouery/cursos/agt2014/
• Slides
• Regras
• Avisos
• E outros...
7
Página da disciplina
http://ic.unicamp.br/∼schouery/cursos/agt2014/
• Slides
• Regras
• Avisos
• E outros...
7
Página da disciplina
http://ic.unicamp.br/∼schouery/cursos/agt2014/
• Slides
• Regras
• Avisos
• E outros...
7
Bibliografia
N. Nisan, T. Roughgarden, E. Tardos e V.V. Vazirani, editores. Algorithmic GameTheory, Cambridge University Press,2007.
http://bit.ly/nisan-agt
8
Bibliografia
N. Nisan, T. Roughgarden, E. Tardos e V.V. Vazirani, editores. Algorithmic GameTheory, Cambridge University Press,2007.
http://bit.ly/nisan-agt
8
Bibliografia
N. Nisan, T. Roughgarden, E. Tardos e V.V. Vazirani, editores. Algorithmic GameTheory, Cambridge University Press,2007.
http://bit.ly/nisan-agt
8
Bibliografia• F. K. Miyazawa. Introdução à Teoria dos Jogos
Algorítmica, ch. 8, pp. 365-417, XXIX Jornada deAtualização em Informática da SBC, 2010, pp.365-417. http://bit.ly/flavio-agt
• D. Easley e J. Kleinberg. Networks, Crowds, andMarkets. Cambridge University Press, 2010.http://bit.ly/networks-book
• D. Fudenberg e J. Tirole. Game Theory. MIT Press,1991.
• P. Cramton, Y. Shoham e R. Steinberg, editores.Combinatorial Auctions. MIT Press, 2006.
9
Bibliografia• F. K. Miyazawa. Introdução à Teoria dos Jogos
Algorítmica, ch. 8, pp. 365-417, XXIX Jornada deAtualização em Informática da SBC, 2010, pp.365-417. http://bit.ly/flavio-agt
• D. Easley e J. Kleinberg. Networks, Crowds, andMarkets. Cambridge University Press, 2010.http://bit.ly/networks-book
• D. Fudenberg e J. Tirole. Game Theory. MIT Press,1991.
• P. Cramton, Y. Shoham e R. Steinberg, editores.Combinatorial Auctions. MIT Press, 2006.
9
Bibliografia• F. K. Miyazawa. Introdução à Teoria dos Jogos
Algorítmica, ch. 8, pp. 365-417, XXIX Jornada deAtualização em Informática da SBC, 2010, pp.365-417. http://bit.ly/flavio-agt
• D. Easley e J. Kleinberg. Networks, Crowds, andMarkets. Cambridge University Press, 2010.http://bit.ly/networks-book
• D. Fudenberg e J. Tirole. Game Theory. MIT Press,1991.
• P. Cramton, Y. Shoham e R. Steinberg, editores.Combinatorial Auctions. MIT Press, 2006.
9
Bibliografia• F. K. Miyazawa. Introdução à Teoria dos Jogos
Algorítmica, ch. 8, pp. 365-417, XXIX Jornada deAtualização em Informática da SBC, 2010, pp.365-417. http://bit.ly/flavio-agt
• D. Easley e J. Kleinberg. Networks, Crowds, andMarkets. Cambridge University Press, 2010.http://bit.ly/networks-book
• D. Fudenberg e J. Tirole. Game Theory. MIT Press,1991.
• P. Cramton, Y. Shoham e R. Steinberg, editores.Combinatorial Auctions. MIT Press, 2006.
9
Conteúdo
• 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)
10
Conteúdo
• Introdução a jogos e conceitos básicos de soluções
• Complexidade computacional de encontrarequilí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)
10
Conteúdo
• 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)
10
Conteúdo
• 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)
10
Conteúdo
• 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)
10
Conteúdo
• 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)
10
Conteúdo
• 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)
10
Conteúdo
• 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)
10
Conteúdo
• 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 daanarquia)
10
Conteúdo
• 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)
10