I recently started learning about randomized online algorithms, and the Wikipedia definitions for the three adversary models are very unhelpful to put it mildly. From poking around I think I have a good understanding of what an oblivious adversary is. From my understanding, the oblivious adversary must determine the "worst possible input sequence" before we even start running our algorithm. Let $I_w$ denote the worst possible input sequence this adversary comes up with. (I.e., the input sequence that produces the greatest gap between the best that can be done and what we expect our algorithm to do.)

We then say that our algorithm is $c$-competitive (for a minimization problem) under this adversary if $$E[Alg(I_w)] \le c \cdot Opt(I_w) + b$$ where $c,b$ are some constants, $E[Alg(I_w)]$ is the expected value of our algorithm on the input, and $Opt(I_w)$ is the cost if we had made perfect decisions. (I.e., if the problem went offline.)

My confusion concerns the adaptive online and adaptive offline adversaries. I neither fully understand their definitions nor the difference between them. I will list my confusions directly below.

  • As I understand it, both of these adversaries somehow build the input sequences as your online algorithm runs. This says before you create the input at time $t$, unlike in the case of the oblivious adversary, both the adaptive online and adaptive offline adversaries have access to the outcomes of your algorithm at time steps $1, \ldots , t-1$. Then it says that in both cases the adversary "incurs the costs of serving the requests online." The difference being that for the online adaptive adversary, it "will only receive the decision of the online algorithm after it decided its own response to the request." Does this mean that the difference is that the offline adaptive adversary can see how your algorithm performs during future steps? Or just the present step? But then why is it still incurring the cost of serving requests online?
  • This source contradicts the source above. It says that the adaptive offline adversary "is charged the optimum offline cost for that sequence." Like I said previously, the previously source says both incur "the cost of serving the requests online." What does it even mean to incur the cost of serving requests online vs. offline? Which is correct?
  • This takes a completely different tack and talks about knowing randomness (online adaptive) vs. knowing "random bits" (offline adaptive). Is this equivalent somehow? How so?
  • How does the definition of the competitive ratio change for these two adversaries? Most sources I looked at just defined the competitive ratio for the oblivious adversary.

A simple example of each to illustrate the difference would be much appreciated. Thanks for the help!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.