License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2018.32
URN: urn:nbn:de:0030-drops-88237
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8823/
Tamir, Tami
The Power of One Secret Agent
Abstract
I am a job. In job-scheduling applications, my friends and I are assigned to machines that can process us. In the last decade, thanks to our strong employee committee, and the rise of algorithmic game theory, we are getting more and more freedom regarding our assignment. Each of us acts to minimize his own cost, rather than to optimize a global objective.
My goal is different. I am a secret agent operated by the system. I do my best to lead my fellow jobs to an outcome with a high social cost. My naive friends keep doing the best they can, each of them performs his best-response move whenever he gets the opportunity to do so. Luckily, I am a charismatic guy. I can determine the order according to which the naive jobs perform their best-response moves. In this paper, I analyze my power, formalized as the Price of a Traitor (PoT), in cost-sharing scheduling games - in which we need to cover the cost of the machines that process us.
Starting from an initial Nash Equilibrium (NE) profile, I join the instance and hurt its stability. A sequence of best-response moves is performed until I vanish, leaving the naive jobs in a new NE. For an initial NE assignment, S_0, the PoT measures the ratio between the social cost of a worst NE I can lead the jobs to, starting from S_0, and the social cost of S_0. The PoT of a game is the maximal such ratio among all game instances and initial NE assignments.
My analysis distinguishes between instances with unit- and arbitrary-cost machines, and instances with unit- and arbitrary-length jobs. I give exact bounds on the PoT for each setting, in general and in symmetric games. While it turns out that in most settings my power is really impressive, my task is computationally hard (and also hard to approximate).
BibTeX - Entry
@InProceedings{tamir:LIPIcs:2018:8823,
author = {Tami Tamir},
title = {{The Power of One Secret Agent}},
booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)},
pages = {32:1--32:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-067-5},
ISSN = {1868-8969},
year = {2018},
volume = {100},
editor = {Hiro Ito and Stefano Leonardi and Linda Pagli and Giuseppe Prencipe},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8823},
URN = {urn:nbn:de:0030-drops-88237},
doi = {10.4230/LIPIcs.FUN.2018.32},
annote = {Keywords: Job scheduling games, Cost sharing, Equilibrium inefficiency}
}
|
Keywords: |
|
Job scheduling games, Cost sharing, Equilibrium inefficiency |
|
Collection: |
|
9th International Conference on Fun with Algorithms (FUN 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.06.2018 |
