Un mecanismo óptimo bayesiano (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 sabe que son variables aleatorias y conoce la distribución de probabilidad de estas variables.
Una aplicación típica es un vendedor que quiere vender algunos artículos a compradores potenciales. El vendedor quiere fijar el precio de 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 cierta 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 a partir de la cual se extraen las valoraciones de los agentes (en contraste con el diseño de mecanismos sin previo , 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 tiene 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 dibuja iid partir 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 [ cita requerida ] (la subasta de puja cerrada al primer precio es un mecanismo no veraz y su beneficio esperado es el mismo ).
Esta subasta no es óptima. Es posible obtener un mayor beneficio estableciendo un precio de reserva . La subasta de Vickrey con un precio de reserva de 1/2 logra una ganancia esperada de 5/12 [ cita requerida ] , que en este caso es óptima [ cita requerida ] .
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 sabemos que cadase extrae iid de una cierta distribución de probabilidad. Denotamos porla función de distribución acumulativa :
y por la función de distribución de probabilidad :
Una asignación es un vector, de modo que para cada , es 1 si el agente gana y 0 en caso contrario. Cada asignación puede tener un costo para el subastador,.
El excedente de una asignación se define como:
Esta es la ganancia total de los agentes, menos el costo del subastador.
El excedente es la mayor ganancia posible. Si cada agente ganador paga exactamente su valor , entonces la ganancia del subastador es exactamente el excedente ; esto significa que el subastador se lleva todo el excedente y no deja ninguna utilidad a los agentes.
Esta ganancia máxima no se puede lograr porque si el subastador intentará 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 abordar este problema.
El mecanismo de Myerson
Roger Myerson diseñó un mecanismo óptimo bayesiano para agentes de servicios públicos de un solo parámetro . El truco clave del mecanismo de Myerson es utilizar valoraciones virtuales . Para cada agente, define su valoración virtual como:
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 x como:
Tenga en cuenta que el superávit virtual suele ser menor que el superávit real.
Un teorema clave de Myerson dice que: [1] : 336 [2]
- La ganancia esperada de cualquier mecanismo veraz es igual a su superávit virtual esperado.
(se toma la expectativa sobre la aleatoriedad en las valoraciones de los agentes).
Este teorema sugiere el siguiente mecanismo:
- Pregunte a cada agente para informar su valoración
- Basado en la respuesta y las funciones de distribución conocidas , calcular .
- Calcule una asignación x que maximice el excedente virtual .
Para completar la descripción del mecanismo, debemos 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 una asignación que maximiza el excedente virtual y un vector de precios. Dado que el vector de precios corresponde a las valoraciones virtuales, debemos convertirlo de nuevo al espacio de valoración real. Entonces, el paso final del mecanismo es:
- Toma de cada agente ganador el precio , dónde es el precio determinado por el mecanismo VCG.
Veracidad
El mecanismo de Myerson es veraz 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 está aumentando débilmente en las valoraciones, pero la usamos con las valoraciones virtuales en lugar de las valoraciones reales. Por lo tanto, el mecanismo de Myerson es verdadero si las valoraciones virtuales aumentan débilmente en las valoraciones reales. Es decir, si por todos: es una función débilmente creciente de .
Si no es una función de crecimiento débil de , entonces se puede utilizar el planchado Myerson .
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,. Suponga que esta función aumenta débilmente. En este caso, el mecanismo de 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 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 de 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:
Entonces, si conocemos las funciones de distribución de probabilidad , podemos calcular la función y, a partir de él, encontrar el precio de reserva óptimo.
Subasta de bienes 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 de VCG asigna un artículo a cada agente con valoración virtual no negativa y cobra el precio mínimo ganador, que es:
Esto es exactamente igual al precio de venta óptimo, el precio que maximiza el valor esperado de la ganancia del vendedor, dada la distribución de valoraciones:
Alternativas
El diseño del mecanismo óptimo bayesiano 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 a priori .
- Cuando ni siquiera se puede suponer que los agentes se extraen de alguna distribución de probabilidad, se debe utilizar un mecanismo sin a priori .
Referencias
- ↑ a b Vazirani, Vijay V .; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
- ^ Myerson, Roger B. (1981). "Diseño de subasta óptimo". Matemáticas de la investigación operativa . 6 : 58. doi : 10.1287 / moor.6.1.58 .