Subasta combinatoria

Una subasta combinatoria es un tipo de mercado inteligente en el que los participantes pueden pujar por combinaciones de artículos heterogéneos discretos, o "paquetes", en lugar de artículos individuales o cantidades continuas. Estos paquetes también se pueden llamar lotes y la subasta completa es una subasta de lotes múltiples. Las subastas combinatorias son aplicables cuando los postores tienen valoraciones no aditivas en paquetes de artículos, es decir, valoran combinaciones de artículos más o menos que la suma de las valoraciones de los elementos individuales de la combinación.

Las subastas combinatorias simples se han utilizado durante muchos años en las subastas de bienes, donde un procedimiento común es aceptar ofertas por paquetes de artículos. Se han utilizado recientemente para el transporte de camiones, rutas de autobuses, adquisiciones industriales y en la asignación de espectro de radio para comunicaciones inalámbricas. En los últimos años, los equipos de adquisiciones han aplicado subastas combinatorias inversas en la adquisición de bienes y servicios. Esta aplicación a menudo se denomina optimización de abastecimiento. Dado que la adquisición de la construcción a menudo implica negociaciones sobre múltiples componentes, se sugieren subastas inversas combinatorias para reducir los costos en esta industria.

Aunque permiten que los postores sean más expresivos, las subastas combinatorias presentan desafíos tanto computacionales como de teoría de juegos en comparación con las subastas tradicionales. Un ejemplo de un problema computacional es cómo determinar eficientemente la asignación una vez que las ofertas se han presentado al subastador. Esto se llama el problema de determinación del ganador.

El problema de determinación del ganador se puede plantear de la siguiente manera: dado un conjunto de ofertas en una subasta combinatoria, encuentre una asignación de artículos a los postores, incluida la posibilidad de que el subastador se quede con algunos artículos, que maximice los ingresos del subastador. Este problema es difícil para instancias grandes. Específicamente, es NP-hard, lo que significa que se conjetura que no existe un algoritmo de tiempo polinomial que encuentre la asignación óptima. El problema de la subasta combinatoria se puede modelar como un problema de empaquetamiento de conjuntos. Por lo tanto, se han propuesto muchos algoritmos para encontrar soluciones aproximadas para el problema de subasta combinatoria. Por ejemplo, Hsieh (2010) propuso un enfoque de relajación lagrangiana para problemas de subasta inversa combinatoria.

Muchos de estos aspectos de las subastas combinatorias, incluidos algunos ejemplos del mundo real, también se analizan en el libro completo editado por Cramton, Shoham y Steinberg (2006).

Historia

Las subastas combinatorias fueron propuestas por primera vez por Rassenti, Smith y Bulfin (1982), para la asignación de turnos de aterrizaje en aeropuertos. Su artículo presentó muchas ideas clave sobre las subastas combinatorias, incluida la formulación de programación matemática del problema del subastador, la conexión entre el problema de determinación del ganador y el problema del conjunto de paquetes, el problema de la complejidad computacional, el uso de técnicas de economía experimental para probar combinatoria subastas, y consideración de cuestiones de compatibilidad de incentivos y revelación de la demanda en subastas combinatorias.

Subasta de relojes combinatorios

Un caso especial de subasta combinatoria es la subasta de reloj combinatoria (CCA), que combina una subasta de reloj, durante la cual los postores pueden proporcionar sus confirmaciones en respuesta al aumento de los precios, con una subasta de oferta sellada posterior, en la que los postores presentan ofertas en paquete cerrado.. El subastador utiliza las ofertas finales para calcular la mejor asignación de valor y los pagos de Vickrey. Se ha demostrado que las CCA son propensas a la posibilidad de aumentar el costo de los rivales.