Abstract | In load balancing games, there is a set of available servers and
a set of clients; each client wishes to run her job on some server. Clients
are sel¯sh and each of them selects a server that, given an assignment
of the other clients to servers, minimizes the latency she experiences
with no regard to the global optimum. In order to mitigate the e®ect of
sel¯shness on the e±ciency, we assign taxes to the servers. In this way,
we obtain a new game where each client aims to minimize the sum of
the latency she experiences and the tax she pays. Our objective is to
¯nd taxes so that the worst equilibrium of the new game is as e±cient
as possible. We present new results concerning the impact of taxes on
the e±ciency of equilibria, with respect to the total latency of all clients
and the maximum latency (makespan). |