×

Strong price of anarchy for machine load balancing. (English) Zbl 1171.68390

Arge, Lars (ed.) et al., Automata, languages and programming. 34th international colloquium, ICALP 2007, Wrocław, Poland, July 9–13, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73419-2/pbk). Lecture Notes in Computer Science 4596, 583-594 (2007).
Summary: As defined by R. J. Aumann [Ann. Math. Stud. 40, 287–324 (1959; Zbl 0085.13005)] in 1959, a strong equilibrium is a Nash equilibrium that is resilient to deviations by coalitions. We give tight bounds on the strong price of anarchy for load balancing on related machines. We also give tight bounds for \(k\)-strong equilibria, where the size of a deviating coalition is at most \(k\).
For the entire collection see [Zbl 1119.68002].

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research
91A10 Noncooperative games

Citations:

Zbl 0085.13005
PDFBibTeX XMLCite
Full Text: DOI Link