You are playing the following game.

  • You have a budget of $B$ dollars. There are $n$ days. Every day $d$, you have to make a bid $b_d\geq0$ that does not exceed your budget. After making the bid, a product appears with price $p_d\leq B$ dollars. If your bid is larger than the price, you buy the product, i.e., $b_d\geq p_d$, and you lose $b_d$ from your budget. Otherwise, you will be left with the same budget as before but you don't buy the product, i.e., if $b_d<p_d$. The next day the same thing happens and so forth. You stop the game when you spend all of your budget or day $n$ is reached. Your objective is to buy as much products as possible with budget $B$.

Can we find a policy that competes against an adversary and buy a "good" number of products? Good here means, for example, a policy with low regret, so the difference between what the adversary bought and what you bought is not large. If we can't, what assumptions could we make to make the regret low?

My policy so far is:

  • For each day $d=1..n$, bid $b_d=B_r/(n-d+1)$, where $B_r$ is your remaining budget.

I was trying to find an input sequence that makes my policy perform badly but I didn't succeed (for large $n$). I think if $n$ is large, then we may reach a low regret with this policy. I am still trying to prove this.

  • 6
    $\begingroup$ What's the relation to your other post cstheory.stackexchange.com/questions/45934/… ? You've made a sequence of several related, slightly ill-defined posts. Would it be better to resolve some of them before posting more? $\endgroup$
    – Neal Young
    Nov 30, 2019 at 0:18
  • $\begingroup$ I will probably remove my old post as this one is a special case. I am working to solve this special case with a competitive algorithm but I think it is not possible with further assumptions. So I said maybe trying to find a low regret policy is easier. $\endgroup$
    – zdm
    Nov 30, 2019 at 0:25
  • 1
    $\begingroup$ Re: your proposed policy (bid $b_d = B_d/(n-d+1)$, where $B_d$ is your remaining budget at day $d$). The adversary can set the price just out of reach for you every day, so you never buy. Then in each of the first $n/2$ days, the price is at most $2B/n$, so the adversary can buy on each of those days. You get nothing, while the adversary gets at least $n/2$ products. $\endgroup$
    – Neal Young
    Nov 30, 2019 at 1:40
  • $\begingroup$ In the last day, if I don't buy any product before, I will have a budget of $B$. So, I can buy (unless the price is larger than $B$). If the price is larger than $B$, than the adversary does not buy either in the last day. Do you mean that the adversary sets the prices larger than $B$ in the last $n/2$ days? I also assumed that the price on any day is less than $B$. $\endgroup$
    – zdm
    Nov 30, 2019 at 1:57
  • $\begingroup$ Price on day $d$ is, say, $B/(n-d+1)+\epsilon$ for some infinitesimal $\epsilon>0$. So yes, on day $d$, the price is just over $B$. If that's not allowed, set the price on day $d$ to $B$. Then you'll get 1 purchase, but adversary will still get at least $n/2$ (days $d\in\{1,2,\ldots, n/2\}$). $\endgroup$
    – Neal Young
    Nov 30, 2019 at 2:04

1 Answer 1


The problem is equivalent to online knapsack problem. Let $n$ represents the number of items. Let the knapsack has capacity $B$. Every item $i$, has value $v_i=1$ and weight $w_i=p_i$.

The offline optimal solution:

  • Sort the items in increasing order of their weights ($p_{\sigma(1)}\leq p_{\sigma(2)}\leq \cdots \leq p_{\sigma(n)}$ for some permutation $\sigma$).
  • Let $S\gets\emptyset$.
  • For $i\gets1$ to $n$: add $\sigma(i)$ to $S$ unless $\sum_{i\in S}p_i>B$.
  • For each $i\in S$, bid $b_i=p_i$ and for each $i\notin S$, bid $b_i=0$.

Claim: No online algorithm can achieve any non-trivial competitive ratio [1].

If we assume that $p_i=o(B)$ and $L\leq p_i\leq U$, then there is a competitive ratio of $\ln(U/L)+1$ [2].

For the regret, I don't know if there is some algorithm that achieves low regret (under some assumptions).

  • 1
    $\begingroup$ I don't agree that the problem is equvalent to online knapsack. To show that, you'd have to describe a reduction from your problem (in its full generality) to online knapsack, and a reduction from online knapsack (in full generality) to your problem. What you've described above doesn't seem to me to be either. $\endgroup$
    – Neal Young
    Sep 1, 2020 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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