Optimal order to minimise time until first success

Question

Say you are a salesperson and you want to make a sale; there are $N$ customers on your list; customer $i$ takes $t_i$ time to talk to and there is $p_i$ probability to make the sale to that customer - you find out immediately at the end of the conversation with that customer whether they agree or not. You have no control over the $t_i$ or $p_i$ values but you choose in which order to call the customers. So, once you've chosen the order, you just call the customers one by one, each immediately after the last one, until you make the sale (can ignore the case where you never make the sale, as having negligible probability).

You want to minimise the expected/average amount of time until you succeed in your sale (you only need one sale).

I would like to find an algorithm to find that optimal ordering of the customers.

Here is what I thought about so far:

• Let $\sigma$ be a chosen order, i.e.a permutation of the $N$ indices. Let $I_{\sigma(i)}$ be an indicator random variable signifying that you speak to the $i$-th customer in your ordering $\sigma$.

  Then the random variable corresponding to the amount of time taken is $T(\sigma) = I_{\sigma(1)}t_{\sigma(1)} + I_{\sigma(2)}t_{\sigma(2)} + ... + I_{\sigma(N)}t_{\sigma(N)} $. Then, the average amount of time is $E(T(\sigma)) = E(I_{\sigma(1)}t_{\sigma(1)} + I_{\sigma(2)}t_{\sigma(2)} + ... + I_{\sigma(N)}t_{\sigma(N)}) = E(I_{\sigma(1)})t_{\sigma(1)} + E(I_{\sigma(2)})t_{\sigma(2)} + ... + E(I_{\sigma(N)})t_{\sigma(N)}$

  $E(I_{\sigma(i)})$ is the probability that you end up speaking with the $i$-th customer in the order, which is the probability that all preceding ones in the order fail, i.e. $E(I_{\sigma(N)}) = (1 - p_{\sigma(1)})(1 - p_{\sigma(2)})...(1 - p_{\sigma(i - 1)})$

  So overall the expected time is $t_{\sigma(1)} + (1 - p_{\sigma(1)})t_{\sigma(2)} + (1 - p_{\sigma(1)})(1 - p_{\sigma(2)})t_{\sigma(3)} + ...$

  So that at least gives the function we want to minimise.

• I thought of using dynamic programming, but onyl thought of ways to do it where I store the optimal ordering for each subset, of the $2^N$ subsets. I also thought of a kind of bubble sort where I start with some order and then try to swap two adjacent customers and see if that gives a better result, but that seems to me a greedy algorithm and not sure if woudl give the overall optimal result.

Answer 1

We can assume that $p_i > 0$ for all $i$: if $p_i = 0$, ask them last.

Consider a certain arrangement, where customer $j$ is contacted directly after customer $i$. What happens if we switch the order of $i$ and $j$? For a certain $\rho \ge 0$, we replace $$ \rho t_i + \rho (1-p_i) t_j $$ with $$ \rho t_j + \rho (1-p_j) t_i $$ in the sum. The difference between these two options (former minus latter) is $$ \Delta = \rho (p_j t_i - p_i t_j) = \rho p_i p_j \left( \frac{t_i}{p_i} - \frac{t_j}{p_j} \right). $$ This suggests the following greedy rule:

Arrange the customers in nondecreasing order of $\displaystyle\frac{t_i}{p_i}$.

Remaining details left to you.