Mecanismo bayesiano óptimo

Un mecanismo bayesiano-óptimo (BOM) es un mecanismo en el que el diseñador no conoce las valoraciones de los agentes para los que está diseñado el mecanismo, pero el diseñador 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 fijar el precio de los artículos de forma que maximice sus beneficios. 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 (a diferencia del diseño de mecanismo sin prioridad , que no supone ninguna distribución de probabilidad previa).
• Óptimo significa que queremos maximizar los ingresos esperados del subastador, donde la expectativa está sobre 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 valor real.

Ejemplo

Hay un artículo a la venta. Hay dos compradores potenciales. La valoración de cada comprador se extrae 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 oferta sellada a primer precio es un mecanismo no veraz y su beneficio esperado es el mismo ).

Esta subasta no es óptima. Es posible obtener una ganancia mayor si se establece un precio de reserva . La subasta Vickrey con un precio de reserva de 1/2 logra una ganancia esperada de 5/12, que en este caso es óptima. ^[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 puede tener un costo 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 máximo beneficio posible. Si cada agente ganador paga exactamente su valor , entonces el beneficio del subastador es 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)}$

No se puede alcanzar esta máxima ganancia porque si el subastador intenta cobrar a cada agente ganador su valor , los agentes mentirán y reportarán un valor menor para pagar menos. El mecanismo de Myerson viene a solucionar este problema. ${\displaystyle v_{i}}$

El mecanismo de Myerson

Roger Myerson diseñó un mecanismo bayesiano óptimo 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)}$

Téngase 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.

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

Este teorema sugiere el siguiente mecanismo:

• Pídele 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, debemos especificar el precio que cada agente ganador debe pagar. Una forma de calcular el precio es utilizar el mecanismo VCG sobre las valoraciones virtuales . El mecanismo VCG devuelve tanto una asignación que maximiza el excedente virtual como un vector de precios. Como el vector de precios corresponde a las valoraciones virtuales, debemos convertirlo nuevamente al espacio de valoraciones reales. Por lo tanto, 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 veraz siempre que la regla de asignación satisfaga la propiedad de monotonía débil , es decir, la función de asignación es débilmente creciente en las valoraciones de los agentes. La regla de asignación VCG es de hecho débilmente creciente en las valoraciones, pero la usamos con las valoraciones virtuales en lugar de las valoraciones reales. Por lo tanto, el mecanismo de Myerson es veraz si las valoraciones virtuales son débilmente crecientes en las valoraciones reales. Es decir, si para todo : es una función débilmente creciente de . ${\displaystyle i}$ ${\displaystyle w_{i}}$ ${\displaystyle v_{i}}$

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

El mecanismo de Myerson puede aplicarse en diversos contextos. 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 es débilmente creciente. En este caso, el mecanismo VCG se reduce a la subasta Vickrey : asigna el artículo al agente con la mayor valoración (la oferta más alta). Pero el mecanismo de Myerson usa VCG con las valoraciones virtuales, que pueden ser negativas. Por lo tanto, el mecanismo de Myerson, en este caso, se reduce a la subasta Vickrey con precio de reserva . Asigna el artículo al agente con la mayor valoración, 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 bienes digitales

En una subasta de bienes digitales , tenemos un suministro ilimitado de artículos idénticos. Cada agente quiere como máximo un artículo. Las valoraciones de los agentes para el 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 mecanismos bayesianos óptimos requiere conocer las distribuciones de las que se extraen las valoraciones de los agentes. Este requisito no siempre es factible. Existen otras alternativas:

• Cuando no se conoce la distribución, se puede utilizar un mecanismo independiente del anterior .
• Cuando ni siquiera puede suponerse que los agentes provienen de alguna distribución de probabilidad, se debe utilizar un mecanismo libre de valores anteriores .

Referencias

1. Vazirani, Vijay V .; Nisán, Noam ; Jardín rugoso, 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". stackexchange .
3. Myerson, Roger B. (1981). "Diseño óptimo de subastas". Matemáticas de la investigación de operaciones . 6 (1): 58–73. doi :10.1287/moor.6.1.58.