# 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 don't see how the decreasing order of values is optimal for the first problem. Is there any reference for this? Nov 24 '13 at 16:45
• I don't understand the sentence "passing through the potential receivers the object defects the value of it". Could you rephrase or elaborate on what that means?
– D.W.
Nov 24 '13 at 19:02
• @D.W. Sorry for being unclear. It means that they decide to take the object or not one by one. If any one accept it, ignore all other people. Nov 25 '13 at 13:50

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!

• Welcome to CS.SE! Thank you for the detailed answer. I'm a bit puzzled how the time complexity can be $O(n^3)$ but the space complexity exponential -- the space complexity is upper-bounded by at most the time complexity (up to a logarithmic factor), as you can only touch at most $O(1)$ memory cells per unit of time.
– D.W.
Nov 7 '15 at 9:41
• That is what they claim. At the end of section VI: "The weakness of the proposed method is that the spatial complexity is much larger than the brute force search and the dynamic programming approach." I am not sure what this means and maybe they were just wrong. Nov 7 '15 at 9:49
• OK. That doesn't mean the space complexity is exponential; a space complexity of $\Theta(n^2)$ or $\Theta(n^3)$ might be enough to make it much larger than the space complexity of those two other algorithms (which might be linear or even less, depending on how they work).
– D.W.
Nov 7 '15 at 9:50
• You are right. So here is the dynamic programming approach paper they were refering to: [Optimal selection of channel sensing order in cognitive radio] (ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=4786510). Looking at Fig. 2, it seems that the space complexity might be $O(2^n)$, because for each state at each stage, you need to record the best branch pointing from one of the states at the previous stage to this current state. Nov 7 '15 at 10:21
• I still have trouble accepting that the time complexity is $\Theta(n^3)$ but the space complexity is $\Theta(2^n)$. An algorithm that takes $n^3$ steps of computation can touch only $n^3$ memory cells, so only $n^3$ memory cells can be non-zero, so you can replace memory with a hashtable mapping "memory address -> value stored there" and get a new algorithm whose running time is $O(n^3)$ and whose space complexity is $O(n^3)$.
– D.W.
Nov 7 '15 at 10:25

If you need to solve this in practice, I would guess that branch-and-bound might be pretty effective here -- at least, it'd be the first approach that I would try.

I would expect that the choice of the 1st receiver will have a much larger effect on $E(v)$ than the choice of the last receiver; and for all $i<j$, the identity of the $i$th receiver will typically have a larger effect on $E(v)$ than the identity of the $j$th receiver. This suggests applying branch-and-bound techniques, where you first select who the 1st receiver will be (enumerate all possibilities), then you select the 2nd receiver, and so on.

This gives you a tree of depth $n$, with $n!$ leaves, corresponding to all $n!$ possible orderings. An internal node at depth $d$ represents a partial assignment, where you've selected who the first $d$ receivers will be but you haven't selected the rest. Notice that, given the identity of the first $d$ receives, you can compute lower and upper bounds on the value of $E(v)$. For example:

$$p_1 w_1 v_1 + \dots + (1-p_1)(1-p_2) \cdots (1-p_{d-1}) p_d w_d v_d + \epsilon \le E(v)$$

and

$$E(v) \le p_1 w_1 v_1 + \dots + (1-p_1)(1-p_2) \cdots (1-p_{d-1}) p_d w_d v_d + \delta,$$

where

$$\epsilon = (1-p_1)(1-p_2) \cdots (1-p_d) p_n w_{d+1} v_n$$ $$\Delta = (1-p_1)(1-p_2) \cdots (1-p_d) (p_{d+1} w_{d+1} v_{d+1} + \dots + p_n w_n v_n),$$

where we've sorted the remaining $n-d$ possible receivers into order of decreasing value of $p_i v_i$. Now using these bounds, you can use branch-and-bound techniques to prune subtrees that are dominated by the current best solution, without needing to explore any node in the pruned subtree.

Given how the first few receivers make the biggest impact on $E(v)$, and this procedure chooses the first few receivers first, I suspect you might be able to prune many subtrees, and branch-and-bound might often be very efficient on real-world instances of this problem. Of course, there are no guarantees. Even if this works well in practice, the worst-case complexity of this approach is probably still exponential. And to find out whether it does work well in practice or not, you'd have to implement it and try it out.

I realize this doesn't tell you the worst-case complexity of the problem. For instance, it doesn't you whether this problem is NP-complete or not. For that, you'd have to look for some other ideas.

If the weighting function $w_i$ is an exponentially decreasing function of $i$, that is, if $w_i=e^{-i\tau}$, then the problem can be solved in $O(n\log{n})$ time. In this case, the objective function becomes:

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

Now, let us consider the expected values associated with $\mathbf{s}=\{1,2\}$ and $\mathbf{\tilde{s}}=\{2,1\}$. We have:

$$E_\mathbf{s}=p_1e^{-\tau}v_1+(1-p_1)p_2e^{-2\tau}v_2$$

and

$$E_\mathbf{\tilde{s}}=p_2e^{-\tau}v_2+(1-p_2)p_1e^{-2\tau}v_1.$$

It is easy to show that

$$E_\mathbf{s}>E_\mathbf{\tilde{s}}\Leftrightarrow\frac{p_1v_1}{e^\tau-1+p_1}>\frac{p_2v_2}{e^\tau-1+p_2}.$$

This pairwise exchange argument can be easily generalized to $n>2$ cases. That is, the optimal order $\mathbf{s}^*=\{s^*_1,s^*_2,\ldots,s^*_n\}$ is the one such that the following chain of inequalities holds:

$$\frac{p_{s^*_1}v_{s^*_1}}{e^\tau-1+p_{s^*_1}}>\frac{p_{s^*_2}v_{s^*_2}}{e^\tau-1+p_{s^*_2}}>\cdots>\frac{p_{s^*_n}v_{s^*_n}}{e^\tau-1+p_{s^*_n}}$$ which can be found using a sorting algorithm in $O(n\log{n})$ time.

For reference, see equation (2) in The Present Value Issue in a Sequential Selection Problem (you can set the costs $c_i$ to zero).