I am working on the exercise 2.8 of Game Theory: an Introduction by Steven Tadelis.
I thought to solve this exercise by undertaking the steps sequentially, in order to minimize the loss in case of failure for each of the steps (all steps must be completed successfully in order to have a positive payoff).
However, I am searching for a way to compute the best order for the steps. Given that the number of decision trees grows with the factorial of the number of steps (in this case $3! = 6$ decision trees), it is not clear to me if there is a better solution instead of drawing all the trees.
The chapter 2 of the book also talks about backward induction, which in this case can be useful reduce the trees. However, is there a simpler methodology, i.e. without drawing the trees?
Juice: Bozoni is a Swiss maker of fruit and vegetable juice, whose products are sold at specialty stores throughout Western Europe. Bozoni is considering whether to add cherimoya juice to its line of products. “It would be one of our more difficult varieties to produce and distribute,” observes Johann Ziffenboeffel, Bozoni’s CEO. “The cherimoya would be flown in from New Zealand in firm, unripe form, and it would need its own dedicated ripening facility here in Europe.” Three successful steps are absolutely necessary for the new cherimoya variety to be worth producing. The industrial ripening process must be shown to allow the delicate flavors of the cherimoya to be preserved; the testing of the ripening process requires the building of a small-scale ripening facility. Market research in selected limited regions around Europe must show that there is sufficient demand among consumers for cherimoya juice. And cherimoya juice must be shown able to withstand the existing tiny gaps in the cold chain (the temperature-controlled supply chain) between the Bozoni plant and the end consumers (these gaps would be prohibitively expensive to fix). Once these three steps have been completed, there would be about €2,500,000 worth of expenses in launching the new variety of juice. A successful new variety will then yield profits, in expected present-value terms, of €42.5 million.
The three necessary steps can be done in parallel or sequentially, and in any order. Data about these three steps are given in the following table:
Probability of success Cost
Ripening process 0.7 1000000
Market research 0.3 5000000
Cold chain 0.6 500000
“Probability of success” refers to how likely it is that the step will be successful. If it is not successful, then that means that cherimoya juice cannot be sold at a profit. All probabilities are independent of each other (i.e., whether a given step is successful or not does not affect the probabilities that the other steps will be successful). “Cost” refers to the cost of undertaking the step (regardless of whether it is successful or not).
Suppose Mr. Ziffenboeffel calls you and asks your advice about the project. In particular he wants to know (i) should he undertake the three necessary steps in parallel (i.e., all at once) or should he undertake them sequentially, and (ii) if sequentially, what’s the correct order in which the steps should be done? What answers do you give him?
Part (i) is trivial – since there is a chance that a test may fail, and if it does, we can save the cost of the remaining tests, the tests should be undertaken sequentially.
Interestingly, the value of the successful product doesn't enter into the decisions on the order of the tests, since its contribution to the expected value is the same for all orders. Likewise, if tests $i$ and $j$ are outstanding, with success probabilities $p_i,p_j$ and costs $c_i,c_j$, the contributions from the case where both succeed are the same, and we can decide their order according to the expected cost $c_i+p_ic_j$ if we perform $i$ first and $c_j+p_jc_i$ if we perform $j$ first. The difference is $\Delta_{ij}=q_jc_i-q_ic_j$, where $q_k=1-p_k$ are the failure probabilities of the tests. Effectively, if $j$ fails we save the cost of $i$, and if $i$ fails we save the cost of $j$.
With the tests labeled by R, M and C, respectively, and money expressed in units of millions of euros, the three deltas are
\begin{align} \Delta_{\text{RM}}&=0.7\cdot1-0.3\cdot5=-0.8\;,\\ \Delta_{\text{MC}}&=0.4\cdot5-0.7\cdot0.5=1.65\;,\\ \Delta_{\text{CR}}&=0.3\cdot0.5-0.4\cdot1=-0.25\;. \end{align}
So if R and M are performed successively, we should perform R before M, and likewise C before M and C before R. The only order that satisfies those constraints is CRM. The expected value in this case is
$$ -0.5+0.6(-1+0.7(-5+0.3\cdot40))=1.84\;. $$
By comparison, the expected value for the opposite order MRC is
$$ -5+0.3(-1+0.7(-0.5+0.6\cdot40))=-0.365\;. $$
P.S. in response to the comment: Assuming non-zero failure probabilities, we can rewrite the condition $\Delta_{ij}\gt0$ as $c_i/q_i\gt c_j/q_j$. This shows that the total antisymmetric relation defined by the pairwise comparisons is transitive and thus actually a total order that determines a unique optimal ordering for any number of tests, namely, the ordering with ascending $c_i/q_i$.