2026-07-21T12:33:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23454 2025-10-02T12:55:35Z ddc:004 open_access

Minimizing Recourse in an Adaptive Balls and Bins Game Fine, Adi Kaplan, Haim Stemmer, Uri Adaptive adversary load-balancing game balls-and-bins randomized algorithms dynamic 3-spanner dynamic graph algorithms adversarial robustness We consider a simple load-balancing game between an algorithm and an adaptive adversary. In a simplified version of this game, the adversary observes the assignment of jobs to machines and selects a machine to kill. The algorithm must then restart the jobs from the failed machine on other machines. The adversary repeats this process, observing the new assignment and eliminating another machine, and so on. The adversary aims to force the algorithm to perform many restarts, while we seek a robust algorithm that minimizes restarts regardless of the adversary’s strategy. This game was recently introduced by Bhattacharya et al. for designing a 3-spanner with low recourse against an adaptive adversary. We prove that a simple algorithm, which assigns each job to a randomly chosen live bin, incurs O(n log n) recourse against an adaptive adversary. This enables us to construct a much simpler 3-spanner with a recourse that is smaller by a factor of O(log² n) compared to the previous construction, without increasing the update time or the size of the spanner. This motivates a careful examination of the range of attacks an adaptive adversary can deploy against simple algorithms before resorting to more complex ones. As our case study demonstrates, this attack space may not be as large as it initially appears, enabling the development of robust algorithms that are both simpler and easier to analyze. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adi Fine and Haim Kaplan and Uri Stemmer 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.77 urn:nbn:de:0030-drops-234544 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.77 eng https://creativecommons.org/licenses/by/4.0/legalcode