# Is the weighted sum of subset prefix product problem NP-hard?

I have this strange problem where we have a set of positive numbers $$M$$, a fixed number $$n$$, and a function $$f: M \rightarrow R^+$$ mapping each number in M to another positive number. We want to know if we can select non-repetitive numbers $$a_1, \cdots, a_n \in M$$, such that the sum over weighted prefix product $$\sum_{i=1}^n f(a_i) \cdot \prod_{j=1}^{i} a_j$$ is maximized. Does anyone know if this is NP-hard?

Edit: What about for some fixed $$m \in [n]$$ and $$p \in (0, 1)$$, maximizing $$\sum_{i=1}^m f(a_i) \cdot \prod_{j=1}^{i} a_j + p \cdot \sum_{i=m+1}^n f(a_i) \cdot \prod_{j=1}^{i} a_j$$?

Theorem 1. The problem has an $$O(m\log m)$$-time algorithm, where $$m=|M|$$.

Proof sketch. Fix an instance of the problem. Assume without loss of generality that $$M\subseteq (0, 1)$$. (Otherwise an optimal solution $$a_1,\ldots, a_n$$ for $$M$$ can be obtained by computing an optimal solution $$a'_1, a'_2, \ldots, a'_{n'}$$ for $$M'=M\cap (0, 1)$$, then prepending the elements in $$M\cap [1, \infty)$$ in decreasing order.)

By rewriting, the problem is equivalent to finding $$p=(p_1, p_2, \ldots, p_n) \subseteq M$$ maximizing $$\text{value}(p) = \sum_{i=1}^n \big(\textstyle\prod_{j=1}^{i-1} p_j\big) (1-p_i) g(p_i),~~~~~~~~~(1)$$ where $$g(z) = f(z)z/(1-z)$$.

Remark for intuition. This interpretation is nice because then $$\text{value}(p)$$ is the expectation of the value returned by the following random process:

1. for $$i \gets 1, 2, \ldots, n$$:
2. $$~~~$$ with probability $$1-p_i$$, halt and return $$g(p_i)$$ (otherwise (with probability $$p_i$$) continue)
3. return 0

With this interpretation, it is not too hard to see that we should use all elements of $$M$$ (in some order), and further that we should use them greedily---in order of decreasing $$g(p_i)$$. The proof below gives the details.

Here is the algorithm:

1. let $$q=(q_1, q_2, \ldots, g_m)$$ be $$M$$ sorted by decreasing $$g(q_i)$$ (breaking ties arbitrarily).
2. return $$q$$

Clearly this can be done in $$O(m\log m)$$ time. To finish we show that $$q$$ is an optimal solution.

By inspection of (1), there is an optimal solution that uses all elements of $$M$$ (as appending unused elements to any solution cannot decrease the cost). Let $$p=(p_1, p_2, \ldots, p_m)$$ be any such optimal solution. Define an inversion in $$p$$ to be a pair $$i, j\in [m]$$ such that $$i < j$$ and $$r(i) > r(j)$$, where $$r(i)$$ is the rank of $$p_i$$ in $$q$$ (so $$q_{r(i)} = p_i$$). If there are no inversions, then $$p=q$$ so $$q$$ is optimal, and we are done. Otherwise, there is an inversion $$(i, i+1)$$. Consider modifying $$p$$ by swapping $$p_i$$ with $$p_{i+1}$$. By calculation, this swap increases the solution value by $$\prod_{j=1}^{i-1} p_j$$ times \begin{aligned} &(1-p_{i+1}) g(p_{i+1})+ p_{i+1} (1-p_i) g(p_i) \\ {}-{} & p_i (1-p_{i+1}) g(p_{i+1}) - (1-p_i) g(p_i) \\ {}={} & [g(p_{i+1}) - g(p_i)] (1-p_i)(1-p_{i+1}) \\ {}\ge{} & 0 & (\text{using } r(i) > r(i+1), \text{ so } g(p_i) \le g(p_{i+1})). \end{aligned} So this swap reduces the number of inversions by one and yields another optimal solution. So repeatedly swapping yields an optimal solution $$p$$ with no inversions, i.e., with $$p=q$$, so $$q$$ is optimal.$$~~~~\Box$$

• Thank you so much for this thorough response! I wasn't sure if it was easy or hard at first glance. Commented Mar 22, 2022 at 21:01
• Sure. One thing: in general it improves posts to add some context about where the problem comes from, what you've tried, and so on. See cstheory.stackexchange.com/help for more advice. Commented Mar 22, 2022 at 21:10
• Yeah this makes sense! I will give more context in the future. (The original problem I was considering was that there are a bunch of boxes, each one with probability $p_i$ has a prize of value $h_i$, and remaining probability with nothing. Our task is to order them in advance and then inspect them one by one, once we see a prize we have to take it and leave. When we can order them however we like it's clear we should inspect box in decreasing $h_i$, but what if some of the boxes have fixed position that we cannot change? The special case of 1-box fixed can be converted to my posted Q. ) Commented Mar 22, 2022 at 23:33
• (Our objective is to have the highest expected prize value.) Commented Mar 22, 2022 at 23:34
• Interesting. How can the case with one box fixed be reduced to your posted question? If you'd like to ask about the more general question, I guess you can make another post. Commented Mar 23, 2022 at 2:28