When does a random Robin Hood win?

TitleWhen does a random Robin Hood win?
Publication TypeJournal Articles
Year of Publication2003
AuthorsGasarch W, Golub E, Srinivasan A
JournalTheoretical Computer Science
Volume304
Issue1–3
Pagination477 - 484
Date Published2003/07/28/
ISBN Number0304-3975
KeywordsGames, Randomized strategy, STRATEGY
Abstract

A certain two-person infinite game (between “Robin Hood” and the “Sheriff”) has been studied in the context of set theory. In certain cases, it is known that for any deterministic strategy of Robin Hood's, if the Sheriff knows Robin Hood's strategy, he can adapt a winning counter-strategy. We show that in these cases, Robin Hood wins with “probability one” if he adopts a natural random strategy. We then characterize when this random strategy has the almost-surely winning property. We also explore the case of a random Sheriff versus a deterministic Robin Hood.

URLhttp://www.sciencedirect.com/science/article/pii/S0304397503002895
DOI10.1016/S0304-3975(03)00289-5