Mecanismo bayesiano óptimo

Un mecanismo óptimo bayesiano (BOM) es un mecanismo en el que el diseñador no conoce las valoraciones de los agentes para quienes está diseñado el mecanismo, pero sabe que son variables aleatorias y conoce la distribución de probabilidad de estas variables.

Una aplicación típica es la de un vendedor que quiere vender algunos artículos a compradores potenciales. El vendedor quiere poner precio a los artículos de una manera que maximice sus ganancias. Los precios óptimos dependen de la cantidad que cada comprador esté dispuesto a pagar por cada artículo. El vendedor no conoce estas cantidades, pero supone que se extraen de una determinada distribución de probabilidad conocida . La frase "diseño de mecanismo óptimo bayesiano" tiene el siguiente significado: ^{[1] : 335–338}

• Bayesiano significa que conocemos la distribución de probabilidad de la que se extraen las valoraciones de los agentes (en contraste con el diseño de mecanismo libre de antecedentes , que no asume ninguna distribución de probabilidad previa).
• Óptimo significa que queremos maximizar los ingresos esperados del subastador, donde la expectativa está por encima de la aleatoriedad en las valoraciones de los agentes.
• Mecanismo significa que queremos diseñar reglas que definan un mecanismo veraz , en el que cada agente tenga un incentivo para informar su verdadero valor.

Ejemplo

Hay un artículo a la venta. Hay dos compradores potenciales. La valoración de cada comprador se obtiene iid de la distribución uniforme en [0,1].

La subasta de Vickrey es un mecanismo veraz y su beneficio esperado, en este caso, es 1/3 (la subasta de primer precio sobre sobre cerrado es un mecanismo no veraz y su beneficio esperado es el mismo ).

Esta subasta no es óptima. Es posible obtener un mayor beneficio fijando un precio de reserva . La subasta de Vickrey con un precio de reserva de 1/2 consigue un beneficio esperado de 5/12, que en este caso es óptimo. ^[2]

Notación

Suponemos que los agentes tienen funciones de utilidad de un solo parámetro , como una subasta de un solo artículo. Cada agente tiene un valor que representa el "valor ganador" del agente (por ejemplo, la valoración del artículo por parte del agente). No conocemos estos valores, pero sí sabemos que cada uno se extrae de una determinada distribución de probabilidad. Denotamos por la función de distribución acumulativa : ${\displaystyle i}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle F_{i}}$

${\displaystyle F_{i}(z)=\Pr[v_{i}<z]}$

y por la función de distribución de probabilidad : ${\displaystyle f_{i}}$

${\displaystyle f_{i}(z)=F_{i}'(z)}$

Una asignación es un vector tal que para cada , es 1 si el agente gana y 0 en caso contrario. Cada asignación podría tener un coste para el subastador . ${\displaystyle x}$ ${\displaystyle i}$ ${\displaystyle x_{i}}$ ${\displaystyle i}$ ${\displaystyle c(x)}$

El excedente de una asignación se define como:

${\displaystyle S(x)=\sum _{i}x_{i}\cdot v_{i}-c(x)}$

Esta es la ganancia total de los agentes, menos el costo del subastador.

El excedente es el mayor beneficio posible. Si cada agente ganador paga exactamente su valor , entonces el beneficio del subastador será exactamente el excedente ; esto significa que el subastador se queda con todo el excedente y deja cero utilidad a los agentes. ${\displaystyle i}$ ${\displaystyle v_{i}}$ ${\displaystyle S(x)}$

Este beneficio máximo no se puede lograr porque si el subastador intenta cobrar a cada agente ganador su valor , los agentes mentirán y reportarán un valor más bajo para pagar menos. El mecanismo Myerson viene a solucionar este problema. ${\displaystyle v_{i}}$

El mecanismo Myerson

Roger Myerson diseñó un mecanismo óptimo bayesiano para agentes de utilidad de un solo parámetro . El truco clave del mecanismo de Myerson es utilizar valoraciones virtuales . Para cada agente , defina su valoración virtual como: ${\displaystyle i}$

${\displaystyle w_{i}(v_{i})=v_{i}-{\frac {1-F_{i}(v_{i})}{f_{i}(v_{i})}}}$

Tenga en cuenta que la valoración virtual suele ser menor que la valoración real. Incluso es posible que la valoración virtual sea negativa mientras que la valoración real sea positiva.

Defina el excedente virtual de una asignación como: ${\displaystyle x}$

${\displaystyle S^{*}(x)=\sum _{i}x_{i}\cdot w_{i}(v_{i})-c(x)}$

Tenga en cuenta que el excedente virtual suele ser menor que el excedente real.

Un teorema clave de Myerson dice que: ^{[1] : 336  [3]}

El beneficio esperado de cualquier mecanismo veraz es igual a su excedente virtual esperado.

(la expectativa se asume sobre la aleatoriedad en las valoraciones de los agentes).

Este teorema sugiere el siguiente mecanismo:

• Pide a cada agente que informe su valoración ${\displaystyle i}$ ${\displaystyle v_{i}}$
• Con base en la respuesta y las funciones de distribución conocidas , calcule . ${\displaystyle F_{i},f_{i}}$ ${\displaystyle w_{i}}$
• Calcule una asignación x que maximice el excedente virtual . ${\displaystyle S^{*}(x)}$

Para completar la descripción del mecanismo conviene especificar el precio que debe pagar cada agente ganador. Una forma de calcular el precio es utilizar el mecanismo VCG en las valoraciones virtuales . El mecanismo VCG devuelve tanto una asignación que maximiza el excedente virtual como un vector de precios. Dado que el vector de precios corresponde a las valoraciones virtuales, debemos convertirlo nuevamente al espacio de valoraciones reales. Entonces el paso final del mecanismo es: ${\displaystyle w_{i}}$

• Tome de cada agente ganador el precio , donde es el precio determinado por el mecanismo VCG. ${\displaystyle i}$ ${\displaystyle p_{i}=w_{i}^{-1}(p'_{i})}$ ${\displaystyle p'_{i}}$

Veracidad

El mecanismo de Myerson es verdadero siempre que la regla de asignación satisface la propiedad de monotonicidad débil , es decir, la función de asignación aumenta débilmente en las valoraciones de los agentes. De hecho, la regla de asignación de VCG aumenta débilmente en las valoraciones, pero la utilizamos con las valoraciones virtuales en lugar de con las valoraciones reales. Por lo tanto, el mecanismo de Myerson es veraz si las valoraciones virtuales aumentan débilmente en las valoraciones reales. Es decir, si para todos : es una función débilmente creciente de . ${\displaystyle i}$ ${\displaystyle w_{i}}$ ${\displaystyle v_{i}}$

Si no es una función que aumenta débilmente , entonces se puede utilizar el planchado Myerson . ${\displaystyle w_{i}}$ ${\displaystyle v_{i}}$

El mecanismo de Myerson se puede aplicar en varios entornos. A continuación se presentan dos ejemplos.

Subasta de un solo artículo

Supongamos que queremos vender un solo artículo y sabemos que las valoraciones de todos los agentes provienen de la misma distribución de probabilidad, con funciones . Entonces, todos los postores tienen la misma función de valoración virtual . Supongamos que esta función aumenta débilmente. En este caso, el mecanismo VCG se reduce a la subasta de Vickrey : asigna el artículo al agente con la mayor valoración (oferta más alta). Pero el mecanismo de Myerson utiliza VCG con valoraciones virtuales, que pueden ser negativas. Por tanto, el mecanismo de Myerson, en este caso, se reduce a la subasta de Vickrey con precio de reserva . Asigna el artículo al agente con la valoración más grande, pero solo si su valoración virtual es al menos 0 . Esto significa que el precio de reserva del mecanismo de Myerson es exactamente: ${\displaystyle F,f}$ ${\displaystyle w}$

${\displaystyle w^{-1}(0)}$

Entonces, si conocemos las funciones de distribución de probabilidad , podemos calcular la función y, a partir de ella, encontrar el precio de reserva óptimo. ${\displaystyle F,f}$ ${\displaystyle w}$

Subasta de productos digitales

En una subasta de productos digitales , tenemos un suministro ilimitado de artículos idénticos. Cada agente quiere como máximo un artículo. Las valoraciones de los agentes al artículo provienen de la misma distribución de probabilidad, con funciones y función de valoración virtual . El mecanismo VCG asigna un artículo a cada agente con valoración virtual no negativa y cobra el precio mínimo ganador, que es: ${\displaystyle F,f}$ ${\displaystyle w}$

${\displaystyle w^{-1}(0)}$

Esto equivale exactamente al precio de venta óptimo: el precio que maximiza el valor esperado de la ganancia del vendedor, dada la distribución de valoraciones:

${\displaystyle \arg \max _{z}{z\cdot (1-F(z))}}$

Alternativas

El diseño de un mecanismo bayesiano óptimo requiere conocer las distribuciones de las que se extraen las valoraciones de los agentes. Este requisito no siempre es factible. Hay algunas otras alternativas:

• Cuando no se conoce la distribución, se puede utilizar un mecanismo independiente de prioridades .
• Cuando ni siquiera se puede suponer que los agentes provienen de alguna distribución de probabilidad, se debe utilizar un mecanismo libre de antecedentes .

Referencias

1. Vazirani, Vijay V .; Nisán, Noam ; Jardín áspero, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
2. Sergio Parreiras. "Ingresos esperados obtenidos por la subasta de Vickery con precio de reserva 1/2". intercambio de pila .
3. Myerson, Roger B. (1981). "Diseño óptimo de subasta". Matemáticas de la Investigación de Operaciones . 6 (1): 58–73. doi :10.1287/moor.6.1.58.