Convergence time to the Nash equilibrium in packing and load balancing games / Tempo de convergencia para o equilibrio de Nash nos jogos empacotamento de itens e balanceamento de carga

AUTOR(ES)
DATA DE PUBLICAÇÃO

2010

RESUMO

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

ASSUNTO(S)

problema de balanceamento de carga games theory teoria dos jogos packing problem problema de empacotamento load balancing problem

ACESSO AO ARTIGO

Documentos Relacionados