# Can a non-competitive deterministic algorithm be k-competitive if randomized?

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

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