TCS Journal 2003 Journal Article
When does a random Robin Hood win?
- William Gasarch
- Evan Golub
- Aravind Srinivasan
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.