6
$\begingroup$

Let's say there is a problem in which all possible deterministic online algorithms tha solve this problem are not-competitive.

Does this mean that a randomized online algorithm for the same problem will also be not-competitive, or is there a case that it can be k-competitive (k is a constant)?

$\endgroup$
10
$\begingroup$

Imagine having to predict 0 or 1 on every round, and we are counting the number of correct predictions. Every deterministic strategy has an adversarial sequence that makes it always predict incorrectly. Hence, no competitive ratio is possible.

However, the randomized strategy of flipping a coin on every round will be $2$-competitive with the best constant prediction (in expectation).

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.1288 studies one such problem.

The problem being studied is multi-unit auctions with unknown supply. The setting is a non-strategic setting (i.e each bidder reports truthfully irrespective of the outcome). Each bidder wants a single item among items which arrive online. When an item arrives it must be allocated immediately, else it perishes. At the end of the algorithm designer is allowed to charge a uniform price to each allocated bidder(which is atmost the bidders bid). The paper shows that there is no deterministic algorithm which is constant competitive, while they show a $1/4$ competitive randomized algorithm.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.