Perspectiva técnica: la búsqueda de subastas óptimas de varios artículos | Agosto 2021

Por Constantinos Daskalakis

Comunicaciones de la ACM, agosto de 2021, vol. 64 No. 8, Página 108
10.1145 / 3470440
Comentarios

¿Cuál es la mejor manera de vender uno o varios artículos indivisibles para maximizar los ingresos? ¿Deberían cotizarse por separado, en paquetes o venderse utilizando un mecanismo de venta más complejo? A pesar de su importancia práctica, historia antigua y siglos de estudio científico, estas preguntas han quedado sin respuesta. El desafío al que se enfrentan tanto los vendedores como los científicos es que existen innumerables mecanismos de venta. Si bien estamos acostumbrados a fijar el precio de los artículos en las tiendas, existen muchos otros mecanismos de venta. Escribir un modelo que abarque todos los mecanismos posibles ya es oneroso, y mucho menos optimizarlos.

Por lo tanto, fue una sorpresa cuando, en la década de 1980, los economistas desarrollaron matemáticas que podían señalar la mejor forma de vender un único artículo a uno o varios compradores estratégicos, dada la información de distribución sobre sus valores para el artículo. Cuando estos valores son independientes y están distribuidos de forma idéntica, el óptimo se puede emitir como la subasta familiar de precio ascendente con un precio de reserva, como el que usa eBay, y se convierte en una subasta algo más exótica cuando los valores no se distribuyen de forma idéntica. El trabajo extremadamente influyente y ganador del premio Nobel de Myerson prescribe exactamente cómo configurarlo.

Por desgracia, llevar este programa al multi-artículo El entorno ha acosado a economistas e informáticos. Debe apreciarse que organizar la venta simultánea de múltiples artículos no es un problema inofensivo ni esotérico. Cuando los gobiernos venden espectro de radio, venden simultáneamente varias licencias en una gran subasta. Cuando los intercambios publicitarios venden anuncios de banner en, digamos, el New York Times portada, venden simultáneamente todos los banners para cada impresión. Cuando los minoristas en línea venden varios artículos a compradores competidores, deben organizar sus ventas de manera inteligente. A pesar de la importancia de la configuración de varios elementos, las soluciones óptimas siguen siendo difíciles de alcanzar.

De hecho, un estudio extenso ha revelado que los mecanismos óptimos de varios artículos, incluso para vender dos artículos a un comprador, son tremendamente más complejos que los de un solo artículo. La agrupación y las asignaciones aleatorias son necesarias, y el mecanismo óptimo puede exhibir varias propiedades contrarias a la intuición, como describo en una encuesta reciente.² En el momento de redactar este artículo, solo existen resultados que caracterizan el resultado óptimo de varios elementos comprador único mecanismos.³ Esos resultados, utilizando la teoría del transporte óptimo para caracterizar la estructura del mecanismo óptimo en términos de las condiciones de dominancia estocástica satisfechas por la distribución del valor del comprador, sugieren que no existe un mecanismo óptimo de múltiples elementos que sirva para todos.

En ausencia de una estructura simple y universal en el mecanismo óptimo, existen dos enfoques naturales, que son un buen augurio para la estética de CS y se han perseguido ampliamente. Uno es cambiar la optimización por la simplicidad, como se persigue en un creciente cuerpo de trabajo que ha estado identificando progresivamente mecanismos más simples y aproximadamente óptimos para configuraciones de múltiples compradores de múltiples artículos cada vez más complejas.

Otro enfoque es desarrollar marcos para informática mecanismos óptimos caso por caso, dadas las distribuciones de valor de los compradores. Dichos marcos son útiles tanto para sus productos finales, es decir, los mecanismos que calculan, como también como herramientas exploratorias, para investigar la existencia de estructura en el mecanismo óptimo en una variedad de escenarios de interés. Hay un gran volumen de trabajo sobre este tema, calculando mecanismos óptimos en entornos bastante complejos a través de la programación convexa.²

El siguiente artículo de Dütting et al. aporta una nueva visión muy interesante y con visión de futuro de este desafío computacional, iniciando el uso del aprendizaje profundo para el diseño de mecanismos.

En lugar de tomar las distribuciones de valor como entrada, su marco recibe muestras de esa distribución y entrena una red neuronal que representa el mecanismo para lograr buenos ingresos empíricos. La complejidad de la muestra de los mecanismos óptimos de múltiples elementos ha sido algo estudiada, por lo que tenemos una comprensión razonable de qué configuraciones permiten identificar mecanismos casi óptimos a partir de muchas muestras polinomiales; en particular, se sabe que se necesita cierta independencia condicional entre los valores de los elementos para la eficiencia estadística.¹

En lugar de perseguir garantías de optimalidad para sus mecanismos, nuevamente se desvían del trabajo anterior al buscar garantías de mejor esfuerzo, es decir, los mejores ingresos que puede ofrecer el descenso de gradiente, incluso sin dotar a sus redes neuronales de mucho sesgo inductivo sobre la estructura del óptimo. mecanismo. Además, en lugar de la veracidad exacta, buscan la veracidad aproximada, impuesta a través de formulaciones de entrenamiento mínimo-máximo para sus redes neuronales.

Con esas opciones de diseño, los autores proporcionan un marco computacional flexible, que se adapta fácilmente a distribuciones continuas y es más escalable en algunas dimensiones del problema. A pesar de la falta de un fuerte sesgo inductivo y optimización basada en gradientes, las pruebas empíricas muestran que los mecanismos identificados por su marco logran ingresos cercanos a los óptimos en entornos simples donde los mecanismos óptimos se han identificado de otra manera, mientras que en otros entornos donde no se había identificado el óptimo. calcula mecanismos que son casi óptimos. ¿Qué tan sólidos son estos hallazgos en entornos más amplios? Y, si lo son, ¿cuál sería esa propiedad elusiva de los mecanismos óptimos de múltiples elementos que permite que las arquitecturas relativamente agnósticas los representen y el gradiente descendente los identifique?

Volver arriba

Volver arriba

Volver arriba

La Biblioteca Digital es una publicación de la Asociación de Maquinaria de Computación. Copyright © 2021 ACM, Inc.

entradas no encontradas