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.
Copyright is held by the author.
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact firstname.lastname@example.org.
Member of collection