Subasta de mochilas

Una subasta de mochilas es una subasta en la que se venden varios artículos idénticos y hay varios postores con diferentes valoraciones interesados ​​en diferentes cantidades de artículos. El objetivo es elegir un subconjunto de los postores con una demanda total, como máximo, del número de artículos y, sujeto a eso, un valor total máximo. Encontrar este conjunto de postores requiere resolver una instancia del problema de la mochila , lo que explica el término "subasta de mochilas".

Un ejemplo de aplicación de una subasta de mochilas es la subasta de tiempo de transmisión entre anunciantes. En este caso, los elementos son las unidades de tiempo (por ejemplo, segundos). Cada anunciante tiene un anuncio de una duración diferente (diferente cantidad de segundos) y un valor diferente para un anuncio. El objetivo es seleccionar un subconjunto de anuncios para publicar en un intervalo de tiempo de una duración específica para maximizar el valor total.

Hay m artículos idénticos y n postores diferentes. Las preferencias de cada postor i están dadas por dos números:

• Demanda s _i : un número entero que determina cuántos artículos desea este postor. El postor necesita precisamente esta cantidad de artículos y no necesita más ni menos artículos.
• Un valor v _i es un número que determina cuánto dinero espera ganar el postor al recibir exactamente s _i artículos.

Un resultado factible de la subasta es un subconjunto W de postores ganadores , de modo que su demanda total sea como máximo m : . El valor de un conjunto W de ganadores es la suma de los valores de los ganadores: . El objetivo es encontrar un conjunto factible de ganadores con un valor total máximo. ${\displaystyle \sum _{i\in W}s_{i}\leq m}$${\displaystyle \sum _{i\in W}v_{i}}$

En el ejemplo del tiempo de transmisión, si hay 5 minutos asignados para anuncios, entonces m = 300 (la cantidad de segundos), n = la cantidad de anunciantes potenciales, s _i = la duración del anuncio de i en segundos, y v i ₌ el dinero que i espera ganar si se transmite su anuncio.

Si las demandas y los valores de todos los postores son conocidos públicamente, entonces el problema puede resolverse mediante cualquier algoritmo para el problema de la mochila . El problema es NP-hard, pero tiene algoritmos de aproximación de factor constante eficientes, así como un FPTAS . En la práctica, normalmente las demandas s _i son conocidas públicamente (por ejemplo, debe conocerse la duración del anuncio de cada anunciante), pero las valoraciones v _i son información privada de los postores. Por lo tanto, el mecanismo de subasta debería incentivar a los postores a revelar sus verdaderas valoraciones.

La subasta VCG es un mecanismo veraz que se puede utilizar para maximizar la suma de valores y al mismo tiempo incentivar a los agentes a revelar sus valores verdaderos. Sin embargo, solo funciona si el resultado maximiza los valores; no funciona con aproximaciones (si el resultado es solo aproximadamente óptimo, entonces VCG ya no es veraz). No se puede encontrar el resultado óptimo en tiempo polinómico a menos que P = NP. Esto plantea la pregunta: ¿existen mecanismos veraces que funcionen en tiempo polinómico y obtengan un resultado aproximadamente óptimo?

Mu'alem y Nisan dieron la primera respuesta afirmativa a esta pregunta: ^[1] demostraron que la combinación de dos algoritmos codiciosos produce un mecanismo de aproximación de dos factores veraz.

Briest, Krysta y Vocking ^[2] mejoraron este resultado al mostrar un FPTAS veraz .

Dutting, Gkatzelis y Roughgarden ^[3] presentaron una subasta veraz de aceptación diferida que alcanza una aproximación de O(log m ) y demostraron que ninguna subasta de aceptación diferida puede lograr una mejor aproximación. Esto muestra una separación entre la clase general de subastas veraces y la subclase de subastas de aceptación diferida.