Mecanismo independiente del anterior

Un mecanismo independiente de lo anterior (PIM) es un mecanismo en el que el diseñador sabe que las valoraciones de los agentes se extraen de alguna distribución de probabilidad , pero no conoce la distribución.

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 estos valores, pero supone que son variables aleatorias con una distribución de probabilidad desconocida.

Un mecanismo de subasta por lo general implica un proceso de muestreo aleatorio . El vendedor toma muestras de algunas valoraciones de la distribución desconocida y, basándose en las muestras, construye una subasta que produce ganancias aproximadamente óptimas. La pregunta principal de investigación en el diseño de un mecanismo de subasta por medio de subasta es: ¿cuál es la complejidad de la muestra del mecanismo? Es decir, ¿cuántos agentes necesita muestrear para lograr una aproximación razonable del bienestar óptimo?

Subastas de artículos individuales

Los resultados de ^[1] implican varios límites en la complejidad de la muestra de la maximización de ingresos de las subastas de un solo artículo: ^[2]

Para una aproximación del ingreso esperado óptimo, la complejidad de la muestra es : una sola muestra es suficiente. Esto es cierto incluso cuando los postores no son iid ^[3] ${\estilo de visualización 1/4}$ ${\estilo de visualización 1}$
Para una aproximación del ingreso esperado óptimo, cuando los postores son iid O cuando hay un suministro ilimitado de artículos (bienes digitales), la complejidad de la muestra es cuando las distribuciones de los agentes tienen una tasa de riesgo monótona , y cuando las distribuciones de los agentes son regulares pero no tienen una tasa de riesgo monótona. $1-\épsilon$ $O(1/\epsilon ^{2})$ $O(1/\epsilon ^{3})$

La situación se complica cuando los agentes no son iid (el valor de cada agente se extrae de una distribución regular diferente) y los bienes tienen una oferta limitada. Cuando los agentes provienen de distribuciones diferentes, la complejidad muestral de la aproximación del ingreso esperado óptimo en subastas de un solo artículo es: ^[2] ${\estilo de visualización k}$ $1-\épsilon$

como máximo , utilizando una variante de la subasta empírica de Myerson. $O({k^{10} \sobre \epsilon ^{7}}\ln ^{3}{k \sobre \epsilon })$
al menos (para valoraciones regulares de tasa de riesgo monótona) y al menos (para valoraciones regulares arbitrarias). $\Omega ({k \sobre {\sqrt {\epsilon \ln k}}})$ $\Omega ({k \sobre \épsilon })$

Agentes monoparamétricos

^[4] analizan subastas arbitrarias con agentes de utilidad de un solo parámetro (no solo subastas de un solo artículo) y mecanismos de subasta arbitrarios (no solo subastas específicas). Con base en resultados conocidos sobre la complejidad de la muestra , muestran que la cantidad de muestras requeridas para aproximarse a la subasta de máximos ingresos de una clase dada de subastas es:

O{\bigg (}({H sobre \epsilon })^{2}(D\ln({H sobre \epsilon })+\ln({1 sobre \delta })){\bigg )}

dónde:

Las valoraciones de los agentes están limitadas en , ${\estilo de visualización [1,H]}$
La dimensión pseudo-VC de la clase de subastas es como máximo , ${\estilo de visualización D}$
El factor de aproximación requerido es , $1-\épsilon$
La probabilidad de éxito requerida es . ${\estilo de visualización 1-\delta}$

En particular, consideran una clase de subastas simples llamadas subastas de nivel 1 : subastas con precios de reserva (una subasta de Vickrey con un precio de reserva único es una subasta de nivel 1). Demuestran que la pseudo-dimensión VC de esta clase es , lo que se traduce inmediatamente en un límite para su error de generalización y complejidad de muestra. También prueban límites para el error de representación de esta clase de subastas. ${\estilo de visualización t}$ ${\estilo de visualización t}$ $O(nt\ln(nt))$

Agentes multiparamétricos

Devanur et al. estudian un mercado con diferentes tipos de artículos y agentes de demanda unitaria . ^[5]

Chawla et al. estudian los PIM para el problema de minimización de la longitud de onda . ^[6]

Hsu et al. estudian un mercado con distintos tipos de artículos. Los suministros son fijos. Los compradores pueden comprar paquetes de artículos y tienen diferentes valoraciones de los paquetes. Demuestran que, si se seleccionan compradores de forma independiente de alguna distribución desconocida, se calcula un vector de precios óptimo y luego se aplica este vector de precios a una nueva muestra de compradores, entonces el bienestar social es aproximadamente óptimo. La relación competitiva implícita en su Teorema 6.3 es, con probabilidad , al menos ${\estilo de visualización n}$ ${\estilo de visualización n}$ ${\estilo de visualización 1-\delta}$

1-O{\bigg (}{\sqrt {h^{3}n^{0.5}m^{4}\ln ^{2}m\ln ^{2}{1 \sobre \delta } \sobre {\text{Bienestar óptimo}}}}{\bigg )}

. ^[7]

Alternativas

Los mecanismos independientes previos (PIM) deben contrastarse con otros dos tipos de mecanismos:

Los mecanismos bayesianos óptimos (BOM) suponen que las valoraciones de los agentes se extraen de una distribución de probabilidad conocida . El mecanismo se adapta a los parámetros de esta distribución (por ejemplo, su valor medio o mediano).
Los mecanismos sin prioridad (PFM) no presuponen que las valoraciones de los agentes se extraigan de una distribución de probabilidad (conocida o desconocida). El objetivo del vendedor es diseñar una subasta que produzca una ganancia razonable incluso en los peores escenarios.

Desde el punto de vista del diseñador, BOM es el más fácil, luego PIM y luego PFM. Las garantías de aproximación de BOM y PIM se dan en la expectativa, mientras que las de PFM se dan en el peor de los casos.

Véase también

Referencias

^ Dhangwatnotai, Peerapong; Roughgarden, Tim; Yan, Qiqi (2015). "Maximización de ingresos con una sola muestra". Juegos y comportamiento económico . 91 : 318–333. doi : 10.1016/j.geb.2014.03.011 .
^ ab Cole, Richard; Roughgarden, Tim (2014). "La complejidad de la muestra en la maximización de los ingresos". Actas del 46.º Simposio anual de la ACM sobre teoría de la computación - STOC '14 . pág. 243. arXiv : 1502.00963 . doi :10.1145/2591796.2591867. ISBN 9781450327107.
^ Hartline, Jason D.; Roughgarden, Tim (2009). "Mecanismos simples versus óptimos". Actas de la décima conferencia de la ACM sobre comercio electrónico - EC '09 . p. 225. doi :10.1145/1566374.1566407. ISBN 9781605584584.
^ Sobre la pseudodimensión de las subastas casi óptimas. NIPS. 2015. arXiv : 1506.03684 . Código Bibliográfico :2015arXiv150603684M.
^ Devanur, Nikhil; Hartline, Jason; Karlin, Anna; Nguyen, Thach (2011). "Diseño de mecanismos multiparamétricos independientes de la prioridad". Internet and Network Economics . Apuntes de clase en informática. Vol. 7090. pág. 122. CiteSeerX 10.1.1.259.3224 . doi :10.1007/978-3-642-25510-6_11. ISBN 978-3-642-25509-0.
^ Chawla, Shuchi ; Hartline, Jason D.; Malec, David; Sivan, Balasubramanian (2013). "Mecanismos independientes de la prioridad para la planificación". Actas del 45.º simposio anual de la ACM sobre Simposio sobre teoría de la computación - STOC '13 . pág. 51. arXiv : 1305.0597 . doi :10.1145/2488608.2488616. ISBN 9781450320290.
^ Hsu, Justin; Morgenstern, Jamie; Rogers, Ryan; Roth, Aaron; Vohra, Rakesh (2016). "¿Los precios coordinan los mercados?". Actas del 48.º Simposio anual ACM SIGACT sobre teoría de la computación - STOC 2016. pág. 440. arXiv : 1511.00925 . doi :10.1145/2897518.2897559. ISBN . 9781450341325.