Seminário de Teoria da Computação
       
            Balanceamento de Carga para Pessoas Egoístas

                      André Luis Vignatti

                 Sexta-feira, 26 de setembro de 2008

                         Sala 322  14:00hs <------ Obs.: Notem sala e horário


Resumo:
No problema de "balanceamento de carga", temos várias tarefas, cada
uma com um peso, e queremos distribuí-las em máquinas de forma que a
carga nas máquinas fique balanceada. Na abordagem mais usual,
assumimos que um algoritmo diz o que cada tarefa deve fazer para
conseguirmos uma boa solução final. O que aconteceria se as tarefas
são controladas por pessoas egoístas? Neste caso elas não vão obedecer
nenhuma regra, a não ser regras que beneficiam elas próprias. Neste
ambiente anárquico, uma solução é obtida quando todas as tarefas
estiverem satisfeitas com suas escolhas, gerando uma solução dita em
"equilíbrio de Nash". Quão pior seria essa solução "anárquica" em
relação a uma solução ótima? E quanto tempo levaria até que todas
tarefas estejam satisfeitas com suas escolhas? O objetivo deste
seminário é fornecer uma visão geral dos resultados já obtidos nesta
nova abordagem do problema.