A Simple Auction Game

Question

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.

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