Equilibria for two parallel links: The strong price of anarchy versus the price of anarchy

Abstract

Following recent interest in the "strong price of anarchy" SPOA),
we consider this measure, as well as the well known "price of
anarchy" (POA) for the job scheduling problem on two uniformly
related parallel machines (or links). The atomic players are the
jobs, and the delay of a job is the completion time of the
machine running it. The social goal is to minimize the maximum
delay of any job. Thus the cost (or social cost) in this case is
the makespan of the schedule. The selfish goal of each job is to
minimize its delay, i.e., the delay of the machine that it
chooses to run on.

A pure Nash equilibrium is a schedule where no job can obtain a
smaller delay by selfishly moving to a different configuration
(machine), while other jobs remain in their original positions. A
strong equilibrium is a schedule where no (non-empty) subset of
jobs exists, where all jobs in this subset can benefit from
changing their configuration. We say that all jobs in a subset
benefit from moving to a different machine if all of them have a
strictly smaller delay as a result of moving (while the other
jobs remain in their positions, and may possibly have a larger
delay as a result).

 The SPOA is the worst case ratio between the social cost of a (pure)
strong equilibrium and the cost of an optimal assignment, that
is, the minimum achievable social cost. The POA is a standard
measure which takes into account not only strong equilibria but
any (pure) equilibrium. These two measures consolidate and give
the same results for some problems, whereas for other problems,
the SPOA gives much more meaningful results than the POA.

We study the behavior of the SPOA versus the behavior of the POA
for this scheduling problem and give tight results for both these
measures. We find the exact SPOA for any possible speed ratio
 s geq 1 of the machines, and compare it to the exact POA which
we also find. We show that for a wide range of speeds ratios
these two measures are very different (1.618<s<2.247), whereas
for other values of $s$, these two measures give the exact same
bound. We extend all our results for cases where a machine may
have an initial load resulting from jobs that can only be
assigned to this machine, and show tight bounds on the SPOA and
the POA for three such variants as well.