Cómo optimizar las preguntas de valor de compra en cascada

Question

Imagina que tengo un artículo que quiero vender a una persona. Sé con seguridad que la persona no está dispuesta a pagar más de \$X for this item, but I don't know which value between \$ 0 y \$X ellos son dispuestos a pagar por ello, y tengo la misma incertidumbre sobre todos ellos. Así que si llamo a cuánto están dispuestos a pagar por él V, $p(V)$ es una distribución uniforme entre 0 y X.

Sin embargo, no puedo preguntarles directamente. Lo que sí puedo hacer es preguntar si están dispuestos a pagar algún valor \$Y for the item. If they are, then I get \$ Y y vender el artículo. Si no es así, no puedo vender el artículo y no me pagan nada.

Por lo tanto, comprarán el producto si valoran mi artículo en \$Y or more and will not otherwise, and so the expected value of asking for \$ Y es $p(V\geq Y) * Y$ . Desde $p(V) = 1/X$ es sencillo ver que el valor Y que maximiza esa expectativa es X/2, y el valor real esperado es \$X/4.

---

Supongamos, sin embargo, que puedo pedirle a esta persona dos veces en lugar de una sola vez. Es decir, puedo preguntarles si están dispuestos a pagar \N por el artículo. Entonces:

• Si lo son, recibo $Y y vendo el artículo.
• Si no lo son, puedo volver a pedir un valor diferente \$X, and then either I sell the item for \$ X o no lo hago y no consigo nada.

Una solución inicial e ingenua sería simplemente iterar la sugerencia anterior: primero pido \$X/2 and then, if I'm refused, I update my probability distribution and ask for \$ X/4. El valor esperado de esa estrategia es \$5X/16 (50% chance that I get \$ X/2, entonces un 50% de posibilidades de que haya un 50% de posibilidades de que obtenga \$X/4, and then in the remaining case I get \$ 0).

Sin embargo, esa no es la estrategia óptima. Supongamos, en cambio, que decido pedir \$2X/3 and then for \$ X/3. Hay un 1/3 de posibilidades de que me acepten la primera solicitud y un 2/3 de posibilidades de que no lo hagan; después, hay un 50% de posibilidades de que me acepten la segundo y un 50% de posibilidades de que no lo hagan. El valor final esperado de esa estrategia es \$X/3, which is greater than the \$ 5X/16 de la idea anterior.

¿Cómo iba a saber esto de antemano? Y si se me permite hacer N preguntas, ¿es siempre mejor pedir \$(N - 1)X/N and then \$ (N - 2)X/N y así sucesivamente hasta llegar a \$X/N?

---

Ahora, supongamos que tengo M personas diferentes que podrían estar dispuestas a comprar mi artículo. Tengo una distribución conjunta a priori sobre el valor de mi artículo. Puedo pedir un total de N preguntas entre todos ellos y, dado que mis creencias sobre cuánto valoran este artículo están correlacionadas, cada vez que uno de ellos rechaza el artículo esto es también información sobre cuánto lo valoran los demás.

¿Cómo puedo resolver este ¿Problema? Si es demasiado abierto, supongamos que lo limito a tener una distribución normal multivariante (con vector de medias y matriz de covarianza conocidos) para mis creencias previas sobre cuánto valoran mi artículo; ¿a dónde voy desde aquí?

Answer 1

Este tipo de problema es un problema de optimización que puede resolverse directamente a partir de la función de beneficio, o en dos pasos utilizando inducción inversa . Para mostrarte cómo utilizar cualquiera de estos métodos, primero escribiré el problema de optimización en una forma matemática útil. A continuación, mostraré la solución por ambos métodos. En este caso particular, la optimización directa es mucho más sencilla, pero si tienes casos más difíciles, el método de inducción hacia atrás puede ser más simple.

---

El problema de la optimización: Se tiene una variable aleatoria continua $V \sim \text{U}(0, x)$ y elegirás dos ofertas $y_1$ y $y_2$ . Su beneficio es la variable aleatoria:

$$\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).$$

Su objetivo es elegir una primera y una segunda oferta para maximizar su beneficio esperado, que es el valor esperado de la función anterior.

---

Optimización directa: Con la optimización directa escribimos el beneficio esperado como una función bivariable de sus dos variables de decisión, y a continuación realizamos la optimización multivariable utilizando técnicas de cálculo estándar. Podemos limitar la atención a los casos $0 \leqslant y_2 < y_1 \leqslant x$ ya que ambas ofertas deben estar dentro del soporte de $V$ La segunda oferta debe ser más baja que la primera. (La segunda oferta sólo importa si se rechaza la primera, por lo que no tiene sentido hacer una segunda oferta que sea igual o mayor que la primera). Restringiendo la atención a este caso, la función de beneficio esperado puede escribirse como la función bivariante

$$\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}$$

El vector gradiente y la matriz hessiana de esta función vienen dados respectivamente por:

$$\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}.$$

Es sencillo demostrar que el hessiano es negativo definido (los valores propios son $\lambda_1 = -3$ y $\lambda_2 = -1$ ), por lo que la función es estrictamente cóncava. Esto significa que tiene un único punto crítico que es el valor maximizador global de la función. Este punto satisface la condición de primer orden (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}.$$

Resolviendo estas dos ecuaciones en dos incógnitas se obtienen los precios de optimización:

$$\hat{y}_1 = \frac{2}{3} \cdot x \quad \quad \quad \hat{y}_2 = \frac{1}{3} \cdot x.$$

---

Optimización por inducción hacia atrás: Con la inducción hacia atrás empezamos optimizando la decisión posterior, y luego trabajamos hacia atrás para optimizar la decisión anterior, asumiendo la optimización de la decisión posterior. Así, imaginemos que ya se ha hecho una primera oferta de $0 \leqslant y_1 \leqslant x$ y ha sido rechazada, así que ahora va a hacer su segunda oferta. Condicionado al rechazo de la primera oferta, tenemos la distribución posterior $V | V < y_1 \sim \text{U}(0, y_1)$ por lo que el beneficio esperado de una nueva oferta de $0 \leqslant y_2 \leqslant x$ es:

$$\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}$$

La optimización univariante (omitiendo los pasos de cálculo) da como resultado el valor de optimización:

$$\hat{y}_2 = \frac{1}{2} \cdot y_1.$$

Una vez obtenido este valor de optimización, procedemos a retroceder hasta la primera oferta. Suponiendo que la segunda oferta es óptima, el beneficio esperado en función de la primera oferta $y_1$ es:

$$\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}$$

La optimización univariante (omitiendo los pasos de cálculo) da como resultado el valor de optimización:

$$\hat{y}_1 = \frac{2}{3} \cdot x.$$

La sustitución de esta oferta óptima por la segunda oferta optimizadora da como resultado:

$$\hat{y}_2 = \frac{1}{3} \cdot x.$$

Es la misma respuesta que se obtiene mediante la optimización directa.

---

Los métodos anteriores pueden extenderse fácilmente al caso más general en el que se tienen más de dos oportunidades de ofertas. Al igual que en el caso anterior, el método más sencillo es el método directo, es decir, se forma una función multivariable para el beneficio esperado condicionado a un vector de ofertas y, a continuación, se optimiza esta función utilizando técnicas de cálculo estándar.

Answer 2

Respuesta corta:

1. En efecto, cuando un mismo cliente puede ser abordado como máximo $n$ veces, es óptimo comenzar con la oferta $y_1=\frac{n-1}{n}x$ y disminuir el precio en $\frac{x}{n}$ con cada negativa.

2. El resultado anterior sólo es válido para la distribución uniforme de la valoración del cliente $v$ . Bajo la distribución normal, la respuesta de forma cerrada es factible sólo numéricamente.

3. Cuando $n$ cliente puede ser abordado, cada uno como máximo una vez, el problema de optimización asume una estructura de doble capa: el problema interno de optimización suave está envuelto en la tarea externa de optimización combinatoria. Esto, unido a una estructura de covarianza no trivial en las valoraciones, hace que la solución analítica (y/o manejable) de forma cerrada sea inviable.

4. Un enfoque prometedor para este último caso sería suponer que las valoraciones $v_1,...,v_n$ se distribuyen uniformemente en un paralelotopo y aprovechar la cálculo poliédrico métodos para acelerar los cálculos.

Respuesta detallada

1. Acercarse al mismo cliente como máximo $n$ veces Cuando tratamos con un solo cliente y podemos intentar hasta $n$ veces hasta que se aleja, la solución del problema es directa y y sigue la lógica presentada en la otra respuesta a este post. El beneficio esperado se puede escribir de la siguiente manera:

\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}

donde la convención implícita es que $y_0$ es un límite superior del soporte de $v$ para que $\mathbb{P}( v < y_0) = 1$ .

La solución del problema es, pues, una secuencia $\mathbf{y}:=(y_1,...,y_n)$ maximizando el beneficio esperado. En el caso de la distribución uniforme, $v \sim U[0, x]$ las condiciones de primer orden con respecto a $y_i$ representan un sistema de ecuaciones lineales:

\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}

De la segunda igualdad se desprende que existe un incremento $\delta$ tal que $\forall i=2,..n$ tiene $y_{i} = y_{i-1} - \delta$ , lo que implica que $y_i = y_1 - (i-1)\delta$ . Esto es consistente con la primera y la última igualdad si $\delta = \frac{x}{n}$ y $y_1 = \frac{n-1}{n}x$ según la intuición descrita en el OP.

Observación:

Una vez que pasamos a una suposición más artificiosa sobre la distribución de la valoración del cliente, la respuesta explícita se vuelve imposible de obtener analíticamente. Por ejemplo, en el caso de una distribución normal truncada en el intervalo $[0,x]$ el sistema de condiciones de primer orden se convierte en

\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}

donde $\phi(z) = (2\pi)^{-1/2}\exp(-\frac{z^2}{2})$ es el pdf de la normal estándar y $\Phi(z) = \int_{-\infty}^{z} \phi(\xi)d\xi$ es su cdf.

Se puede ver claramente que la solución analítica de forma cerrada es inviable en este caso.

2. Acercándose como máximo a $n$ diferentes clientes no más de una vez cada

Primero veamos un problema de 2 clientes: para una secuencia de ofertas $y_1, y_2$ y la ordenación (permutación) de los clientes $\sigma(1),\sigma(2)$ los ingresos previstos son los siguientes:

\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}

Ahora bien, no es difícil escribir la fórmula de $n$ clientes:

\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}

donde la última igualdad se cumple si planteamos $y_{n+1}\equiv 0$ .

Aquí, al igual que en la observación anterior, se puede ver que la solución analítica de forma cerrada del problema de optimización suave interior es imposible de obtener bajo el supuesto de normalidad conjunta, ya que las condiciones de primer orden serán ciertamente no polinómicas.

Esto y dado que el problema exterior es combinatorio hace que la solución numérica (algorítmica) del problema sea el camino más prometedor.

Una idea para avanzar:

Cálculo de probabilidades $\mathbb{P}\left(\cap_{j=1}^{i} v_{\sigma(j)}<y_j\right)$ puede resultar más fácil si asumimos una distribución uniforme distorsionada (uniforme sobre un [paralelótopo][3]). No he visto nada parecido en la literatura, pero podría ser un buen compromiso entre la simplicidad de las operaciones con la distribución uniforme y la capacidad de la normal para capturar la estructura de covarianza no trivial.

Más concretamente, se puede suponer que $\mathbf{v}=(v_1,...,v_n)$ se distribuye uniformemente en un $n$ -paralelotopo . En este caso el parámetro de la distribución sería la matriz de $n$ vectores apilados $a_1,...,a_n$ en el marco del paralelótopo, y la densidad incondicional sería la inversa de su volumen, mientras que la condicional pueden calcularse como volúmenes de polítopos convexos formulados de forma sencilla.

Dado un oráculo razonablemente rápido para calcular el óptimo $\mathbf{y}$ la optimización combinatoria para la moderación $n$ puede realizarse entonces mediante una simple comparación de los beneficios esperados de diferentes permutaciones.