We introduce several congestion games and study the speed of convergence to Nash Equilibria under reasonable reallocation protocols. We focus on a particular atomic congestion game, distributed selfish load balancing, in which a set of resources are to be allocated to tasks with selfish agents willing to minimize their own latency. We revisit and improve the previous results for the uniform case where tasks share identical resources, and the latency function of a resource is the number of tasks utilizing it. Moreover we introduce two variations of this setting. In the first variation we consider the case where tasks have different weights and the latency of each resource is the total weights of the tasks utilizing it. Another variation is the case where tasks are identical, but resources have arbitrary latency functions. We give upper bounds for the convergence time of these models, and some examples to justify our protocols.
展开▼
