Algorithmic Mechanism Design for Load Balancing

Computational Grids are large scale computing system composed of geographically distributed resources (comput-ers, storage etc.) owned by self interested agents or organi-zations. These agents may manipulate the resource alloca-tion algorithm in their own benefit and their selfish behav-ior may lead to severe performance degradation and poor efficiency. In this paper we investigate the problem of de-signing protocols for resource allocation involving selfish agents. Solving this kind of problems is the object of mech-anism design theory. Using this theory we design a truthful mechanism for solving the static load balancing problem in heterogeneous distributed systems. We prove that using the optimal allocation algorithm the output function admits a truthful payment scheme satisfying voluntary participation. We derive a protocol that implements our mechanism and present experiments to show its effectiveness. 1