How to optimise waterfall questions of purchase value Imagine I have an item I want to sell to a person. I know for sure that the person is not willing to pay more than \$X for this item, but I don't know which value between \$0 and \$X they are willing to pay for it, and I'm equally uncertain about all of them. So if I call how much they're willing to pay for it V, $p(V)$ is a uniform distribution between 0 and X.
I cannot, however, straightforwardly ask them. What I can do instead is ask whether they're willing to pay some value \$Y for the item. If they are, then I get \$Y and sell the item. If they aren't, then I cannot sell the item at all, and they pay me nothing.
Therefore, they will buy the product if they value my item at \$Y or more and will not otherwise, and so the expected value of asking for \$Y is $p(V\geq Y) * Y$. Since $p(V) = 1/X$, it is straightforward to see that the value Y which maximises that expectation is X/2, and the actual expected value is \$X/4.

Suppose, however, that I can ask this person twice instead of just once. That is, I can ask them whether they're willing to pay \$Y for the item. Then:


*

*If they are, I get $Y and sell the item.

*If they are not, I can ask again for a different value \$X, and then either I sell the item for \$X or I don't and get nothing.


An initial, naive solution would be to just iterate the above suggestion: first I ask for \$X/2 and then, if I'm refused, I update my probability distribution and ask for \$X/4. The expected value of that strategy is \$5X/16 (50% chance that I get \$X/2, then a 50% chance that there's a 50% chance that I get \$X/4, and then in the remaining case I get \$0).
However, that is not the optimal strategy. Suppose, instead, that I decide to ask for \$2X/3 and then for \$X/3. There's a 1/3 chance that they'll take me up on my first request and a 2/3 chance that they won't; after that, there's a 50% chance that they'll take me up on my second request, and a 50% chance that they won't. The final expected value of that strategy is \$X/3, which is greater than the \$5X/16 from the previous idea.
How would I have found this out in advance? What if I'm allowed to ask N questions, is it always better to ask for \$(N - 1)X/N and then \$(N - 2)X/N and so on until I get to \$X/N?

Now, suppose instead that I have M different people who might be willing to buy my item. I have a joint prior distribution about how much they value my item. I can ask a total of N questions between them all and, since my beliefs about how much they value this item are correlated, whenever one of them refuses the item this is also information about how much the others value it.
How do I solve this problem? If it's too open, suppose I constrain it to having a multivariate Normal distribution (with known mean vector and covariance matrix) for my prior beliefs about how much they value my item; where do I go from here?
 A: This kind of problem is an optimisation problem that can either be solved directly from the profit function, or in two-steps using backward induction.  To show you how to uses either of these methods, I will first write the optimisation problem out in a helpful mathematical form.  I will show the solution by both methods.  In this particular case, direct optimisation is much simpler, but if you have more difficult cases then the method of backward induction can be simpler.

The optimisation problem: You have a continuous random variable $V \sim \text{U}(0, x)$ and you will choose two offers $y_1$ and $y_2$.  Your profit is the random variable:
$$\pi_V(y_1,y_2) = y_1 \cdot \mathbb{I}(y_1 \leqslant V) + y_2 \cdot \mathbb{I}(y_2 \leqslant V < y_1).$$
Your goal is to choose a first and second offer to maximise your expected profit, which is the expected value of the above function.

Direct optimisation: With direct optimisation we write out the expected profit as a bivariate function of your two decision variables, and we then conduct multivariate optimisation using standard calculus techniques.  We can restrict attention to the cases $0 \leqslant y_2 < y_1 \leqslant x$, since both offers must be within the support of $V$, and your second offer should be lower than your first.  (The second offer only matters if the first is rejected, so it makes no sense to make a second offer that is equal or greater to the first.)  Restricting attention to this case, the expected profit function can be written as the bivariate function:
$$\begin{equation} \begin{aligned}
\bar{\pi}(y_1,y_2) 
&\equiv \mathbb{E}(\pi_V(y_1,y_2)) \\[6pt]
&= y_1 \cdot \mathbb{P}(y_1 \leqslant V) + y_2 \cdot \mathbb{P}(y_2 \leqslant V < y_1) \\[6pt]
&= y_1 \cdot \frac{x-y_1}{x} + y_2 \cdot \frac{y_1-y_2}{x} \\[6pt]
&= \frac{1}{x} \big( y_1 (x-y_1) + y_2 (y_1-y_2) \big) \\[6pt]
&= \frac{1}{x} \big( y_1 x -y_1^2 + y_2 y_1 - y_2^2 \big). \\[6pt]
\end{aligned} \end{equation}$$
The gradient vector and Hessian matrix of this function are given respectively by:
$$\nabla \bar{\pi}(y_1,y_2) 
= \frac{1}{x} \begin{bmatrix} 
x - 2y_1 + y_2 \\ y_1 - 2 y_2
\end{bmatrix}
\quad \quad \quad \quad \quad 
\nabla^2 \bar{\pi}(y_1,y_2) 
= \frac{1}{x} \begin{bmatrix} 
- 2 & 1 \\ 1 & - 2 \
\end{bmatrix}.$$
It is simple to show that the Hessian is negative definite (eigenvalues are $\lambda_1 = -3$ and $\lambda_2 = -1$), so the function is strictly concave.  This means that it has a unique critical point that is the global maximising value of the function.  This point satisfies the first-order condition (FOC): 
$$\mathbf{0} = \nabla \bar{\pi}(\hat{y}_1,\hat{y}_2) 
= \frac{1}{x} \begin{bmatrix} 
x - 2\hat{y}_1 + \hat{y}_2 \\ \hat{y}_1 - 2 \hat{y}_2
\end{bmatrix}.$$
Solving these two equations in two unknowns yields the optimising prices:
$$\hat{y}_1 = \frac{2}{3} \cdot x
\quad \quad \quad \hat{y}_2 = \frac{1}{3} \cdot x.$$

Optimisation by backwards induction: With backward induction we begin by optimising the later decision, and then work backwards to optimise the earlier decision, assuming optimisation of the later decision.  So, let's imagine that you have already made some first offer of $0 \leqslant y_1 \leqslant x$ and it has been rejected, so now you are going to make your second offer.  Conditional on the rejection of the first offer, we have the posterior distribution $V | V < y_1 \sim \text{U}(0, y_1)$, so the expected profit from a new offer of $0 \leqslant y_2 \leqslant x$ is:
$$\begin{equation} \begin{aligned}
\bar{\pi}(y_2) 
&= \mathbb{E}(\pi_V(y_1,y_2) | V \sim \text{U}(0, y_1)) \\[6pt]
&= \mathbb{E}(y_2 \cdot \mathbb{I}(y_2 \leqslant V) | V \sim \text{U}(0, y_1)) \\[6pt]
&= y_2 \cdot \frac{y_1-y_2}{y_1} \cdot \mathbb{I}(y_2 < y_1) \\[6pt]
&= \frac{1}{y_1} \cdot (y_2 y_1 - y_2^2) \cdot \mathbb{I}(y_2 < y_1) \\[6pt]
\end{aligned} \end{equation}$$
Univariate optimisation (omitting the calculus steps) yields the optimising value:
$$\hat{y}_2 = \frac{1}{2} \cdot y_1.$$
Having obtained this optimising value, we proceed backward to the first offer.  Assuming that the second offer is optimal, the expected profit as a function of the first offer $y_1$ is:
$$\begin{equation} \begin{aligned}
\bar{\pi}(y_1|\hat{y}_2) 
&= \mathbb{E}(\pi_V(y_1,\hat{y}_2) | V \sim \text{U}(0, x)) \\[6pt]
&= \mathbb{E}(\pi_V(y_1,y_1/2) | V \sim \text{U}(0, x)) \\[6pt]
&= \mathbb{E}(y_1 \cdot \mathbb{I}(y_1 \leqslant V) + \frac{y_1}{2} \cdot \mathbb{I}(y_1/2 \leqslant V < y_1) | V \sim \text{U}(0, x)) \\[6pt]
&= y_1 \cdot \mathbb{P}(y_1 \leqslant V) + \frac{y_1}{2} \cdot \mathbb{P}(y_1/2 \leqslant V < y_1) \\[6pt]
&= y_1 \cdot \frac{x-y_1}{x} + \frac{y_1}{2} \cdot \frac{y_1/2}{x} \\[6pt]
&= \frac{1}{x} \big( x y_1 - y_1^2 + \frac{y_1^2}{4} \big) \\[6pt]
&= \frac{1}{x} \big( x y_1 - \frac{3 y_1^2}{4} \big). \\[6pt]
\end{aligned} \end{equation}$$
Univariate optimisation (omitting the calculus steps) yields the optimising value:
$$\hat{y}_1 = \frac{2}{3} \cdot x.$$
Substitution of this optimum offer to the second optimising offer then gives:
$$\hat{y}_2 = \frac{1}{3} \cdot x.$$
This is the same answer that is obtained via direct optimisation.

The above methods can easily be extended to the more general case where you have more than two opportunities for offers.  As in the above case, the simplest method is the direct method ---i.e., you form a multivariate function for the expected profit conditional on a vector of offers, and then optimise this function using standard calculus techniques.
A: Short answer:


*

*Indeed, when the same customer may be approached at most $n$ times, it is optimal to start with offer $y_1=\frac{n-1}{n}x$ and decrease the price by $\frac{x}{n}$ with every refusal.

*The above result only holds for the uniform distribution of the customer's valuation $v$. Under the normal distribution, closed form answer is feasible only numerically.

*When $n$ customer may be approached, each at most once, the optimization problem assumes a double layer structure: inner smooth optimization problem is wrapped in outer combinatorial optimization task. Coupled with non-trivial covariance structure in valuations, this makes the analytical (and/or tractable) closed form solution infeasible. 

*A promising approach for the latter case would be to assume that valuations $v_1,...,v_n$ are uniformly distributed over a parallelotope and leverage the polyhedral computation methods to speed up computations.
Detailed answer


*

*Approaching the same customer at most $n$ times
When we are dealing with asingle customer and may try up to $n$ times until he walks away, the problem solution is straightforward and and follows the logic presented in the other answer to this post. The expected profit can be written down as follows:


\begin{align}
\mathbb{E}\pi =& y_1 \cdot \mathbb{P}(v > y_1) + y_2 \cdot \mathbb{P}(v < y_1 \cap v < y_2 )+ ... + y_n \cdot \mathbb{P}(v < y_n \cap (\cap_{j=1}^{n-1} v < y_j )) =\\
= & \sum_{i=1}^n y_i \mathbb{P}(v < y_n \cap (\cap_{j=1}^{i-1} v < y_j )) = \\
= & \sum_{i=1}^n y_i \mathbb{P}(y_i < v < y_{i-1})
\end{align}
where the implicit convention is that $y_0$ is some upper bound of the support of $v$ so that $\mathbb{P}( v < y_0) = 1$.
The solution to the problem is thus a sequence $\mathbf{y}:=(y_1,...,y_n)$ maximizing the expected profit. In the case of uniform distribution, $v \sim U[0, x]$ the first order conditions with respect to $y_i$ represent a system of linear equations:
\begin{equation}
\frac{\partial}{\partial y_i} \mathbb{E} \pi = 0 \iff 
\begin{cases}
 \frac{x-y_1}{x} - y_1 \frac{1}{x} + y_2 \frac{1}{x}  = 0  \\
 \frac{y_{i-1}-y_{i}}{x} - y_i \frac{1}{x} + y_{i+1} \frac{1}{x} = 0 \quad \forall i=2,..n-1 \\
 \frac{y_{n-1}-y_{n}}{x} - y_n \frac{1}{x} = 0
\end{cases}
\end{equation}
It is immediate from the second equality that there exists an increment $\delta$ such that  $\forall i=2,..n$ holds $y_{i} = y_{i-1} - \delta$, implying that $y_i = y_1 - (i-1)\delta$. This is consistent with the first and the last equality iff $\delta = \frac{x}{n}$ and $y_1 = \frac{n-1}{n}x$ as per intuition described in the OP.  
Remark:
Once we switch to a more contrived assumption about the distribution of the customer valuation, explicit answer becomes impossible to obtain analytically. E.g. in the case of a normal distribution truncated to the interval $[0,x]$ the system of first order conditions becomes
\begin{equation}
\begin{cases}
 \frac{\Phi(x)-\Phi(y_1)}{\Phi(x)-1/2} - y_1 \frac{\phi(y_1)}{\Phi(x)-1/2} + y_2 \frac{\phi(y_1)}{\Phi(x)-1/2}  = 0  \\
 \frac{\Phi(y_{i-1})-\Phi(y_{i})}{\Phi(x)-1/2} - y_i \frac{\phi(y_i)}{\Phi(x)-1/2} + y_{i+1} \frac{\phi(y_i)}{\Phi(x)-1/2} = 0 \quad \forall i=2,..n-1 \\
 \frac{\Phi(y_{n-1})-\Phi(y_{n})}{\Phi(x)-1/2} - y_n \frac{\phi(y_n)}{\Phi(x)-1/2} = 0
\end{cases}
\end{equation}
where $\phi(z) = (2\pi)^{-1/2}\exp(-\frac{z^2}{2})$ is the pdf of the standart normal and $\Phi(z) = \int_{-\infty}^{z} \phi(\xi)d\xi$ is its cdf. 
One can clearly see that the analytical closed form solution is infeasible in this case.


*Approaching at most $n$ different customers no more than once each
First take a look at a 2-customer problem: for a sequence of offers $y_1, y_2$  and the ordering (permutation) of clients $\sigma(1),\sigma(2)$ the expected revenue looks as follows:
\begin{align}
 \mathbb{E}\pi = &y_1 \mathbb{P}(v_{\sigma(1)} > y_1)
+ \mathbb{P}(v_{\sigma(1)} < y_1) \cdot  y_2 \mathbb{P}(v_{\sigma(2)}>y_2 | y_1 > v_{\sigma(1)}) =\\
= & y_1 \mathbb{P}(v_{\sigma(1)} > y_1) + y_2 \mathbb{P}(v_{\sigma(1)} < y_1 \cap v_{\sigma(2)}>y_2).
\end{align}
Now, it is not hard to write down the formula for $n$ clients:
\begin{align}
   \mathbb{E}\pi =& \sum_{i=1}^n y_i \cdot \mathbb{P}\left(v_{\sigma(i)} > y_i \cap ( \cap_{j=1}^{i-1} v_{\sigma(j)}<y_j)\right) = \\
 = & \sum_{i=1}^n y_i \cdot (\mathbb{P}\left(\cap_{j=1}^{i-1} v_{\sigma(j)}<y_j\right) - \mathbb{P}\left(\cap_{j=1}^i v_{\sigma(j)}<y_j\right) )= \\
= & y_1 + \sum_{i=1}^{n} (y_{i+1} - y_i) \mathbb{P}\left(\cap_{j=1}^{i} v_{\sigma(j)}<y_j\right),
\end{align}
where the last equality holds true if we posit $y_{n+1}\equiv 0$.
Here just as in the remark above, one can see that analytical closed form solution of the inner smooth optimization problem is impossible to obtain under the joint normality assumption as the first order conditions will certainly be non-polynomial.
This and given that the outer problem is combinatorial makes the numerical (algorithmical) solution of the problem the most promising way forward.
An idea for a way forward:
Computation of probabilities $\mathbb{P}\left(\cap_{j=1}^{i} v_{\sigma(j)}<y_j\right)$ might turn out to be easier if we assume a distorted uniform distribution (uniform over a [parallelotope][3]). I haven't seen anything like this in the litterature myself, but it might be the good compromise between the simplicity of operations with the uniform distribution and the capacity of the normal to capture non-trivial covariance structure. 
More precisely, one may assume that $\mathbf{v}=(v_1,...,v_n)$ is distributed uniformly over an $n$-parallelotope. In this case the parameter of the distribution would be the matrix of $n$ stacked vectors $a_1,...,a_n$ in the frame of the parallelotope, and the unconditional density would be the inverse of its volume, whereas conditional 
probabilities may be computed as volumes of straightforwardly formulated convex polytopes.
Given a reasonably fast oracle for computing optimal $\mathbf{y}$, the combinatorial optimization for moderate $n$ may then be performed by a simple comparison of expected profits of different permutations.
