Document Open Access Logo

The Power of One Secret Agent

Author Tami Tamir

PDF
Thumbnail PDF

File

LIPIcs.FUN.2018.32.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Tami Tamir
  • School of Computer Science, The Interdisciplinary Center (IDC), Herzliya, Israel

Cite As Get BibTex

Tami Tamir. The Power of One Secret Agent. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FUN.2018.32

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).

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
Keywords
  • Job scheduling games
  • Cost sharing
  • Equilibrium inefficiency

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4):1602-1623, 2008. Google Scholar
  2. G. Avni and T. Tamir. Cost-sharing scheduling games on restricted unrelated machines. Theoretical Computer Science, 646:26-39, 2016. Google Scholar
  3. V. Bilò and C. Vinci. On the impact of singleton strategies in congestion games. In Proc. 25th Annual European Symposium on Algorithms, pages 17:1-17:14, 2017. Google Scholar
  4. Ioannis Caragiannis, Michele Flammini, Christos Kaklamanis, Panagiotis Kanellopoulos, and Luca Moscardelli. Tight bounds for selfish and greedy load balancing. Algorithmica, 61(3):606-637, 2011. Google Scholar
  5. E.Even-Dar, A.Kesselman, and Y.Mansour. Convergence time to nash equilibria. In Proc. 30th Int. Colloq. on Automata, Languages, and Programming, pages 502-513, 2003. Google Scholar
  6. A. Fabrikant, C. Papadimitriou, and K. Talwar. The complexity of pure nash equilibria. In Proc. 36th ACM Symp. on Theory of Computing, pages 604-612, 2004. Google Scholar
  7. A. Fanelli, M. Flammini, and L. Moscardelli. Stackelberg strategies for network design games. In Proc. of the 3rd International Conference on Algorithmic Game Theory, pages 222-–233, 2010. Google Scholar
  8. M. Feldman, Y. Snappir, and T. Tamir. The efficiency of best-response dynamics. In Proc. of the 10th International Symposium on Algorithmic Game Theory (SAGT), 2017. Google Scholar
  9. D. Fisman, O. Kupferman, and Y. Lustig. Rational synthesis. In The 16th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pages 190-204, 2010. Google Scholar
  10. D. Fotakis. Stackelberg strategies for atomic congestion games. Theory of Computing Systems, 47(1):218-249, 2010. Google Scholar
  11. Vasilis Gkatzelis, Konstantinos Kollias, and Tim Roughgarden. Optimal cost-sharing in general resource selection games. Operations Research, 64(6):1230-1238, 2016. Google Scholar
  12. T. Harks and M. Klimm. On the existence of pure nash equilibria in weighted congestion games. Math. Oper. Res., 37(3):419-436, 2012. Google Scholar
  13. Samuel Ieong, Robert McGrew, Eugene Nudelman, Yoav Shoham, and Qixiang Sun. Fast and compact: A simple class of congestion games. In Proceedings of the 20th National Conference on Artificial Intelligence - Volume 2, AAAI'05, 2005. Google Scholar
  14. Yannis A. Korilis, Aurel A. Lazar, and Ariel Orda. Achieving network optima using stackelberg routing strategies. IEEE/ACM Trans. Netw., 5(1):161-173, 1997. Google Scholar
  15. E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. Computer Science Review, 3(2):65-69, 2009. Google Scholar
  16. Anna Lysyanskaya and Nikos Triandopoulos. Rationality and adversarial behavior in multi-party computation. In Advances in Cryptology - CRYPTO 2006, pages 180-197, 2006. Google Scholar
  17. I. Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, 13(1):111-124, 1996. Google Scholar
  18. Shien Jin Ong, David C. Parkes, Alon Rosen, and Salil Vadhan. Fairness with an honest minority and a rational majority. In Omer Reingold, editor, Theory of Cryptography, pages 36-53, 2009. Google Scholar
  19. C. H. Papadimitriou. Algorithms, games, and the internet. In Proc. 33rd ACM Symp. on Theory of Computing, pages 749-753, 2001. Google Scholar
  20. M. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, 2008. Google Scholar
  21. R. W. Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65-67, 1973. Google Scholar
  22. V. Syrgkanis. The complexity of equilibria in cost sharing games. In WINE, volume 6484, pages 366-377. Springer, 2010. Google Scholar
  23. Tami Tamir. Scheduling with bully selfish jobs. In Proceedings of the 5th International Conference on Fun with Algorithms, FUN'10, pages 355-367, 2010. Google Scholar
  24. B. Vöcking. Algorithmic Game Theory, chapter 20: Selfish Load Balancing. Cambridge University Press, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact