# 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? • Hi Pedro, nice question. In the M people situation, what happens when the price you set is low enough for two or more people? Who gets the item? Nov 7, 2019 at 9:55 • I only ask one person at a time so whoever I ask first gets the item. Presumably I'd ask first whoever had the highest probability of valuing the item at that value X or higher, but also presumably I'd have some fallback option if they were identical. I don't expect them to be identical in most cases, though; the correlation between any two people in my multivariate distribution for how much they value the item is probably never 1. – Red Nov 7, 2019 at 13:51 ## 2 Answers Short answer: 1. 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. 2. 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. 3. 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. 4. 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 1. 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: $$$$\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}$$$$ 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{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}$$$$ 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. 1. 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)} 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)} 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. • If the "each at most once" problem is intractable, then I expect so is the problem where I can ask any of them any number of times? Or "each at most K times"? – Red Nov 12, 2019 at 18:34 • Well, yes. "One customer at most N times" is the special case of "each at most K times", and there you run into intractability already under the normal distribution. On the bright side, if you construct an algorithm similar to what I mentioned in the last remark, exact solution of these two additional problems is within reach as well. I guess one could even try to do so in Mathematica, although I'd go with Python myself. Nov 12, 2019 at 19:14 • Btw, may I ask, what is the application of this model? I you haveNpotential buyers with unknown valuations, why not organize an auction? There is an impressive body of theoretical results there. Nov 12, 2019 at 19:15 • It's the problem of waterfall optimisation of ad pricing within a mobile app, where each customer is an adnetwork and the "products" I'm selling are ad opportunities within the app. And auctions would get computationally infeasible really quickly in this environment. – Red Nov 12, 2019 at 21:31 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{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} 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{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} 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{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} 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. • Thanks! My main concern about this, though, is – how do I extend this to the multivariate case from my last section, where I have M different people and different beliefs about how much they value my item? And also, the probability distribution is not necessarily a multivariate uniform – in that case I actually have a multivariate Gaussian. – Red Nov 6, 2019 at 14:36 • @PedroCarvalho in the case of two people. Say their limits for accepting the offers are distributed asf(v_1,v_2)$, your first offer to one of them is$y_1$, and your follow up offers are$y_s$in case of success of$y_f$in case of failure, then the (expected) money you make with these two is the integral: $$(y_1) \int_{y_1}^{\infty} \int_{0}^{\infty} f(v_1,v_2) \text{d}v_2 \text{d}v_1 + (y_s) \int_{y_1}^{\infty} \int_{y_s}^{\infty} f(v_1,v_2) \text{d}v_2 \text{d}v_1 + (y_f) \int_{0}^{y_1} \int_{y_f}^{\infty} f(v_1,v_2) \text{d}v_2 \text{d}v_1$$ Nov 12, 2019 at 15:15 • You can do the same backward trick by optimizing$y_s$and$y_f$given$y_1$, then optimizing$y_1$for the final solution. When this becomes difficult to do analytically then you might do it computationally. Nov 12, 2019 at 15:19 • I'm not sure I understand what$y_s$and$y_f\$ are? I will only ask a second time if the first time wasn't taken.
– Red
Nov 12, 2019 at 18:36