Subasta secuencial

Una subasta secuencial es una subasta en la que se venden varios artículos, uno tras otro, al mismo grupo de compradores potenciales. En una subasta secuencial de primer precio (SAFP), cada artículo individual se vende mediante una subasta de primer precio , mientras que en una subasta secuencial de segundo precio (SASP), cada artículo individual se vende mediante una subasta de segundo precio .

Una subasta secuencial se diferencia de una subasta combinatoria , en la que se subastan muchos artículos simultáneamente y los agentes pueden pujar por paquetes de artículos. Una subasta secuencial es mucho más sencilla de implementar y más común en la práctica. Sin embargo, los postores de cada subasta saben que habrá subastas futuras y esto puede afectar sus consideraciones estratégicas. A continuación se muestran algunos ejemplos.

Ejemplo 1. [ ^1] Hay dos artículos en venta y dos compradores potenciales: Alice y Bob, con las siguientes valoraciones:

• Alice valora cada artículo como 5, y ambos artículos como 10 (es decir, su valoración es aditiva ).
• Bob valora cada artículo como 4, y ambos artículos como 4 (es decir, su valoración es demanda unitaria ).

En un SASP, cada artículo se pone en una subasta de segundo precio. Por lo general, esta subasta es un mecanismo veraz , por lo que si cada artículo se vende de forma aislada, Alice gana ambos artículos y paga 4 por cada uno, su pago total es 4 + 4 = 8 y su utilidad neta es 5 + 5 − 8 = 2. Pero, si Alice conoce las valoraciones de Bob, tiene una mejor estrategia: puede dejar que Bob gane el primer artículo (por ejemplo, ofertando 0). Entonces, Bob no participará en la segunda subasta en absoluto, por lo que Alice ganará el segundo artículo y pagará 0, y su utilidad neta será 5 − 0 = 5.

Un resultado similar ocurre en un SAFP. Si cada artículo se vende de forma aislada, existe un equilibrio de Nash en el que Alice ofrece un precio ligeramente superior a 4 y gana, y su utilidad neta es ligeramente inferior a 2. Pero, si Alice conoce las valoraciones de Bob, puede desviarse hacia una estrategia que le permita a Bob ganar en la primera ronda para que en la segunda ronda ella pueda ganar por un precio ligeramente superior a 0.

Ejemplo 2. [ ^2] Se subastan varios objetos idénticos y los agentes tienen limitaciones presupuestarias. Puede ser ventajoso para un postor pujar agresivamente por un objeto con vistas a aumentar el precio pagado por su rival y agotar su presupuesto para que el segundo objeto pueda entonces obtenerse a un precio más bajo. En efecto, un postor puede desear “aumentar los costos de un rival” en un mercado para obtener ventaja en otro. Tales consideraciones parecen haber desempeñado un papel importante en las subastas de licencias de espectro radioeléctrico realizadas por la Comisión Federal de Comunicaciones . La evaluación de las limitaciones presupuestarias de los postores rivales fue un componente principal de la preparación previa a la licitación del equipo de licitación de GTE .

Equilibrio de Nash

Una subasta secuencial es un caso especial de un juego secuencial . Una pregunta natural que se plantea en este tipo de juego es cuándo existe un equilibrio perfecto en subjuegos en estrategias puras (SPEPS). Cuando los jugadores tienen información completa (es decir, conocen la secuencia de subastas de antemano) y se vende un solo artículo en cada ronda, un SAFP siempre tiene un SPEPS, independientemente de las valoraciones de los jugadores. La prueba es por inducción hacia atrás : ^{[1] : 872–874}

• En la última ronda, tenemos una subasta de primer precio simple . Tiene un equilibrio de Nash de estrategia pura en el que el agente de mayor valor gana al ofertar un poco más que el segundo valor más alto.
• En cada ronda anterior, la situación es un caso especial de subasta de primer precio con externalidades . En una subasta de este tipo, cada agente puede ganar valor, no solo cuando gana, sino también cuando ganan otros agentes. En general, la valoración del agente está representada por un vector , donde es el valor del agente cuando gana. En una subasta secuencial, las externalidades están determinadas por los resultados de equilibrio en las rondas futuras. En el ejemplo introductorio, hay dos resultados posibles: ${\displaystyle i}$ ${\displaystyle v_{i}[1],\dots ,v_{i}[n]}$ ${\displaystyle v_{i}[j]}$ ${\displaystyle i}$ ${\displaystyle j}$
  • Si Alice gana la primera ronda, entonces el resultado de equilibrio en la segunda ronda es que Alice compra un artículo que vale $5 por $4, ^[3] por lo que su ganancia neta es $1. Por lo tanto, su valor total por ganar la primera ronda es . ${\displaystyle v_{\text{Alice}}[{\text{Alice}}]=5+1=6}$
  • Si Bob gana la primera ronda, entonces el resultado de equilibrio en la segunda ronda es que Alice compra un artículo que vale $5 por $0, por lo que su ganancia neta es $5. Por lo tanto, su valor total por dejar que Bob gane es . ${\displaystyle v_{\text{Alice}}[{\text{Bob}}]=0+5=5}$
• Cada subasta de primer precio con externalidades tiene un equilibrio de Nash de estrategia pura. ^[1] En el ejemplo anterior, el equilibrio en la primera ronda es que Bob gana y paga $1.
• Por lo tanto, por inducción hacia atrás, cada SAFP tiene una SPE de estrategia pura.

Notas:

• El resultado de existencia también es válido para SASP. De hecho, cualquier resultado de equilibrio de una subasta de primer precio con externalidades es también un resultado de equilibrio de una subasta de segundo precio con las mismas externalidades.
• El resultado de existencia se cumple independientemente de las valoraciones de los postores: pueden tener funciones de utilidad arbitrarias sobre bienes indivisibles . Por el contrario, si todas las subastas se realizan simultáneamente , no siempre existe un equilibrio de Nash de estrategia pura, incluso si los postores tienen funciones de utilidad subaditivas . ^[4]

Bienestar social

Una vez que sabemos que existe un equilibrio perfecto en subjuegos , la siguiente pregunta natural es qué tan eficiente es: ¿obtiene el máximo bienestar social? Esto se cuantifica mediante el precio de la anarquía (PoA), la relación entre el máximo bienestar social alcanzable y el bienestar social en el peor equilibrio. En el Ejemplo 1 introductorio, el máximo bienestar social alcanzable es 10 (cuando Alice gana ambos artículos), pero el bienestar en equilibrio es 9 (Bob gana el primer artículo y Alice gana el segundo), por lo que el PoA es 10/9. En general, el PoA de las subastas secuenciales depende de las funciones de utilidad de los postores.

Los primeros cinco resultados se aplican a los agentes con información completa (todos los agentes conocen las valoraciones de todos los demás agentes):

Caso 1: Artículos idénticos . ^{[5] [6]} Hay varios artículos idénticos. Hay dos postores. Al menos uno de ellos tiene una función de valoración cóncava ( rendimientos decrecientes ). El PoA de SASP es como máximo . Los resultados numéricos muestran que, cuando hay muchos postores con funciones de valoración cóncavas, la pérdida de eficiencia disminuye a medida que aumenta el número de usuarios. ${\displaystyle 1/(1-e)\approx 1.58}$

Caso 2: postores aditivos . ^{[1] : 885} Los artículos son diferentes y todos los postores consideran que todos los artículos son bienes independientes , por lo que sus valoraciones son funciones de conjunto aditivas . El PoA de SASP no tiene límites: el bienestar en un SPEPS puede ser arbitrariamente pequeño.

Caso 3: postores con demanda unitaria . ^[1] Todos los postores consideran que todos los artículos son bienes sustitutos puros , por lo que sus valoraciones son demanda unitaria . El PoA de SAFP es como máximo 2 – el bienestar en un SPEPS es como mínimo la mitad del máximo (si se permiten estrategias mixtas, el PoA es como máximo 4). Por el contrario, el PoA en SASP es nuevamente ilimitado.

Estos resultados son sorprendentes y resaltan la importancia de la decisión de diseño de utilizar una subasta de primer precio (en lugar de una subasta de segundo precio) en cada ronda.

Caso 4: postores submodulares . ^[1] Las valoraciones de los postores son funciones de conjunto submodulares arbitrarias (nótese que la demanda aditiva y la demanda unitaria son casos especiales de submodular). En este caso, el PoA tanto de SAFP como de SASP es ilimitado, incluso cuando solo hay cuatro postores. La intuición es que el postor de alto valor podría preferir dejar que gane un postor de bajo valor, para disminuir la competencia que podría enfrentar en las rondas futuras.

Caso 5: aditivo+UD . ^[7] Algunos postores tienen valoraciones aditivas mientras que otros tienen valoraciones de demanda unitaria. El PoA de SAFP podría ser al menos , donde m es el número de artículos y n es el número de postores. Además, los equilibrios ineficientes persisten incluso bajo la eliminación iterada de estrategias débilmente dominadas. Esto implica ineficiencia lineal para muchos entornos naturales, incluidos: ${\displaystyle \min(n,m)}$

• Postores con valoraciones brutas de sustitución ,
• valoraciones capacitadas,
• valoraciones aditivas al presupuesto,
• valoraciones aditivas con duras restricciones presupuestarias sobre los pagos.

Caso 6: postores con demanda unitaria y con información incompleta . ^[8] Los agentes no conocen las valoraciones de los demás agentes, sino solo la distribución de probabilidad de la que se extraen sus valoraciones. La subasta secuencial es entonces un juego bayesiano y su PoA podría ser mayor. Cuando todos los postores tienen valoraciones con demanda unitaria , el PoA de un equilibrio de Nash bayesiano en un SAFP es como máximo 3.

Maximización de ingresos

Una cuestión práctica importante para los vendedores que venden varios artículos es cómo diseñar una subasta que maximice sus ingresos. Hay varias preguntas:

• 1. ¿Es mejor utilizar una subasta secuencial o una subasta simultánea? Las subastas secuenciales con ofertas anunciadas entre ventas parecen preferibles porque las ofertas pueden transmitir información sobre el valor de los objetos que se venderán más tarde. La literatura sobre subastas muestra que este efecto de información aumenta los ingresos esperados del vendedor, ya que reduce la maldición del ganador . Sin embargo, también existe un efecto de engaño que se desarrolla en las ventas secuenciales. Si un postor sabe que su oferta actual revelará información sobre objetos posteriores, entonces tiene un incentivo para ofertar por menos de lo que debería. ^[9]
• 2. Si se utiliza una subasta secuencial, ¿en qué orden se deben vender los artículos para maximizar los ingresos del vendedor?

Supongamos que hay dos artículos y que hay un grupo de postores sujetos a restricciones presupuestarias. Los objetos tienen valores comunes para todos los postores, pero no necesariamente son idénticos y pueden ser bienes complementarios o bienes sustitutos . En un juego con información completa : ^[2]

• 1. Una subasta secuencial produce más ingresos que una subasta simultánea ascendente si: (a) la diferencia entre los valores de los artículos es grande, o (b) existen complementariedades significativas.
  Una forma híbrida simultánea-secuencial produce mayores ingresos que la subasta secuencial.
• 2. Si los objetos se venden mediante una secuencia de subastas abiertas ascendentes, entonces siempre es óptimo vender primero el objeto más valioso (asumiendo que los valores de los objetos son de conocimiento común).

Además, las restricciones presupuestarias pueden surgir de forma endógena. Es decir, una empresa que oferta puede decirle a su representante "puede gastar como máximo X en esta subasta", aunque la propia empresa tenga mucho más dinero para gastar. Limitar el presupuesto de antemano ofrece a los ofertantes algunas ventajas estratégicas.

Cuando se venden varios objetos, las restricciones presupuestarias pueden tener otras consecuencias imprevistas. Por ejemplo, un precio mínimo puede aumentar los ingresos del vendedor aunque esté fijado en un nivel tan bajo que nunca es vinculante en el equilibrio.

Mecanismos componibles

Las subastas secuenciales y simultáneas son casos especiales de un contexto más general, en el que los mismos postores participan en varios mecanismos diferentes. Syrgkanis y Tardos ^[10] sugieren un marco general para el diseño de mecanismos eficientes con buenas propiedades garantizadas incluso cuando los jugadores participan en múltiples mecanismos de manera simultánea o secuencial. La clase de mecanismos suaves (mecanismos que generan precios de equilibrio del mercado aproximados) da como resultado un resultado de alta calidad tanto en equilibrio como en resultados de aprendizaje en el contexto de información completa, así como en equilibrio bayesiano con incertidumbre sobre los participantes. Los mecanismos suaves se componen bien: la suavidad local en cada mecanismo implica eficiencia global. Para los mecanismos donde un buen desempeño requiere que los postores no oferten por encima de su valor, se pueden usar mecanismos débilmente suaves , como la subasta Vickrey. Son aproximadamente eficientes bajo el supuesto de no sobreoferta, y la propiedad de suavidad débil también se mantiene por la composición. Algunos de los resultados son válidos también cuando los participantes tienen restricciones presupuestarias.

Referencias

1. Leme, Renato Paes; Syrgkanis, Vasilis; Tardos, Eva (2012). "Subastas secuenciales y externalidades". Actas del vigésimo tercer simposio anual ACM-SIAM sobre algoritmos discretos . pág. 869. arXiv : 1108.2452 . doi :10.1137/1.9781611973099.70. ISBN. 978-1-61197-210-8.
2. Benoit, J.-P.; Krishna, V. (2001). "Subastas de objetos múltiples con postores con limitaciones presupuestarias". The Review of Economic Studies . 68 : 155–179. doi :10.1111/1467-937X.00164.
3. De hecho, Alice podría pagar un poco más de $4 (por ejemplo, si las ofertas están en centavos enteros, Alice podría pagar $4,01). Para simplificar, ignoramos esta diferencia infinitesimal.
4. Hassidim, Avinatan; Kaplan, Haim; Mansour, Yishay; Nisan, Noam (2011). "Equilibrios no relacionados con el precio en mercados de bienes discretos". Actas de la 12.ª conferencia de la ACM sobre comercio electrónico – EC '11 . pág. 295. arXiv : 1103.3950 . doi :10.1145/1993574.1993619. ISBN 9781450302616.
5. Bae, Junjik; Beigman, Eyal; Berry, Randall ; Honig, Michael; Vohra, Rakesh (2008). "Subastas secuenciales de ancho de banda y potencia para la compartición distribuida del espectro". Revista IEEE sobre áreas seleccionadas en comunicaciones . 26 (7): 1193. doi :10.1109/JSAC.2008.080916. S2CID  28436853.
6. Bae, Junjik; Beigman, Eyal; Berry, Randall ; Honig, Michael L.; Vohra, Rakesh (2009). "Sobre la eficiencia de las subastas secuenciales para compartir el espectro". Conferencia internacional de 2009 sobre teoría de juegos para redes . pág. 199. CiteSeerX 10.1.1.148.7218 . doi :10.1109/gamenets.2009.5137402. ISBN .  978-1-4244-4176-1.
7. Feldman, Michal ; Lucier, Brendan; Syrgkanis, Vasilis (2013). "Límites de eficiencia en subastas secuenciales". Economía de Internet y Web . Apuntes de clase en informática. Vol. 8289. pág. 160. arXiv : 1309.2529 . doi :10.1007/978-3-642-45046-4_14. ISBN . 978-3-642-45045-7.
8. Syrgkanis, Vasilis; Tardos, Eva (2012). "Subastas secuenciales bayesianas". Actas de la 13.ª Conferencia de la ACM sobre comercio electrónico – EC '12 . pág. 929. arXiv : 1206.4771 . doi :10.1145/2229012.2229082. ISBN 9781450314152.
9. Hausch, Donald B. (1986). "Subastas de objetos múltiples: ventas secuenciales frente a ventas simultáneas". Management Science . 32 (12): 1599–1610. doi :10.1287/mnsc.32.12.1599.
10. Syrgkanis, Vasilis; Tardos, Eva (2013). "Mecanismos componibles y eficientes". Actas del 45.º simposio anual de la ACM sobre teoría de la computación – STOC '13 . pág. 211. arXiv : 1211.1325 . doi :10.1145/2488608.2488635. ISBN 9781450320290.