Tempo de convergencia para o equilíbrio de Nash nos jogos empacotamento de itens e balanceamento de carga
Andre Luis Vignatti
TESE
Português
T/UNICAMP V683t
[Convergence time to the Nash equilibrium in packing and load balancing games]
Campinas, SP : [s.n.], 2010.
85 f. : il.
Orientador: Flavio Keidi Miyazawa
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação
Resumo: Nesta tese, estudamos versões de teoria dos jogos dos problemas de empacotamento de itens e balanceamento de carga. Consideramos que a implementação de um algoritmo centralizado de controle é inviável, fazendo com que as entidades participantes do sistema ajam de maneira egoísta. Assim, a...
Ver mais
Resumo: Nesta tese, estudamos versões de teoria dos jogos dos problemas de empacotamento de itens e balanceamento de carga. Consideramos que a implementação de um algoritmo centralizado de controle é inviável, fazendo com que as entidades participantes do sistema ajam de maneira egoísta. Assim, a escolha egoísta de estratégias pelas entidades pode ou não levar a um estado estável do sistema, chamado de equilíbrio de Nash. Dependendo das condições definidas pelo modelo utilizado, devemos embutir certas regras para as entidades, contanto que as entidades tenham incentivo de utilizá-las e que, além disso, façam com que o sistema alcance um equilíbrio de Nash. Os principais resultados desta tese são relativos ao tempo de convergência para o equilíbrio de Nash, ou seja, buscamos saber quantas vezes os agentes mudam suas estratégias até alcançarem o equilíbrio de Nash, seja agindo de maneira completamente egoísta ou seguindo certas regras. Para o jogo de empacotamento de itens, apresentamos limitantes teóricos para o tempo de convergência, olhando ambos os casos de atualizações seqüenciais ou simultâneas das estratégias. Para o jogo de balanceamento de carga consideramos um modelo distribuído assíncrono com entidades heterogêneas, apresentando algumas regras que as entidades devem seguir e realizamos simulações para comparar as regras apresentadas
Ver menos
Abstract: In this thesis, we study game-theorical versions of the bin packing and load balancing problems. We consider that the implementation of a centralized controller algorithm is not feasible, making the entities that participate in the system act in a selfish way. Thus, the selfish choice of...
Ver mais
Abstract: In this thesis, we study game-theorical versions of the bin packing and load balancing problems. We consider that the implementation of a centralized controller algorithm is not feasible, making the entities that participate in the system act in a selfish way. Thus, the selfish choice of the strategies by the entities may or may not lead to a stable state of the system, called Nash equilibrium. Depending on the conditions defined by the considered model, we must build certain rules for entities, provided that the entities have incentive to use them and also make the system reach a Nash equilibrium. The main results of this thesis are related to the convergence time to Nash equilibrium, i.e., we seek to know how many times the agents change their strategies until they reach a Nash equilibrium, whether they act in a completely selfish way or follow certain rules. For the bin packing game, we present theoretical bounds for the convergence time, considering both the cases of sequential or simultaneous updates of the strategies. For the load balancing game, we consider an asynchronous distributed model with heterogeneous entities, presenting some rules that the entities must follow and we carry out simulations to compare the presented rules
Ver menos
Miyazawa, Flávio Keidi, 1970-
Orientador
Donadelli Junior, Jair
Avaliador
Meira, Luis Augusto Angelotti, 1979-
Avaliador
Dahab, Ricardo, 1957-
Avaliador
Mandel, Arnaldo
Avaliador
Tempo de convergencia para o equilíbrio de Nash nos jogos empacotamento de itens e balanceamento de carga
Andre Luis Vignatti
Tempo de convergencia para o equilíbrio de Nash nos jogos empacotamento de itens e balanceamento de carga
Andre Luis Vignatti
Exemplares
Nº de exemplares: 2
Não existem reservas para esta obra