We study the problem of optimizing the performance of a system shared
by selfish, noncooperative users. We consider the concrete setting
of scheduling jobs on a set of shared machines possessing
load-dependent latency functions specifying the amount of time needed
to complete a job; we measure system performance by the {\em total
latency} of the system.
Assigning jobs according to the selfish interests of individual users
(who wish to minimize only the latency that their own jobs experience)
typically results in suboptimal system performance. However, in many
systems of this type there is a mixture of ``selfishly controlled''
and ``centrally controlled'' jobs; as the assignment of centrally
controlled jobs will influence the subsequent actions by selfish
users, we aspire to contain the degradation in system performance due
to selfish behavior by scheduling the centrally controlled jobs in the
best possible way.
We formulate this goal as an optimization problem via {\em Stackelberg
games}, games in which one player acts a {\em leader} (here, the
centralized authority interested in optimizing system performance) and
the rest as {\em followers} (the selfish users). The problem is then
to compute a strategy for the leader (a {\em Stackelberg strategy})
that induces the followers to react in a way that (at least
approximately) minimizes the total latency in the system.
In this paper, we prove that it is NP-hard to compute the optimal
Stackelberg strategy and present simple strategies with provable
performance guarantees. More precisely, we give a simple algorithm
that computes a strategy inducing a job assignment with total latency
no more than a constant times that of the optimal assignment of all of
the jobs; in the absence of centrally controlled jobs and a Stackelberg
strategy, no result of this type is possible. We also prove stronger
performance guarantees in the special case where every machine latency
function is linear in the machine load.