<p>The problem is equivalent to online knapsack problem. Let <span class="math-container">$n$</span> represents the number of items. Let the knapsack has capacity <span class="math-container">$B$</span>. Every item <span class="math-container">$i$</span>, has value <span class="math-container">$v_i=1$</span> and weight <span class="math-container">$w_i=p_i$</span>.</p>

<p><strong>The offline optimal solution:</strong> </p>

<ul>
<li>Sort the items in increasing order of their weights (<span class="math-container">$p_{\sigma(1)}\leq p_{\sigma(2)}\leq \cdots \leq p_{\sigma(n)}$</span> for some permutation <span class="math-container">$\sigma$</span>).</li>
<li>Let <span class="math-container">$S\gets\emptyset$</span>.</li>
<li>For <span class="math-container">$i\gets1$</span> to <span class="math-container">$n$</span>: add <span class="math-container">$\sigma(i)$</span> to <span class="math-container">$S$</span> unless <span class="math-container">$\sum_{i\in S}p_i&gt;B$</span>.</li>
<li>For each <span class="math-container">$i\in S$</span>, bid <span class="math-container">$b_i=p_i$</span> and for each <span class="math-container">$i\notin S$</span>, bid <span class="math-container">$b_i=0$</span>.</li>
</ul>

<p><strong>Claim:</strong> No online algorithm can achieve any non-trivial competitive ratio <a href="https://link.springer.com/article/10.1007/BF01585758" rel="nofollow noreferrer">[1]</a>.</p>

<p>If we assume that <span class="math-container">$p_i=o(B)$</span> and <span class="math-container">$L\leq p_i\leq U$</span>, then there is a competitive ratio of <span class="math-container">$\ln(U/L)+1$</span> <a href="https://www.cs.dartmouth.edu/~deepc/PUBS/CZL-full.pdf" rel="nofollow noreferrer">[2]</a>.</p>

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

CC BY-SA 4.0
2020-09-01T15:37:25.807Z
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.
Neal Young
CC BY-SA 4.0
2019-12-04T16:45:41.717Z
2019-12-04T16:45:41.717Z
zdm
<p>You are playing the following game.</p>

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

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

<p>My policy so far is:</p>

<ul>
<li>For each day <span class="math-container">$d=1..n$</span>, bid <span class="math-container">$b_d=B_r/(n-d+1)$</span>, where <span class="math-container">$B_r$</span> is your remaining budget.</li>
</ul>

<p>I was trying to find an input sequence that makes my policy perform badly but I didn't succeed (for large <span class="math-container">$n$</span>). I think if <span class="math-container">$n$</span> is large, then we may reach a low regret with this policy. I am still trying to prove this.</p>

CC BY-SA 4.0
2019-11-30T00:18:42.603Z
What's the relation to your other post https://cstheory.stackexchange.com/questions/45934/learning-with-unknown-probabilities ?  You've made a sequence of several related, slightly ill-defined posts. Would it be better to resolve some of them before posting more?
Neal Young
CC BY-SA 4.0
2019-11-30T00:25:48.020Z
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.
zdm
CC BY-SA 4.0
2019-11-30T01:40:29.720Z
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.
Neal Young
CC BY-SA 4.0
2019-11-30T01:57:58.700Z
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$.
zdm
CC BY-SA 4.0
2019-11-30T02:04:16.830Z
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\}$).
Neal Young
CC BY-SA 4.0
2019-11-30T05:47:53.807Z
I think that in general one can prove a lower bound on the regret of $\min(B, n-2B)$ if both players play optimally.  E.g. if you start with $B=n/3$, the adversary can force any deterministic online algorithm to have regret of at least $n/3$.  It's probably higher, but I think I can prove at least that.  Also, FWIW, here is some Python code to explore it: https://repl.it/repls/InsubstantialCheeryUserinterface.
Neal Young
CC BY-SA 4.0
2019-11-30T12:39:40.320Z
what do you mean by "what adversary buys"? It seems like in this framework, it's better to compare your method to "offline optimal", don't you think?
AmeerJ
CC BY-SA 4.0
2019-11-30T14:22:31.467Z
@AmeerJ It's the same.  We assume the adversary's buys are optimal.  (Or for a lower bound on the regret or competitive ratio, we oftern describe one way for the adversary to buy and use it as a lower bound on OPT.)
Neal Young
CC BY-SA 4.0
2019-11-30T16:55:18.023Z
@NealYoung thanks for the code. If we assume that the prices are given in some random order or follow some distribution, can we improve the regret? I think it is similar to the problem of online procurement problem.
zdm
<reference-request><online-algorithms><online-learning><adversarial-learning>
A Simple Auction Game
zdm
# A Simple Auction Game

(Asked by: username_0 on 2019-11-30)

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

**Tags:** reference-request, online-algorithms, online-learning, adversarial-learning
> **Comments:**
> **username_1**: What's the relation to your other post https://cstheory.stackexchange.com/questions/45934/learning-with-unknown-probabilities ?  You've made a sequence of several related, slightly ill-defined posts. Would it be better to resolve some of them before posting more?  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: 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$.  
> **username_1**: 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\}$).  
> **username_1**: I think that in general one can prove a lower bound on the regret of $\min(B, n-2B)$ if both players play optimally.  E.g. if you start with $B=n/3$, the adversary can force any deterministic online algorithm to have regret of at least $n/3$.  It's probably higher, but I think I can prove at least that.  Also, FWIW, here is some Python code to explore it: https://repl.it/repls/InsubstantialCheeryUserinterface.  
> **username_2**: what do you mean by "what adversary buys"? It seems like in this framework, it's better to compare your method to "offline optimal", don't you think?  
> **username_1**: @AmeerJ It's the same.  We assume the adversary's buys are optimal.  (Or for a lower bound on the regret or competitive ratio, we oftern describe one way for the adversary to buy and use it as a lower bound on OPT.)  
> **username_0**: @NealYoung thanks for the code. If we assume that the prices are given in some random order or follow some distribution, can we improve the regret? I think it is similar to the problem of online procurement problem.  

---

## 1 answers

### Answer by username_0 on 2019-12-04. Score: -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]](https://link.springer.com/article/10.1007/BF01585758).

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]](https://www.cs.dartmouth.edu/~deepc/PUBS/CZL-full.pdf).

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

> **Comments:**
> **username_1**: 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.  

---

