Convergence to Nash equilibria in distributed and selfish reallocation processes

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2007
Authors/Contributors
Abstract
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.
Document
Copyright statement
Copyright is held by the author.
Permissions
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 summit-permissions@sfu.ca.
Scholarly level
Language
English
Member of collection
Attachment Size
etd3297.pdf 739.29 KB