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
Pagination477 - 484
Date Published2003/07/28/
ISBN Number0304-3975
KeywordsGames, Randomized strategy, STRATEGY

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.