1. Scheduling selfish jobs on multidimensional parallel machines
- Author
-
Leah Epstein and Elena Kleiman
- Subjects
TheoryofComputation_MISCELLANEOUS ,Computer Science::Computer Science and Game Theory ,Mathematical optimization ,General Computer Science ,Job shop scheduling ,TheoryofComputation_GENERAL ,0102 computer and information sciences ,02 engineering and technology ,Load balancing (computing) ,01 natural sciences ,Theoretical Computer Science ,Scheduling (computing) ,Pareto optimal ,symbols.namesake ,010201 computation theory & mathematics ,Nash equilibrium ,Norm (mathematics) ,0202 electrical engineering, electronic engineering, information engineering ,Price of anarchy ,symbols ,020201 artificial intelligence & image processing ,Price of stability ,Mathematical economics ,Mathematics - Abstract
We study the multidimensional vector scheduling problem with selfish jobs, both in non-cooperative and in cooperative versions, in two variants. These variants differ in the private costs of the jobs: in the first variant, the cost is the l ∞ norm (maximum over components) while in the second variant it is the l 1 norm (sum of components) of the load. We show existence of assignments that are Nash, strong Nash, weakly and strictly Pareto optimal Nash equilibria in these settings. For the first variant, we improve upon the previous bounds on the price of anarchy for the non-cooperative case, and find tight bounds for every number of machines and dimension. For the cooperative case we provide tight bounds on the strong prices of anarchy and stability, as well as tight bounds on weakly and strictly Pareto optimal prices of anarchy and stability, for every number of machines and dimension. For the second variant, which was not considered before, we again consider all the aforementioned measures, and find tight bounds, each of which being a function of the number of machines and the dimension, showing cardinal differences in the behavior of these measures both between the two variants, and in comparison to the one-dimensional case.
- Published
- 2014