Una subasta de aceptación diferida ( DAA ) es una subasta en la que la asignación se elige rechazando repetidamente las ofertas menos atractivas. Se trata de un mecanismo veraz con propiedades estratégicas que lo hacen especialmente adecuado para subastas complejas como la de reasignación del espectro radioeléctrico . [1] Una ventaja importante de DAA sobre la subasta VCG más famosa es que DAA es inmune a las manipulaciones de coaliciones de postores, mientras que VCG es inmune a las manipulaciones sólo de postores individuales.
La subasta de aceptación diferida está relacionada con las subastas de reloj como la subasta japonesa , ya que ambas funcionan rechazando las ofertas que no pueden ganar hasta que solo queden las ofertas que deben ganar.
Supongamos que el gobierno quiere vender derechos de transmisión en dos áreas: el Norte y el Sur. Tres agentes compiten por estos derechos:
El gobierno quiere maximizar el bienestar social. En este caso, hay dos asignaciones factibles: darle todos los derechos a Alice (bienestar = 3) o darle el Norte a Bob y el Sur a Carl (bienestar = 2). Dado que las valoraciones son información privada de los agentes, el gobierno necesita utilizar un mecanismo veraz para inducir a los agentes a revelar sus verdaderas valoraciones. Comparamos dos tipos de mecanismos veraces.
El algoritmo Vickrey-Clarke-Groves (VCG) encuentra la asignación socialmente óptima, que consiste en darle ambas áreas a Alice. Alice debería pagar un precio determinado por las externalidades que impone a los demás agentes. En este caso, Alice paga 2 millones de dólares, ya que sin ella, el bienestar de Bob y Carl habría sido de 2 millones de dólares. Bob y Carl no reciben nada ni pagan nada.
La subasta de aceptación diferida rechaza iterativamente al agente de menor valor que puede rechazarse manteniendo un conjunto óptimo de agentes activos. Entonces, Carl es rechazado primero, luego Bob. Alice se queda y es aceptada. Luego paga un precio umbral, que es el valor de la oferta más baja que podría haber ofertado y aun así haber ganado. En este caso, el precio umbral de Alice es 1 millón de dólares, que ella paga.
Ambos tipos de subastas son veraces: ningún agente podría ganar si informa un valor diferente. Sin embargo, difieren cuando los agentes pueden formar coaliciones . Supongamos que Bob y Carl juntos aumentan su oferta a 4 millones de dólares. Ahora, ni Bob ni Carl por sí solos tienen ningún efecto sobre Alice. Entonces, la subasta VCG aceptará a Bob y Carl, ¡y les cobrará a cada uno un precio de 0! Por el contrario, la DAA rechazará a Alice, luego aceptará a Bob y Carl, y cobrará a cada uno de ellos su precio umbral, que es de 3 millones de dólares. Cada uno de ellos pierde 2 millones de dólares, por lo que la estrategia intentada no da resultados.
El rendimiento de las subastas de aceptación diferida fue analizado por Dütting et al. en 2014. Se centraron en subastas de mochila y en subastas para postores decididos . [2] En 2014, ese mismo año, investigadores de informática de Stanford, incluido Tim Roughgarden, describieron una aplicación de esta idea en un entorno de subasta doble . [3]