Tema: Teoria dos jogos algorítmica e otimização combinatória
Orientadora: Cristina Gomes Fernandes
Aluno: Atol Fortin de Oliveira

Resumo da monografia desenvolvida

Nos últimos anos, notou-se que vários problemas de otimização combinatória podem ser olhados sob o ponto de vista de teoria dos jogos, e isso tem trazido resultados interessantes para tais problemas, pois permite que técnicas e observações da área de teoria dos jogos sejam usadas ou sirvam de inspiração. Ao mesmo tempo, o crescimento da internet trouxe consigo uma variedade de problemas novos, muitos deles envolvendo aspectos de teoria dos jogos. Neste projeto, pretendemos estudar problemas de otimização combinatória sob o enfoque de teoria dos jogos, e resultados nesta linha.

A principal fonte de estudo que foi usada é o livro Algorithmic Game Theory [1] .

Objetivos do trabalho

Dentro desta rica área de problemas que envolvem teoria dos jogos, estamos particularmente interessados em problemas de otimização combinatória. Resultados recentes mostram que várias técnicas de otimização combinatória têm sido bem sucedidas na resolução de problemas nesta linha. Os resultados obtidos incluem tanto algoritmos eficientes para alguns destes problemas quanto bons algoritmos de aproximação para problemas difíceis nestas classes. A determinação da complexidade computacional de vários destes problemas encontra-se ainda em aberto, sendo um tópico de grande interesse.

Inicialmente revisitamos alguns problemas clássicos de otimização combinatória, sob um ponto de vista de teoria dos jogos. Em uma segunda fase, estudamos problemas de teoria dos jogos que possam ser modelados como problemas de otimização combinatória e para os quais existam bons resultados desta área. O objetivo desta monografia é apresentar os resultados estudados em um texto didático que ajude uma pessoa interessada em começar a estudar tópicos desta área.

Estrutura da monografia

A monografia é composta por uma parte técnica e uma parte subjetiva. A monografia aborda os seguintes itens:

• Introdução: apresenta o assunto abordado, os motivos e os objetivos da monografia.
• Resultados obtidos: parte central da monografia, onde são expostos os assuntos estudados.
• Conclusões.
• Referências bibliográficas.
• Dificuldades encontradas durante o desenvolvimento da monografia.
• Disciplinas cursadas que ajudaram na realização da monografia e seus motivos.

Referências

[1] N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, 2007.