### Skapa referens, olika format (klipp och klistra)

**Harvard**

Abed, F., Correa, J. och Huang, C. (2014) *Optimal coordination mechanisms for multi-job scheduling games*.

** BibTeX **

@conference{

Abed2014,

author={Abed, F. and Correa, J.R. and Huang, Chien-Chung},

title={Optimal coordination mechanisms for multi-job scheduling games},

booktitle={Lecture Notes in Computer Science - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings.},

isbn={9783662447765},

pages={13-24},

abstract={We consider the unrelated machine scheduling game in which players control subsets of jobs. Each player's objective is to minimize the weighted sum of completion time of her jobs, while the social cost is the sum of players' costs. The goal is to design simple processing policies in the machines with small coordination ratio, i.e., the implied equilibria are within a small factor of the optimal schedule. We work with a weaker equilibrium concept that includes that of Nash. We first prove that if machines order jobs according to their processing time to weight ratio, a.k.a. Smith-rule, then the coordination ratio is at most 4, moreover this is best possible among nonpreemptive policies. Then we establish our main result. We design a preemptive policy, externality, that extends Smith-rule by adding extra delays on the jobs accounting for the negative externality they impose on other players. For this policy we prove that the coordination ratio is 1+φ≈2.618, and complement this result by proving that this ratio is best possible even if we allow for randomization or full information. Finally, we establish that this externality policy induces a potential game and that an ε-equilibrium can be found in polynomial time. An interesting consequence of our results is that an ε-local optima of R| |∑w j C j for the jump (a.k.a. move) neighborhood can be found in polynomial time and are within a factor of 2.618 of the optimal solution. The latter constitutes the first direct application of purely game-theoretic ideas to the analysis of a well studied local search heuristic.},

year={2014},

keywords={Heuristic algorithms, Polynomial approximation, Scheduling Coordination ratio, Full informations, Local search heuristics, Negative externalities, Non-preemptive policy, Optimal coordination, Optimal solutions, Unrelated machines},

}

** RefWorks **

RT Conference Proceedings

SR Electronic

ID 216497

A1 Abed, F.

A1 Correa, J.R.

A1 Huang, Chien-Chung

T1 Optimal coordination mechanisms for multi-job scheduling games

YR 2014

T2 Lecture Notes in Computer Science - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings.

SN 9783662447765

SP 13

OP 24

AB We consider the unrelated machine scheduling game in which players control subsets of jobs. Each player's objective is to minimize the weighted sum of completion time of her jobs, while the social cost is the sum of players' costs. The goal is to design simple processing policies in the machines with small coordination ratio, i.e., the implied equilibria are within a small factor of the optimal schedule. We work with a weaker equilibrium concept that includes that of Nash. We first prove that if machines order jobs according to their processing time to weight ratio, a.k.a. Smith-rule, then the coordination ratio is at most 4, moreover this is best possible among nonpreemptive policies. Then we establish our main result. We design a preemptive policy, externality, that extends Smith-rule by adding extra delays on the jobs accounting for the negative externality they impose on other players. For this policy we prove that the coordination ratio is 1+φ≈2.618, and complement this result by proving that this ratio is best possible even if we allow for randomization or full information. Finally, we establish that this externality policy induces a potential game and that an ε-equilibrium can be found in polynomial time. An interesting consequence of our results is that an ε-local optima of R| |∑w j C j for the jump (a.k.a. move) neighborhood can be found in polynomial time and are within a factor of 2.618 of the optimal solution. The latter constitutes the first direct application of purely game-theoretic ideas to the analysis of a well studied local search heuristic.

LA eng

DO 10.1007/978-3-662-44777-2_2

LK http://dx.doi.org/10.1007/978-3-662-44777-2_2

OL 30