MC918/MO829 Tópicos em Teoria da Computação Teoria dos...

MC918/MO829Tópicos em Teoria da Computação

Teoria dos Jogos Algorítmica

Rafael C. S. Schoueryschouery@ic.unicamp.br

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 schouery@ic.unicamp.br avisando aparticipação pelo menos 24 horas antes!

6

Atendimento

• Quartas-feiras, 16h• Sala do Prof. Flávio Keidi Miyazawa

Enviar email para schouery@ic.unicamp.br avisando aparticipação pelo menos 24 horas antes!

6

Atendimento

• Quartas-feiras, 16h• Sala do Prof. Flávio Keidi Miyazawa

Enviar email para schouery@ic.unicamp.br 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