hide
Free keywords:
-
Abstract:
We consider a scheduling problem where each job is controlled by a
selfish agent, who is only interested in minimizing its own cost,
defined as the total load of the machine that its job is assigned
to. We consider the objective of maximizing the minimum load (the
value of the cover) over the machines. Unlike the regular makespan
minimization problem, which was extensively studied in a game
theoretic context, this problem has not been considered in this
setting before.
We study the price of anarchy (\poa) and the price of stability
(\pos). These measures are unbounded already for two uniformly
related machines \citeEpKS10, and therefore we focus on
identical machines. We show that the \pos is 1, and derive tight
bounds on the pure \poa for m≤q 7 and on the overall pure
\poa, showing that its value is exactly 1.7. To achieve the
upper bound of 1.7, we make an unusual use of weighting functions.
Finally, we show that the mixed \poa grows exponentially with
m for this problem.
In addition, we consider a similar setting of selfish jobs with a
different objective of minimizing the maximum ratio between the
loads of any pair of machines in the schedule. We show that under
this objective the \pos is 1 and the pure \poa is 2, for any
m≥q 2.
