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

Question

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

Answer 1

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$