<p>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.</p>

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

CC BY-SA 3.0
2012-04-04T00:30:16.643Z
2012-04-04T00:30:16.643Z
Lev Reyzin
<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.1288" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.1288</a> studies one such problem.</p>

<p>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.</p>

CC BY-SA 3.0
2012-04-04T01:03:29.907Z
2012-04-04T01:03:29.907Z
Ashwinkumar B V
<p>Let's say there is a problem in which all possible deterministic online algorithms tha solve this problem are not-competitive. </p>

<p>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)?</p>

<ds.algorithms><gt.game-theory><online-algorithms>
Can a non-competitive deterministic algorithm be k-competitive if randomized?
Goro Manpir
# Can a non-competitive deterministic algorithm be k-competitive if randomized?

(Asked by: username_0 on 2012-04-03)

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)?

**Tags:** ds.algorithms, gt.game-theory, online-algorithms


---

## 2 answers

### Answer by username_1 on 2012-04-04. Score: 10

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).


---

### Answer by username_2 on 2012-04-04. Score: 2

<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.


---

