Seminário de Teoria da Computação

                       Jogos de Roteamento

                      Eduardo Candido Xavier

               Sexta-feira, 05 de setembro de 2008

                       Sala 85  16:00hs

Neste seminário iremos apresentar resultados para jogos de roteamento.
O jogo é dado por um grafo com custos c_e para cada aresta. Tais
custos indicam o congestionamento na aresta. Jogadores devem
estabelecer rotas de comunicação de tal forma a minimizar os custos de
congestionamento de suas rotas. Veremos que tal jogo sempre admite um
equilíbrio de Nash e discutiremos o preço da anarquia de tal jogo.

Referência Cap. 18 do livro Algorithmic Game Theory, Noam Nisan,
Tim Roughgarden, Eva Tardos, Vijay V. Vazirani.