Subasta generalizada de segundo precio

Mecanismo de subasta de búsqueda

La subasta generalizada de segundo precio (GSP) es un mecanismo de subasta no veraz para múltiples artículos. Cada postor hace una oferta. El mejor postor obtiene el primer puesto, el segundo, el segundo y así sucesivamente, pero el mejor postor paga el precio ofertado por el segundo mejor postor, el segundo mejor paga el precio ofertado por el tercero más alto, y pronto. Concebido inicialmente como una extensión natural de la subasta de Vickrey , conserva algunas de las propiedades deseables de la subasta de Vickrey. Se utiliza principalmente en el contexto de subastas de palabras clave, donde los espacios de búsqueda patrocinados se venden mediante subasta. Los primeros análisis del SPG se encuentran en la literatura económica de Edelman, Ostrovsky y Schwarz ^[1] y de Varian . ^[2] Es utilizado por la tecnología AdWords de Google y Facebook.

modelo formal

Supongamos que hay postores y espacios. Cada ranura tiene una probabilidad de que se haga clic en . Podemos suponer que los primeros puestos tienen una mayor probabilidad de ser clicados, por lo que: ${\displaystyle n}$ ${\displaystyle k<n}$ ${\displaystyle \alpha _{i}}$

${\displaystyle \alpha _{1}\geq \alpha _{2}\geq \cdots \geq \alpha _{k}.\,}$

Podemos pensar en tragamonedas virtuales adicionales con una tasa de clics cero, por lo que, por . Ahora, cada postor presenta una oferta indicando el máximo que está dispuesto a pagar por un puesto. Cada postor también tiene un valor intrínseco por comprar un espacio . Tenga en cuenta que no es necesario que la oferta de un jugador sea la misma que su valoración real . Ordenamos a los postores por su oferta, digamos: ${\displaystyle n-k}$ ${\displaystyle \alpha _{m}=0}$ ${\displaystyle k<m\leq n}$ ${\displaystyle b_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle v_{i}}$

${\displaystyle b_{1}\geq b_{2}\geq \cdots \geq b_{n},\,}$

y cobrar un precio a cada postor . El precio será 0 si no ganaron una plaza. Las tragamonedas se venden en un modelo de pago por clic , por lo que un postor solo paga por una ranura si el usuario realmente hace clic en esa ranura. Decimos que la utilidad del postor al que se le asigna el espacio es . El bienestar social total por poseer o vender todas las máquinas tragamonedas viene dado por: Los ingresos totales esperados están dados por: ${\displaystyle p_{i}}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle u_{i}=\alpha _{i}(v_{i}-p_{i})}$ ${\displaystyle SW=\sum _{i}\alpha _{i}v_{i}.}$ ${\displaystyle TR=\sum _{i}\alpha _{i}p_{i}.}$

Mecanismo SGP

Para especificar un mecanismo necesitamos definir la regla de asignación (quién obtiene qué espacio) y los precios pagados por cada postor. En una subasta generalizada de segundo precio ordenamos a los postores según su oferta y le damos el primer puesto al mejor postor, el segundo puesto al segundo mejor postor, y así sucesivamente. Luego, suponiendo que las ofertas se enumeran en orden decreciente, el postor que oferta obtiene el espacio para . Cada postor que gane un puesto paga la oferta del siguiente postor más alto, por lo que: . ${\displaystyle b_{1}\geq b_{2}\geq \cdots \geq b_{n},\,}$ ${\displaystyle b_{i}}$ ${\displaystyle i}$ ${\displaystyle 1\leq i\leq k}$ ${\displaystyle p_{i}=b_{i+1}}$

Falta de veracidad

Hay casos en los que ofertar la valoración verdadera no es un equilibrio de Nash . Por ejemplo , considere dos espacios con y y tres postores con valoraciones y ofertas y respectivamente . Así, , y . La utilidad para el postor es Este conjunto de ofertas no es un equilibrio de Nash, ya que el primer postor podría reducir su oferta a 5 y obtener el segundo puesto por el precio de 1, aumentando su utilidad a . ${\displaystyle \alpha _{1}=1}$ ${\displaystyle \alpha _{2}=0.4}$ ${\displaystyle v_{1}=7}$ ${\displaystyle v_{2}=6}$ ${\displaystyle v_{3}=1}$ ${\displaystyle b_{1}=7}$ ${\displaystyle b_{2}=6}$ ${\displaystyle b_{3}=1}$ ${\displaystyle p_{1}=b_{2}=6}$ ${\displaystyle p_{2}=b_{3}=1}$ ${\displaystyle 1}$ ${\displaystyle u_{1}=\alpha _{1}(v_{1}-p_{1})=1(7-6)=1.}$ ${\displaystyle 0.4(7-1)=2.4}$

Equilibrios del SPG

Edelman, Ostrovsky y Schwarz, ^[1] trabajando con información completa, muestran que el GSP (en el modelo presentado anteriormente) siempre tiene un equilibrio libre de envidia local eficiente, es decir, un equilibrio que maximiza el bienestar social, que se mide según dónde se asigna al postor . ranura según el vector de oferta decreciente . Además, el ingreso total esperado en cualquier equilibrio libre de envidia local es al menos tan alto como en el resultado (veraz) del VCG . ${\displaystyle SW=\sum _{i}\alpha _{i}v_{i}}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle (b_{1},\dots ,b_{n})}$

^{Caragiannis et al. [3]} dan los límites del bienestar en el equilibrio de Nash, demostrando un precio de la anarquía con límite de . Dütting et al. ^[4] y Lucier et al. demuestre ^[5] que cualquier equilibrio de Nash extrae al menos la mitad de los ingresos reales de VCG de todas las máquinas tragamonedas excepto la primera. Thompson y Leyton-Brown han realizado un análisis computacional de este juego . ^[6] ${\displaystyle 1.282}$

SPG e incertidumbre

Los resultados clásicos debidos a Edelman, Ostrovsky y Schwarz ^[1] y Varian ^[2] se mantienen en el entorno de información completa , cuando no hay incertidumbre involucrada. Resultados recientes como Gomes y Sweeney ^[7] y Caragiannis et al. ^[3] y también empíricamente por Athey y Nekipelov ^[8] discuten la versión bayesiana del juego, donde los jugadores tienen creencias sobre los otros jugadores pero no necesariamente conocen las valoraciones de los otros jugadores.

Gomes y Sweeney ^[7] demuestran que podría no existir un equilibrio eficiente en el entorno de información parcial. Caragiannis et al. ^[3] considere la pérdida de bienestar en el equilibrio de Bayes-Nash y demuestre un precio de anarquía con límite de 2,927. Los límites a los ingresos en el equilibrio de Bayes-Nash los dan Lucier et al. ^[5] y Caragiannis et al. ^[9]

Limitaciones presupuestarias

El efecto de las restricciones presupuestarias en el modelo de búsqueda patrocinada o subasta de posiciones se analiza en Ashlagi et al. ^[10] y en el problema de asignación más general de Aggarwal et al. ^[11] y Dütting et al. ^[12]

Ver también

• Subasta de Vickrey-Clarke-Groves
• Subasta generalizada de primer precio
• Anuncios de Google
• teoría de la subasta
• subasta japonesa

Referencias

1. Benjamin Edelman, Michael Ostrovsky y Michael Schwarz: "La publicidad en Internet y la subasta generalizada de segundo precio: venta de palabras clave por valor de miles de millones de dólares". American Economic Review 97(1), 2007 págs. 242-259
2. HR Varian: "Subastas de posición. Revista Internacional de Organización Industrial, 2006".
3. Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis; Kyropoulou, María; Lucier, Brendan; Paes Leme, Renato; Tardós, Eva (2015). "Limitar la ineficiencia de los resultados en las subastas generalizadas de segundo precio". Revista de teoría económica . 156 : 343–388. arXiv : 1201.6429 . doi :10.1016/j.jet.2014.04.010. S2CID  37395632.
4. Dütting, Paul; Fischer, Félix; Parkes, David C. (2011). "Compensaciones entre simplicidad y expresividad en el diseño de mecanismos". Actas de la 12ª conferencia ACM sobre comercio electrónico . págs. 341–350. doi :10.1145/1993574.1993632. ISBN 9781450302616. S2CID  607322.
5. Lucier, Brendan; Renato, Paes Leme; Eva, Tardós (2012). "Sobre los ingresos en la subasta generalizada de segundo precio". Actas de la 21ª conferencia internacional sobre la World Wide Web . págs. 361–370. doi :10.1145/2187836.2187886. ISBN 9781450312295. S2CID  6518222.
6. DRM Thompson y K. Leyton-Brown. Análisis computacional de subastas de posiciones de información perfecta. En EC '09: Actas de la décima conferencia ACM sobre comercio electrónico, páginas 51–60, Nueva York, NY, EE. UU., 2009. ACM.
7. RD Gomes y KS Sweeney. "Equilibrios de Bayes-Nash de la subasta generalizada de segundo precio". En EC '09: Actas de la décima conferencia ACM sobre comercio electrónico , páginas 107–108, Nueva York, NY, EE. UU., 2009. ACM
8. Susan Athey y Denis Nekipelov. Un modelo estructural de subastas de publicidad de búsqueda patrocinada Archivado el 25 de abril de 2012 en Wayback Machine , Taller de subastas de anuncios, 2010
9. Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis; Kyropoulou, María (2014). «Garantías de Ingresos en la Subasta de Segundo Precio Generalizada» (PDF) . Transacciones ACM sobre tecnología de Internet . 14 (2–3): 1–19. doi :10.1145/2663497. S2CID  9233522.
10. Ashlagi, Itai; Braverman, Marcos ; Jasidim, Avinatam; Lavi, Ron; Tennenholtz, Moshe (2010). "Subastas de Posición con Presupuestos: Existencia y Singularidad". La Revista BE de Economía Teórica . 10 (1): Artículo 20. doi :10.2202/1935-1704.1648. hdl : 1721.1/64459 . S2CID  8624078.
11. Aggarwal, Gagan; Muthukrishnan, Muthu ; Pal, David; Pal, Martín (2009). "Mecanismo general de subasta de publicidad en buscadores". Actas de la 18.ª conferencia internacional sobre la World Wide Web . págs. 241-250. arXiv : 0807.1297 . doi :10.1145/1526709.1526742. ISBN 9781605584874. S2CID  2800123.
12. Dütting, Paul; Henzinger, Mónica ; Weber, Ingmar (2011). "Un mecanismo expresivo para las subastas en la web". Actas de la vigésima conferencia internacional sobre la World Wide Web . págs. 127-136. doi :10.1145/1963405.1963427. ISBN 9781450306324. S2CID  2138064.

• S. Lahaie, D. Pennock, A. Saberi y R. Vohra. Teoría algorítmica de juegos , capítulo "Subastas de búsqueda patrocinadas", páginas 699–716. Prensa de la Universidad de Cambridge, 2007
• Apuntes de conferencias sobre publicidad basada en palabras clave