<p>@orlp's intuition is correct. </p>

<p><strong>lemma.</strong> <em>No online algorithm solves the problem in the worst case.</em></p>

<p><em>Proof.</em>  Consider the following instance:</p>

<p><span class="math-container">$$f(p) = (1+p_1)(1+p_2)(1+p_3) \ge 8 \text{ with } B=3.$$</span></p>

<p>This instance has just one solution (one <span class="math-container">$p$</span> that satisfies it), namely <span class="math-container">$p=(1,1,1)$</span>.  So, given <span class="math-container">$B=3$</span> and <span class="math-container">$L=8$</span> and just the first factor <span class="math-container">$1+p_1$</span>, the algorithm has to choose <span class="math-container">$p_1 = 1$</span>.</p>

<p>But then the adversary instead continues by defining the following instance:</p>

<p><span class="math-container">$$g(p) = (1+p_1)(1+ 1.49 p_2)(1+0\cdot p_3) \ge 8 \text{ with } B=3.$$</span></p>

<p>This instance is feasible (e.g. for <span class="math-container">$p_1=p_2=3/2$</span> we have <span class="math-container">$g(p)\approx 8.1$</span>). However, the algorithm committed to <span class="math-container">$p_1 = 1$</span>, so the residual problem it is faced with is now <span class="math-container">$2(1+1.49 p_2) \ge 8$</span> with <span class="math-container">$p_2 \le 2$</span>.  Since <span class="math-container">$2(1+1.49\cdot 2) &lt; 2\cdot 4 = 8$</span>, this residual problem is not feasible.  </p>

<p>So the online algorithm cannot guarantee a solution, even if it knows in advance that it will face just one of the two instances above. <span class="math-container">$~~~\Box$</span></p>

CC BY-SA 4.0
2019-11-03T00:03:55.763Z
2019-11-03T00:17:18.023Z
2019-11-03T00:17:18.023Z
Neal Young
<p>You have a budget <span class="math-container">$B$</span> and a satisfaction level <span class="math-container">$L$</span>. An indivisible product is available for sell and you are interested in buying. The product is divided into <span class="math-container">$n$</span> parts. Part <span class="math-container">$i$</span> of the product has positive value <span class="math-container">$v_i$</span>.</p>

<p>On day <span class="math-container">$i$</span>, you get to know <span class="math-container">$v_i$</span> and you have to decide how much price <span class="math-container">$p_i\geq0$</span> you would pay for this part of the product.</p>

<p>After <span class="math-container">$j$</span> days, given the values <span class="math-container">$v_1, v_2, \ldots, v_j$</span> and the prices you paid <span class="math-container">$p_1, p_2, \ldots, p_j$</span> for each value, you know that you can reach a satisfaction level of <span class="math-container">$(1+v_1p_1)(1+v_2p_2)\cdots(1+v_jp_j)$</span>.</p>

<p>Your objective is to buy the product after <span class="math-container">$n$</span> days while you reach the satisfaction level of <span class="math-container">$L$</span> and pay no more than <span class="math-container">$B$</span>.</p>

CC BY-SA 4.0
2019-10-29T12:05:39.400Z
"indivisible product... divided into $n$ parts"?!
Aryeh
CC BY-SA 4.0
2019-10-29T14:35:02.340Z
@Aryeh you can see it as $n$ products.
zdm
CC BY-SA 4.0
2019-10-29T18:22:45.917Z
This question is fundamentally unanswerable without assuming some distribution on $v_i$ (or at least properties of that distribution). Any strategy agnostic to such a distribution will have an adversary choice of $v_i$ that causes it to fail.
orlp
CC BY-SA 4.0
2019-10-29T22:10:50.480Z
@orlp Can you see any similarity between this problem and some known problem in the literature?
zdm
CC BY-SA 4.0
2019-10-30T00:01:40.617Z
@zdm A very, very rough similar-ish problem is the secretary problem.
orlp
CC BY-SA 4.0
2019-10-30T17:15:36.080Z
For n=2 there is a strategy.  Once you see v1, compute the minimum value of v2, say v2*, such that the problem (v1, v2*) is feasible.  Then choose p1 and p2 to be the values that work for (v1, v2*).  This suffices because the actual v2 will be at least v2*.  @orlp, can you prove your claim that any online strategy will fail on at least one input?  I'm not so sure.
Neal Young
CC BY-SA 4.0
2019-10-30T17:31:19.167Z
Note, also, for intuition, that for the modified the problem where we replace each $1+v_ip_i$ by $\exp(v_i p_i)$, there is an online strategy: set $p_i=0$ for all $i$ except the first where $v_i\ge \ln(L)/B$, and set that one to $B$.  (If there is no such $i$, then the instance is not feasible, because $$\prod_i \exp(v_ip_i) = \exp(\sum_i v_i p_i) < \exp(\ln(L)/B \sum_i p_i) \le \exp(\ln(L)/B \cdot B) = L.)$$
Neal Young
<online-algorithms>
Solving an online problem without maximizing or minimizing an objective
zdm
# Solving an online problem without maximizing or minimizing an objective

(Asked by: username_0 on 2019-10-25)

You have a budget $B$ and a satisfaction level $L$. An indivisible product is available for sell and you are interested in buying. The product is divided into $n$ parts. Part $i$ of the product has positive value $v\_i$.

On day $i$, you get to know $v\_i$ and you have to decide how much price $p\_i\geq0$ you would pay for this part of the product.

After $j$ days, given the values $v\_1, v\_2, \ldots, v\_j$ and the prices you paid $p\_1, p\_2, \ldots, p\_j$ for each value, you know that you can reach a satisfaction level of $(1+v\_1p\_1)(1+v\_2p\_2)\cdots(1+v\_jp\_j)$.

Your objective is to buy the product after $n$ days while you reach the satisfaction level of $L$ and pay no more than $B$.

**Tags:** online-algorithms

> **Comments:**
> **username_1**: "indivisible product... divided into $n$ parts"?!  
> **username_0**: @username_1 you can see it as $n$ products.  
> **username_2**: This question is fundamentally unanswerable without assuming some distribution on $v_i$ (or at least properties of that distribution). Any strategy agnostic to such a distribution will have an adversary choice of $v_i$ that causes it to fail.  
> **username_0**: @username_2 Can you see any similarity between this problem and some known problem in the literature?  
> **username_2**: @username_0 A very, very rough similar-ish problem is the secretary problem.  
> **username_3**: For n=2 there is a strategy.  Once you see v1, compute the minimum value of v2, say v2*, such that the problem (v1, v2*) is feasible.  Then choose p1 and p2 to be the values that work for (v1, v2*).  This suffices because the actual v2 will be at least v2*.  @username_2, can you prove your claim that any online strategy will fail on at least one input?  I'm not so sure.  
> **username_3**: Note, also, for intuition, that for the modified the problem where we replace each $1+v_ip_i$ by $\exp(v_i p_i)$, there is an online strategy: set $p_i=0$ for all $i$ except the first where $v_i\ge \ln(L)/B$, and set that one to $B$.  (If there is no such $i$, then the instance is not feasible, because $$\prod_i \exp(v_ip_i) = \exp(\sum_i v_i p_i) < \exp(\ln(L)/B \sum_i p_i) \le \exp(\ln(L)/B \cdot B) = L.)$$  

---

## 1 answers

### Answer by username_3 on 2019-11-03. Score: 2 | Accepted answer

@username_2's intuition is correct.

**lemma.** *No online algorithm solves the problem in the worst case.*

*Proof.* Consider the following instance:

$$f(p) = (1+p\_1)(1+p\_2)(1+p\_3) \ge 8 \text{ with } B=3.$$

This instance has just one solution (one $p$ that satisfies it), namely $p=(1,1,1)$. So, given $B=3$ and $L=8$ and just the first factor $1+p\_1$, the algorithm has to choose $p\_1 = 1$.

But then the adversary instead continues by defining the following instance:

$$g(p) = (1+p\_1)(1+ 1.49 p\_2)(1+0\cdot p\_3) \ge 8 \text{ with } B=3.$$

This instance is feasible (e.g. for $p\_1=p\_2=3/2$ we have $g(p)\approx 8.1$). However, the algorithm committed to $p\_1 = 1$, so the residual problem it is faced with is now $2(1+1.49 p\_2) \ge 8$ with $p\_2 \le 2$. Since $2(1+1.49\cdot 2) < 2\cdot 4 = 8$, this residual problem is not feasible.

So the online algorithm cannot guarantee a solution, even if it knows in advance that it will face just one of the two instances above. $~~~\Box$


---

