Mecanismo óptimo bayesiano

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

Un ejemplo típico es el de un vendedor que desea vender artículos a compradores potenciales. El vendedor busca fijar el precio de los artículos de manera que maximice su ganancia. Los precios óptimos dependen de la cantidad que cada comprador esté dispuesto a pagar por cada artículo. El vendedor desconoce estas cantidades, pero supone que provienen de una distribución de probabilidad conocida . La expresión "diseño bayesiano de mecanismos óptimos" 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 mecanismos sin información previa , que no asume ninguna distribución de probabilidad previa).
• Óptimo significa que queremos maximizar los ingresos esperados del subastador, donde la expectativa supera la aleatoriedad en las valoraciones de los agentes.
• Por mecanismo queremos diseñar reglas que definan un mecanismo veraz , en el que cada agente tenga un incentivo para informar sobre su verdadero valor.

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

Esta subasta no es óptima. Es posible obtener una mayor ganancia estableciendo un precio de reserva . La subasta de Vickrey con un precio de reserva de 1/2 alcanza una ganancia esperada de 5/12, que en este caso es óptima. ^{[ 2 ]}

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

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

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

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

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

El superávit 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 la mayor ganancia posible. Si cada agente ganador${\displaystyle i}$paga exactamente su valor${\displaystyle v_{i}}$Entonces, la ganancia del subastador es exactamente el excedente.${\displaystyle S(x)}$Esto significa que el subastador se queda con todo el excedente y no deja ninguna utilidad para los agentes.

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

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

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

Cabe señalar que la valoración virtual suele ser inferior a 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.${\displaystyle x}$como:

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

Cabe señalar que el superávit virtual suele ser menor que el superávit 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 esperanza se calcula teniendo en cuenta la aleatoriedad en las valoraciones de los agentes).

Este teorema sugiere el siguiente mecanismo:

• Pregúntale a cada agente${\displaystyle i}$para informar su valoración${\displaystyle v_{i}}$
• Basándonos en la respuesta y las funciones de distribución conocidas${\displaystyle F_{i},f_{i}}$, calcular${\displaystyle w_{i}}$.
• Calcula 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.${\displaystyle w_{i}}$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 de nuevo al espacio de valoraciones reales. Por lo tanto, el paso final del mecanismo es:

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

El diseño de mecanismos óptimos bayesianos requiere conocer las distribuciones de las que se extraen las valoraciones de los agentes. Este requisito no siempre es factible. Existen otras alternativas:

• Cuando se desconoce la distribución, se puede utilizar un mecanismo independiente de la distribución previa .
• Cuando ni siquiera se puede asumir que los agentes provienen de alguna distribución de probabilidad, se debe utilizar un mecanismo que no requiera información previa .