Serving in the Dark should be done Non-Uniformly

摘要: We study the following balls and bins stochastic game between a player an adversary: there are B sequence of ball arrival extraction events. In event is stored in empty bin chosen by adversary discarded if no empty. event, algorithm selects bin, clears it, gains its content. interested analyzing gain which serves dark without any feedback at all, i.e., does not see sequence, content bins, even cleared (i.e. oblivious algorithm). compare that to optimal, open eyes, strategy gets same online sequence. name this ratio “loss serving dark”.