# Solving an online problem without maximizing or minimizing an objective

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

• "indivisible product... divided into $n$ parts"?! – Aryeh Oct 29 '19 at 12:05
• @Aryeh you can see it as $n$ products. – zdm Oct 29 '19 at 14:35
• @zdm A very, very rough similar-ish problem is the secretary problem. – orlp Oct 30 '19 at 0:01
• 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 Oct 30 '19 at 17:15
• 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 Oct 30 '19 at 17:31

@orlp'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$$.

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