| Parte de una serie sobre |
| Subastas |
|---|
.jpg/440px-Microcosm_of_London_Plate_006_-_Auction_Room,_Christie's_(colour).jpg) |
| Tipos |
|
| Ofertas |
| Contextos |
|
| Teoría |
|
| En línea |
|
Una subasta combinatoria es un tipo de mercado inteligente en el que los participantes pueden realizar ofertas en 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 varios lotes . [1] Las subastas combinatorias son aplicables cuando los licitadores tienen valoraciones no aditivas sobre paquetes de artículos, es decir, valoran combinaciones de artículos más o menos que la suma de sus valoraciones de elementos individuales de la combinación.
Las subastas combinatorias simples se han utilizado durante muchos años en las subastas de bienes raíces , donde un procedimiento común es aceptar ofertas para 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 las adquisiciones de construcción a menudo implican negociaciones sobre múltiples componentes, se sugieren subastas inversas combinatorias para reducir los costos en esta industria. [2]
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 de cálculo es cómo determinar eficientemente la asignación una vez que las ofertas se han presentado al subastador. A esto se le 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 retenga algunos artículos, que maximice los ingresos del subastador. Este problema es difícil para grandes instancias. 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 puede modelarse como un problema de empaquetado fijo . Por lo tanto, se han propuesto muchos algoritmos para encontrar soluciones aproximadas al problema de la subasta combinatoria. Por ejemplo, Hsieh (2010) propuso una relajación lagrangiana enfoque para problemas combinatorios de subasta inversa.
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 espacios de aterrizaje en los aeropuertos . Su artículo introdujo muchas ideas clave sobre 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 empaquetado de conjuntos , el tema de la complejidad computacional, el uso de técnicas de la economía experimental para probar combinatorias. 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 una 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 a los precios en aumento, con una subasta de puja sellada subsecuente, en la que los postores presentan ofertas de paquete sellado . El subastador utiliza las ofertas finales para calcular la asignación de mejor valor y los pagos de Vickrey . [3] [4]
Ver también
- Optimización (matemáticas)
- Teoría de juegos combinatorios
- Subasta de primer precio
Referencias
- ^ Mullen, Tracy; Wellman, Michael P. (1998). "The Auction Manager: Market Middleware para el comercio electrónico a gran escala" (PDF) . Taller de USENIX sobre Comercio Electrónico .
- ^ Al Shaqsi, Salim (2018). "Subastas inversas combinatorias en la contratación de la construcción" . Consultado el 22 de mayo de 2021 . Cite journal requiere
|journal=( ayuda ) - ^ Bichler, Martin; Goeree, Jacob K. (26 de octubre de 2017). Manual de diseño de subastas de espectro . Prensa de la Universidad de Cambridge. ISBN 978-1-107-13534-5. Consultado el 22 de octubre de 2020 .
- ^ Ausubel, Lawrence M .; Baranov, Oleg (1 de octubre de 2017). "Una guía práctica para la subasta de relojes combinatorios" . The Economic Journal . 127 (605): F334 – F350. doi : 10.1111 / ecoj.12404 . ISSN 0013-0133 . S2CID 26571660 .
Lectura adicional
- Peter Cramton, Yoav Shoham y Richard Steinberg (2006). Subastas Combinatorias . Prensa del MIT . ISBN 0-262-03342-9 . Un libro contribuido con una amplia cobertura del tema.
- de Vries, S .; Vohra, R. (2003). "Subastas combinatorias: una encuesta" (PDF) . INFORMA Revista de Computación . 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 .; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.. Un libro contribuido con un buen capítulo introductorio sobre subastas combinatorias desde la perspectiva de la teoría de las ciencias de la computación; ver 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 los aeropuertos" (PDF) . Bell Journal of Economics . 13 (2): 402–417. doi : 10.2307 / 3003463 . JSTOR 3003463 . Trabajo temprano que popularizó la idea de una subasta combinatoria.
- Rothkopf, M .; Pekec, A .; Harstad, R. (1998). "Subastas combinatorias computacionalmente manejables". Ciencias de la gestión . 44 (8): 1131-1147. CiteSeerX 10.1.1.723.9753 . doi : 10.1287 / mnsc.44.8.1131 . Un artículo temprano influyente sobre consideraciones computacionales.
- Hammami, Farouk; Rekik, Monia; Coelho, Leandro C. (2019). "Enfoques de solución exacta y heurística para el problema de construcción de licitaciones en subastas de aprovisionamiento de transporte con flota heterogénea". Investigación de transporte Parte E: Revisión de logística y transporte . 127 : 150-177. doi : 10.1016 / j.tre.2019.05.009 . Una aplicación de subastas combinatorias para la contratación de servicios de transporte.
- Hsieh, Fu-Shiung (2010). "Subasta combinatoria inversa basada en la revelación de multiplicadores lagrangianos" (PDF) . Sistemas de apoyo a la toma de decisiones . 48 (2): 323–330. doi : 10.1016 / j.dss.2009.08.009 .
- Shoham, Yoav; Leyton-Brown, Kevin (2009). Sistemas multiagente: fundamentos algorítmicos, teóricos de juegos y lógicos . Nueva York: Cambridge University Press . ISBN 978-0-521-89943-7.Una descripción general en forma de libro de texto; consulte la Sección 11.3. Descarga gratuita en línea .
