Subasta combinatoria

Parte de una serie sobre
Subastas
Tipos
Todo pago Chino Tarifa de licitación Dólar Ámsterdam Anglo-holandés Trueque doble Mejor/no mejor brasileño Calcuta Vela Ofertas con cuadro de clic Combinacional Valor común Aceptación diferida Precio discriminatorio Doble Holandés Inglés Adelante Francés Primer precio generalizado Segundo precio generalizado japonés Mochila Multi-atributo Multiunidad Sin reserva Rango Contrarrestar escocés Sellado de primer precio Ascendente simultáneo Precio único Semáforo Precio uniforme Oferta única Valor de los ingresos Vickrey Vickrey-Clarke-Groves Walrasian Yankee
Bidding
Shading Calor licitantis Cancellation hunt Jump Rigging Sniping Suicide Tacit collusion
Contexts
Algorithms Autos Art Charity Children Players Domain names Flowers Loans Scam Slaves Spectrum Stamps Virginity Wine Wives
Theory
Digital goods Price of anarchy Revenue equivalence Winner's curse
Online
Ebidding Private electronic market Software
v t e

Una subasta combinatoria es un tipo de mercado inteligente en el que los participantes pueden realizar ofertas sobre combinaciones de artículos heterogéneos discretos, o "paquetes", en lugar de artículos individuales o cantidades continuas. Estos paquetes también pueden denominarse lotes y la subasta completa una subasta de lotes múltiples . ^[1] Las subastas combinatorias son aplicables cuando los postores tienen valoraciones no aditivas en paquetes de artículos, es decir, valoran las 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 subastas de bienes raíces , 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 radioeléctrico 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 conoce como 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. ^[2]

Aunque permiten a los postores ser más expresivos, las subastas combinatorias presentan desafíos computacionales y 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 denomina el problema de determinación del ganador .

El problema de determinación del ganador puede enunciarse 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 retenga 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 la 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 completo libro editado por Cramton, Shoham y Steinberg (2006).

Las subastas combinatorias fueron propuestas por primera vez por Rassenti, Smith y Bulfin (1982) para la asignación de franjas horarias de aterrizaje en aeropuertos . Su artículo introdujo 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 de empaquetamiento de conjuntos , la cuestión de la complejidad computacional, el uso de técnicas de economía experimental para probar subastas combinatorias y la consideración de cuestiones de compatibilidad de incentivos y revelación de la demanda en subastas combinatorias.

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

• Optimización (matemáticas)  – Estudio de algoritmos matemáticos para problemas de optimización.Pages displaying short descriptions of redirect targets
• Teoría de juegos combinatorios  : rama de la teoría de juegos que estudia los juegos secuenciales de dos jugadores con información perfecta.
• Subasta de primer precio  : subasta en la que todos los participantes presentan simultáneamente ofertas no reveladasPages displaying short descriptions of redirect targets

• Peter Cramton, Yoav Shoham y Richard Steinberg (2006). Combinatorial Auctions . MIT Press . ISBN 0-262-03342-9 . Un libro colaborativo con una amplia cobertura del tema. 
• de Vries, S.; Vohra, R. (2003). "Subastas combinatorias: una encuesta" (PDF) . INFORMS Journal on Computing . 15 (3): 284–309. CiteSeerX  10.1.1.23.8046 . doi :10.1287/ijoc.15.3.284.16077. ISSN  1526-5528.Un poco anticuado, pero una encuesta clásica.
• Vazirani, Vijay V .; Nisán, Noam ; Jardín rugoso, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.Un libro colaborativo con un buen capítulo introductorio sobre subastas combinatorias desde una perspectiva de teoría de la informática; consulte el Capítulo 11. ^{: 267–299}
• Rassenti, Stephen J .; Smith, Vernon L.; Bulfin, Robert L. (1982). "Un mecanismo de subasta combinatoria para la asignación de franjas horarias en aeropuertos" (PDF) . Bell Journal of Economics . 13 (2): 402–417. doi :10.2307/3003463. JSTOR  3003463. Archivado desde el original el 15 de enero de 2009 . Consultado el 22 de junio de 2023 .{{cite journal}}: CS1 maint: bot: original URL status unknown (link)Primer trabajo que popularizó la idea de una subasta combinatoria.
• Rothkopf, M.; Pekec, A.; Harstad, R. (1998). "Subastas combinatorias manejables computacionalmente". Management Science . 44 (8): 1131–1147. CiteSeerX  10.1.1.723.9753 . doi :10.1287/mnsc.44.8.1131.Un artículo temprano e influyente sobre consideraciones computacionales.
• Hammami, Farouk; Rekik, Monia; Coelho, Leandro C. (2019). "Enfoques de soluciones exactas y heurísticas para el problema de construcción de ofertas en subastas de adquisición de transporte con una flota heterogénea". Transportation Research Part E: Logistics and Transportation Review . 127 : 150–177. doi :10.1016/j.tre.2019.05.009. S2CID  182223089.Una aplicación de subastas combinatorias para la adquisición de servicios de transporte.
• Hsieh, Fu-Shiung (2010). "Subasta inversa combinatoria basada en la revelación de multiplicadores lagrangianos" (PDF) . Decision Support Systems . 48 (2): 323–330. doi :10.1016/j.dss.2009.08.009.
• Palacios-Huerta, Ignacio, David C. Parkes y Richard Steinberg. 2024. "Subastas combinatorias en la práctica". Revista de Literatura Económica , 62 (2): 517-53.
• Shoham, Yoav; Leyton-Brown, Kevin (2009). Sistemas multiagente: fundamentos algorítmicos, lógicos y de teoría de juegos. Nueva York: Cambridge University Press . ISBN 978-0-521-89943-7.Una descripción general en formato de libro de texto; consulte la Sección 11.3. Descargable en línea de forma gratuita.