2
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ "indivisible product... divided into $n$ parts"?! $\endgroup$
    – Aryeh
    Commented Oct 29, 2019 at 12:05
  • $\begingroup$ @Aryeh you can see it as $n$ products. $\endgroup$
    – zdm
    Commented Oct 29, 2019 at 14:35
  • 1
    $\begingroup$ @zdm A very, very rough similar-ish problem is the secretary problem. $\endgroup$
    – orlp
    Commented Oct 30, 2019 at 0:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Commented Oct 30, 2019 at 17:15
  • 1
    $\begingroup$ 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.)$$ $\endgroup$
    – Neal Young
    Commented Oct 30, 2019 at 17:31

1 Answer 1

Reset to default
2
$\begingroup$

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

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$

Improve this answer
$\endgroup$

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.