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 ofertar 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. Aquí hay unos ejemplos.

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

• Alice valora cada elemento como 5 y ambos elementos 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 la demanda unitaria ).

En un SASP, cada artículo se somete a una subasta de segundo precio. Por lo general, dicha 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 artículo, 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 estrategia mejor: puede dejar que Bob gane el primer artículo (por ejemplo, ofertando 0). Entonces, Bob no participará en la segunda subasta, 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 una SAFP. Si cada artículo se vende de forma aislada, existe un equilibrio de Nash en el que Alice oferta ligeramente por encima de 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 ganar a Bob. en la primera ronda para que en la segunda 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 resultar ventajoso para un postor ofertar agresivamente por un objeto con miras a aumentar el precio pagado por su rival y agotar su presupuesto, de modo que luego pueda obtener el segundo objeto 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. Estas consideraciones parecen haber jugado 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 juego secuencial . Una pregunta natural para un juego de este tipo 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 las subastas de antemano) y se vende un solo artículo en cada ronda, una 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 simple de primer precio . Tiene un equilibrio de Nash de estrategia pura en el que el agente de mayor valor gana ofertando ligeramente por encima del segundo valor más alto.
• En cada ronda anterior, la situación es un caso especial de subasta de primer precio con externalidades . En dicha subasta, cada agente puede ganar valor, no sólo cuando él gana, sino también cuando otros agentes ganan. En general, la valoración del agente está representada por un vector , donde es el valor del agente cuando el agente 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 Alicia gana la primera ronda, entonces el resultado de equilibrio en la segunda ronda es que Alicia compra un artículo que vale 5 dólares por 4 dólares, ^[3] por lo que su ganancia neta es 1 dólar. 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 ganar a Bob 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 mantiene 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 por el precio de la anarquía (PoA), es decir, la relación entre el máximo bienestar social alcanzable y el bienestar social en el peor equilibrio. En el ejemplo introductorio 1, el bienestar social máximo alcanzable es 10 (cuando Alice gana ambos ítems), pero el bienestar en equilibrio es 9 (Bob gana el primer ítem 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 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 elementos 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 todos los artículos como bienes independientes , por lo que sus valoraciones son funciones de conjuntos aditivos . El PoA de SASP es ilimitado: el bienestar en un SPEPS podría ser arbitrariamente pequeño.

Caso 3: Postores de demanda unitaria . ^[1] Todos los postores consideran todos los artículos como 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 al menos la mitad del máximo (si se permiten estrategias mixtas, el PoA es como máximo 4). En contraste, el PoA en SASP nuevamente es ilimitado.

Estos resultados son sorprendentes y enfatizan 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 conjuntos submodulares arbitrarios (tenga en cuenta que la suma y la demanda unitaria son casos especiales de submodular). En este caso, el PoA tanto de la SAFP como del SASP es ilimitado, incluso cuando sólo hay cuatro postores. La intuición es que el postor de alto valor podría preferir dejar ganar a un postor de bajo valor, para disminuir la competencia que podría enfrentar en 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 reiterada de estrategias débilmente dominadas. Esto implica una ineficiencia lineal para muchos entornos naturales, incluidos: ${\displaystyle \min(n,m)}$

• Postores con valoraciones sustitutivas brutas ,
• valoraciones capacitadas,
• valoraciones aditivas al presupuesto,
• valoraciones aditivas con fuertes restricciones presupuestarias en los pagos.

Caso 6: oferentes de demanda unitaria con información incompleta . ^[8] Los agentes no conocen las valoraciones de los demás agentes, sino sólo 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 de demanda unitaria , el PoA de un equilibrio bayesiano de Nash 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 adelante. 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 menos. ^[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 hay un grupo de postores que están sujetos a restricciones presupuestarias. Los objetos tienen valores comunes a todos los postores pero no necesitan ser 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 ascendente simultánea 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 genera 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 (suponiendo que los valores de los objetos sean de conocimiento común).

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

Cuando se venden varios objetos, las limitaciones presupuestarias pueden tener otras consecuencias imprevistas. Por ejemplo, un precio de reserva puede aumentar los ingresos del vendedor aunque se fije en un nivel tan bajo que nunca sea vinculante en equilibrio.

Mecanismos componibles

Las subastas secuenciales y las subastas simultáneas son casos especiales de un entorno 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 forma simultánea o secuencial. La clase de mecanismos fluidos (mecanismos que generan aproximadamente precios de equilibrio del mercado) dan como resultado resultados de alta calidad tanto en equilibrio como en resultados de aprendizaje en el entorno de información completa, así como en equilibrio bayesiano con incertidumbre sobre los participantes. Los mecanismos fluidos se componen bien: la suavidad local en cada mecanismo implica eficiencia global. Para los mecanismos en los que el buen desempeño requiere que los postores no oferten por encima de su valor, se pueden utilizar mecanismos débilmente suaves , como la subasta de Vickrey. Son aproximadamente eficientes bajo el supuesto de no sobreoferta, y la composición también mantiene la propiedad de suavidad débil. Algunos de los resultados son válidos también cuando los participantes tienen restricciones presupuestarias.

Referencias

1. Leme, Renato Paes; Syrgkanis, Vasilis; Tardós, Eva (2012). "Subastas Secuenciales y Externalidades". Actas del vigésimo tercer simposio anual ACM-SIAM sobre algoritmos discretos . pag. 869. arXiv : 1108.2452 . doi :10.1137/1.9781611973099.70. ISBN 978-1-61197-210-8.
2. Benoit, JP; Krishna, V. (2001). "Subastas de objetos múltiples con postores con presupuesto limitado". La Revista de Estudios Económicos . 68 : 155-179. doi :10.1111/1467-937X.00164.
3. De hecho, Alicia puede pagar un poco más de 4 dólares (por ejemplo, si las ofertas son en centavos enteros, Alicia puede pagar 4,01 dólares). Por simplicidad, ignoramos esta diferencia infinitesimal.
4. Jasidim, Avinatan; Kaplan, Haim; Mansur, Yishay; Nisán, Noam (2011). "Equilibrios distintos de los precios en mercados de bienes discretos". Actas de la 12ª conferencia ACM sobre comercio electrónico - EC '11 . pag. 295. arXiv : 1103.3950 . doi :10.1145/1993574.1993619. ISBN 9781450302616.
5. Bae, Junjik; Beigman, Eyal; Baya, Randall ; Honig, Michael; Vohra, Rakesh (2008). "Subastas secuenciales de ancho de banda y energía para compartir espectro distribuido". Revista IEEE sobre áreas seleccionadas de las comunicaciones . 26 (7): 1193. doi :10.1109/JSAC.2008.080916. S2CID  28436853.
6. Bae, Junjik; Beigman, Eyal; Baya, Randall ; Honig, Michael L.; Vohra, Rakesh (2009). "Sobre la eficiencia de las subastas secuenciales para compartir espectro". 2009 Congreso Internacional sobre Teoría de Juegos para Redes . pag. 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 la Web y de Internet . Apuntes de conferencias sobre 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; Tardós, Eva (2012). "Subastas secuenciales bayesianas". Actas de la 13ª Conferencia ACM sobre Comercio Electrónico - EC '12 . pag. 929. arXiv : 1206.4771 . doi :10.1145/2229012.2229082. ISBN 9781450314152.
9. Hausch, Donald B. (1986). "Subastas de objetos múltiples: ventas secuenciales versus ventas simultáneas". Ciencias de la gestión . 32 (12): 1599-1610. doi :10.1287/mnsc.32.12.1599.
10. Syrgkanis, Vasilis; Tardós, Eva (2013). "Mecanismos componibles y eficientes". Actas del 45º simposio anual de ACM sobre Simposio sobre teoría de la informática - STOC '13 . pag. 211. arXiv : 1211.1325 . doi :10.1145/2488608.2488635. ISBN 9781450320290.