Yiannis, Giannakopoulos and Koutsoupias, Elias and Kyropoulou, Maria (2019) The Anarchy of Scheduling Without Money. Theoretical Computer Science, 778. pp. 19-32. DOI https://doi.org/10.1016/j.tcs.2019.01.022
Yiannis, Giannakopoulos and Koutsoupias, Elias and Kyropoulou, Maria (2019) The Anarchy of Scheduling Without Money. Theoretical Computer Science, 778. pp. 19-32. DOI https://doi.org/10.1016/j.tcs.2019.01.022
Yiannis, Giannakopoulos and Koutsoupias, Elias and Kyropoulou, Maria (2019) The Anarchy of Scheduling Without Money. Theoretical Computer Science, 778. pp. 19-32. DOI https://doi.org/10.1016/j.tcs.2019.01.022
Abstract
We consider the scheduling problem on n strategic unrelated machines when no payments are allowed, under the objective of minimizing the makespan. We adopt the model introduced in [Koutsoupias 2014] where a machine is bound by her declarations in the sense that if she is assigned a particular job then she will have to execute it for an amount of time at least equal to the one she reported, even if her private, true processing capabilities are actually faster. We provide a (non-truthful) randomized algorithm whose pure Price of Anarchy is arbitrarily close to 1 for the case of a single task and close to n if it is applied independently to schedule many tasks, which is asymptotically optimal for the natural class of anonymous, task-independent algorithms. Previous work considers the constraint of truthfulness and proves a tight approximation ratio of (n+1)/2 for one task which generalizes to n(n+1)/2 for many tasks. Furthermore, we revisit the truthfulness case and reduce the latter approximation ratio for many tasks down to n, asymptotically matching the best known lower bound. This is done via a detour to the relaxed, fractional version of the problem, for which we are also able to provide an optimal approximation ratio of 1. Finally, we mention that all our algorithms achieve optimal ratios of 1 for the social welfare objective.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | mechanism design without payments; price of anarchy; scheduling unrelated machines; approximation algorithms |
Subjects: | H Social Sciences > HG Finance Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 06 Feb 2019 12:12 |
Last Modified: | 30 Oct 2024 16:28 |
URI: | http://repository.essex.ac.uk/id/eprint/23852 |
Available files
Filename: The Anarchy of Scheduling Without Money-jv.pdf
Licence: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0