@inproceedings{4169e5c4ff5741d9bf9292fa23d3811f,
title = "Antirandomizing the wrong game",
abstract = "We study a variant of the tenure game introduced by J. Spencer (Theor. Comput. Sci. 131 (1994), 415-429). In this version, chips are not removed from the game, but moved down to the lowest level instead. Though the rules of both versions differ only slightly, it seems impossible to convert an upper bound strategy into a lower bound one using the antirandomization approach of Spencer (which was very effective for the original game and several others). For the upper bound we give a potential function argument (both randomized and derandomized). We manage to prove a nearly matching lower bound using a strategy that can be interpreted as an antirandomization of Spencer's original game.",
keywords = "Derandomization, Games, Randomization",
author = "Benjamin Doerr",
year = "2002",
month = jan,
day = "1",
doi = "10.1007/3-540-45465-9\_75",
language = "English",
isbn = "3540438645",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "876--887",
editor = "Peter Widmayer and Stephan Eidenbenz and Francisco Triguero and Rafael Morales and Ricardo Conejo and Matthew Hennessy",
booktitle = "Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings",
note = "29th International Colloquium on Automata, Languages, and Programming, ICALP 2002 ; Conference date: 08-07-2002 Through 13-07-2002",
}