Mecanismo de muestreo aleatorio

Cuando el mercado es grande, se puede utilizar el siguiente esquema general: ^{[ 1 ] : 341–344}

1. Se solicita a los compradores que revelen sus valoraciones.
2. Los compradores se dividen en dos submercados,${\displaystyle M_{L}}$("izquierda") y${\displaystyle M_{R}}$("derecha"), utilizando un muestreo aleatorio simple : cada comprador se dirige a uno de los lados lanzando una moneda justa .
3. En cada submercado${\displaystyle M_{s}}$, una función de distribución empírica${\displaystyle F_{s}}$se calcula.
4. El mecanismo bayesiano óptimo (mecanismo de Myerson) se aplica en el submercado.${\displaystyle M_{R}}$con distribución${\displaystyle F_{L}}$y en${\displaystyle M_{L}}$con${\displaystyle F_{R}}$.

Este método se denomina "Myerson empírico de muestreo aleatorio" (RSEM, por sus siglas en inglés).

La declaración de cada comprador no afecta al precio que debe pagar; el precio lo determinan los compradores del otro submercado. Por lo tanto, es una estrategia dominante para los compradores revelar su verdadera valoración. En otras palabras, se trata de un mecanismo veraz .

Intuitivamente, según la ley de los grandes números , si el mercado es suficientemente grande, las distribuciones empíricas serán suficientemente similares a las distribuciones reales, por lo que cabe esperar que el RSEM alcance un beneficio casi óptimo. Sin embargo, esto no es necesariamente cierto en todos los casos. Se ha demostrado que lo es en algunos casos especiales.

El caso más simple es la subasta de bienes digitales . Allí, el paso 4 es simple y consiste únicamente en calcular el precio óptimo en cada submercado. El precio óptimo en${\displaystyle M_{L}}$se aplica a${\displaystyle M_{R}}$y viceversa. Por lo tanto, el mecanismo se denomina "Precio Óptimo por Muestreo Aleatorio" (RSOP). Este caso es sencillo porque siempre calcula asignaciones factibles. Es decir, siempre es posible aplicar el precio calculado en un lado al otro. Esto no ocurre necesariamente con los bienes físicos.

Incluso en una subasta de bienes digitales, RSOP no necesariamente converge a la ganancia óptima. Converge solo bajo el supuesto de valoraciones limitadas : para cada comprador, la valoración del artículo está entre 1 y${\displaystyle h}$, dónde${\displaystyle h}$es alguna constante. La tasa de convergencia de RSOP a la optimalidad depende de${\displaystyle h}$. La tasa de convergencia también depende del número de posibles "ofertas" consideradas por el mecanismo. ^{[ 2 ]}

Para entender qué es una "oferta", considere una subasta de bienes digitales en la que se sabe que las valoraciones de los compradores, en dólares, están limitadas a${\displaystyle [1,h]}$. Si el mecanismo utiliza solo precios en dólares enteros, entonces solo hay${\displaystyle h}$posibles ofertas.

En general, el problema de optimización puede implicar mucho más que un solo precio. Por ejemplo, podríamos querer vender varios productos digitales diferentes, cada uno con un precio distinto. Entonces, en lugar de un "precio", hablamos de una "oferta". Suponemos que existe un conjunto global.${\displaystyle G}$de posibles ofertas. Por cada oferta${\displaystyle g\in G}$y agente${\displaystyle i}$,${\displaystyle g(i)}$es la cantidad que agente${\displaystyle i}$paga cuando se le presenta la oferta${\displaystyle g}$. En el ejemplo de los bienes digitales,${\displaystyle G}$es el conjunto de precios posibles. Para cada precio posible${\displaystyle p}$, hay una función${\displaystyle g_{p}}$de tal manera que${\displaystyle g_{p}(i)}$es o 0 (si${\displaystyle v_{i}<p}$) o${\displaystyle p}$(si${\displaystyle v_{i}\geq p}$).

Para cada conjunto${\displaystyle S}$de agentes, el beneficio del mecanismo por presentar la oferta${\displaystyle g}$a los agentes en${\displaystyle S}$es:

${\displaystyle g(S):=\sum _{i\in S}g(i)}$

y el beneficio óptimo del mecanismo es:

${\displaystyle OPT_{G}(S):=\max _{g\in G}g(S)}$

El RSM calcula, para cada submercado${\displaystyle M_{s}}$una oferta óptima${\displaystyle g_{s}}$, calculado de la siguiente manera:

${\displaystyle g_{s}:=\arg \max _{g\in G}g(M_{s})}$

La oferta${\displaystyle g_{L}}$se aplica a los compradores en${\displaystyle M_{R}}$, es decir: cada comprador${\displaystyle i\in M_{R}}$¿Quién dijo eso?${\displaystyle g_{L}(i)>0}$recibe la asignación ofrecida y paga${\displaystyle g_{L}(i)}$; cada comprador en${\displaystyle M_{R}}$¿Quién dijo eso?${\displaystyle g_{L}(i)=0}$No reciba ni pague nada. La oferta${\displaystyle g_{R}}$se aplica a los compradores en${\displaystyle M_{L}}$De manera similar.

El oráculo de ganancias es otro esquema RSM que se puede utilizar en grandes mercados. ^{[ 3 ]} Es útil cuando no tenemos acceso directo a las valoraciones de los agentes (por ejemplo, debido a razones de privacidad). Todo lo que podemos hacer es realizar una subasta y observar su ganancia esperada. En una subasta de un solo artículo, donde hay${\displaystyle n}$postores, y para cada postor hay como máximo${\displaystyle K}$Con valores posibles (seleccionados al azar con probabilidades desconocidas), la subasta de ingresos máximos se puede aprender utilizando:

${\displaystyle O(n^{2}K^{2})}$

llamadas al oráculo-ganancias.

La primera investigación en este contexto fue para una subasta de bienes digitales con utilidad de un solo parámetro . ^{[ 4 ]}

Para el mecanismo de precio óptimo por muestreo aleatorio, se han calculado varias aproximaciones cada vez mejores:

• Por ^{[ 5 ],} la ganancia del mecanismo es al menos 1/7600 de la óptima.
• Según ^{[ 6 ],} el beneficio del mecanismo es al menos 1/15 del óptimo.
• Por ^{[ 7 ]} el beneficio del mecanismo es al menos 1/4,68 del óptimo, y en la mayoría de los casos 1/4 del óptimo, lo cual es ajustado.

Cuando las valoraciones de los agentes satisfacen alguna condición de regularidad técnica (llamada tasa de riesgo monótona ), es posible alcanzar una aproximación de factor constante a la subasta de beneficio máximo utilizando el siguiente mecanismo: ^{[ 8 ]}

• Seleccione un único agente aleatorio y consulte su valor (se supone que los agentes tienen una utilidad de un solo parámetro ).
• En los demás agentes, ejecute una subasta VCG con un precio de reserva determinado por el agente muestreado.

El beneficio de este mecanismo es al menos${\displaystyle {n-1 \over 4n}}$, dónde${\displaystyle n}$es el número de agentes. Este valor es 1/8 cuando hay dos agentes y tiende a 1/4 a medida que aumenta el número de agentes. Este esquema se puede generalizar para manejar restricciones en los subconjuntos de agentes que pueden ganar simultáneamente (por ejemplo, solo hay un número finito de artículos). También puede manejar agentes con diferentes atributos (por ejemplo, postores jóvenes frente a postores mayores).