Prove or disprove NP-Completeness: An optimal ordering problem

Consider assigning a single object to $n$ potential receivers. It can only be assigned to one person.

For each receiver $k$, there is a value of profit $v_k$ and a probability $p_k$.
Fix an ordering of the receivers, then for the $i$th receiver he accept the object with probability $p_i$, if he does, we gain a value $v_i$; if he doesn't, consider the next person in the ordering.

Then the expected value we gain is

$E(V)=p_1v_1+(1-p_1)p_2v_2+\cdots +(1-p_1)(1-p_2)\cdots (1-p_{n-1})p_nv_n$

It can be easily seen: to maximize the expected value we gain, the ordering should be in the decrease of the $v$.

But since passing through the potential receivers the object defects the value of it, the $i$th receiver has a parameter $w_i$ where $w_1>w_2>\cdots>w_n$.

$v_k$ is assigned to each person $k$, and $w_i$ is assigned to the $i$th person in the ordering. For example if the $3$rd person in the ordering is person $5$, then he has $v_5$ and $w_3$.

so the expected value changes to

$E(v)=p_1w_1v_1+(1-p_1)p_2w_2v_2+\cdots+(1-p_1)(1-p_2)\cdots(1-p_{n-1})p_nw_nv_n$

Is there a polynomial algorithm to give an optimal ordering that maximizes the expected value? Or should this be NP-Complete?

Any hint is appreciated. Thanks in advance.

I think your question is better written as follows (to avoid ambiguity):
Find an order $\mathbf{s}=(s_1,s_2,...s_n)$ (that is, a permutation of $(1,...,n)$) such that
$$
E_{\mathbf{s}}(\mathbf{v},\mathbf{p})=p_{s_1}w_1v_{s_1}+(1-p_{s_1})p_{s_2}w_2v_{s_2}+\cdots+\left[\prod_{j=1}^{n-1}(1-p_{s_j})\right]p_{s_n}w_nv_{s_n}.
$$
is maximized, where $w_i$ is the positive weight for the expected achievable value at the $i^{th}$ stage, $\mathbf{v}=\{v_1,v_2,\ldots,v_n\}$ and $\mathbf{p}=\{p_1,p_2,\ldots,p_n\}$ are the positive profits and the probabilities associated with the $n$ receivers. If $w_i$ is a linearly decreasing function, say, if $w_i=1-i\tau$, the objective function becomes:

$$
E_{\mathbf{s}}(\mathbf{v},\mathbf{p})=p_{s_1}(1-\tau)v_{s_1}+(1-p_{s_1})p_{s_2}(1-2\tau)v_{s_2}+\cdots+\left[\prod_{j=1}^{n-1}(1-p_{s_j})\right]p_{s_n}(1-n\tau)v_{s_n}.
$$

Now, let us consider the following two orders which differ only in the $(i-1)^{th}$ and the $i^{th}$ positions: $\mathbf{s}=\{\ldots,\underset{i-1}{1},\underset{i}{2},\ldots\}$ and $\mathbf{\tilde{s}}=\{\ldots,\underset{i-1}{2},\underset{i}{1},\ldots\}$. It is easy to show that

$$
E_\mathbf{s}>E_\mathbf{\tilde{s}}\Leftrightarrow\frac{v_1}{\frac{\tau}{\theta_1}+w_i }>\frac{v_2}{\frac{\tau}{\theta_2}+w_i }.
$$
which (I believe) implies that the problem cannot be solved by a simple index policy (i.e., a sorting algorithm), because whether $\mathbf{s}=\{\ldots,\underset{i-1}{1},\underset{i}{2},\ldots\}$ or $\mathbf{\tilde{s}}=\{\ldots,\underset{i-1}{2},\underset{i}{1},\ldots\}$ is better really depends on $w_i$ (or the stage number $i$).

Here is a paper Optimal wideband spectrum sensing order based on decision-making tree in cognitive radio, which gives an exact algorithm assuming $w_i=1-i\tau$ and they claim that it runs in polynomial time $O(n^3)$, although the space complexity seems to be exponential.

I believe their algorithm holds for general monotonically decreasing $w_i$ values (with respect to $i$).

However, it seems that they solve the problem by finding the optimum from a set of candidate sequences. The running time is assumed to be proportional to the size of this candidate set. In order to find this candidate set, a branch and bound approach is adopted, but the time needed to compute this candidate set is ignored. So I double if their running time claim is valid.. I would really appeciate it if someone can convince me that their $O(n^3)$ claim is valid (and so it only takes at most $O(n^3)$ time to find the candidate set)? or if the problem (with $w_i=1-i\tau$) is actually np-hard? Thank you!

StackExchange Computer Science Q#18296, answer score: 2