Precio de la anarquía en subastas

El Precio de la Anarquía (PoA) es un concepto en teoría de juegos y diseño de mecanismos que mide cómo se degrada el bienestar social de un sistema debido al comportamiento egoísta de sus agentes. Se ha estudiado extensamente en varios contextos, particularmente en subastas.

En una subasta, hay uno o más artículos y uno o más agentes con diferentes valoraciones para los artículos. Los artículos tienen que ser divididos entre los agentes. Se desea que el bienestar social -la suma de valores de todos los agentes- sea lo más alto posible.

Un enfoque para maximizar el bienestar social es diseñar un mecanismo veraz. En dicho mecanismo, se incentiva a cada agente a informar sus verdaderas valoraciones a los artículos. Luego, el subastador puede calcular e implementar una asignación que maximice la suma de valores. Un ejemplo de tal mecanismo es la subasta de VCG.

En la práctica, sin embargo, no siempre es factible utilizar mecanismos veraces. El mecanismo VCG, por ejemplo, puede ser demasiado complicado para que lo entiendan los participantes, puede tomar demasiado tiempo para que el subastador lo calcule y puede tener otras desventajas. En la práctica, a menudo se utilizan mecanismos no veraces, y es interesante calcular cuánto bienestar social se pierde por esta no veracidad.

A menudo se supone que, en una subasta no veraz, los participantes juegan una estrategia de equilibrio, como un equilibrio de Nash. El precio de la anarquía de la subasta se define como la relación entre el bienestar social óptimo y el bienestar social en el peor equilibrio:

Una noción relacionada es el Precio de la Estabilidad (PoS) que mide la relación entre el bienestar social óptimo y el bienestar social en el mejor equilibrio:

Obviamente _

Cuando hay información completa (cada agente conoce las valoraciones de todos los demás agentes), el tipo de equilibrio común es el equilibrio de Nash, ya sea puro o mixto. Cuando hay información incompleta, el tipo de equilibrio común es el equilibrio de Bayes-Nash. En este último caso, es habitual hablar del precio bayesiano de la anarquía, o BPoA.

Subastas de un solo artículo

En una subasta de primer precio de un solo artículo, un equilibrio de Nash siempre es eficiente, por lo que el PoA y el PoS son 1.

En una subasta de segundo precio, existe un equilibrio de Nash en el que los agentes informan con veracidad; es eficiente, por lo que el PoS es 1. Sin embargo, ¡el PoA no tiene límites! Por ejemplo, supongamos que hay dos jugadores: Alice valora el elemento como a y Bob como b, con a > b.

Existe un equilibrio de Nash "bueno" en el que Alice ofrece a y Bob ofrece b; Alice recibe el artículo y paga b. El bienestar social es un, que es óptimo.

Sin embargo, también existe un equilibrio de Nash "malo" en el que Alice ofrece 0 y Bob ofrece, por ejemplo, un +1; Bob recibe el artículo y no paga nada. Este es un equilibrio ya que Alice no quiere sobrepujar a Bob. El bienestar social es b. Por lo tanto, el PoA es a / b, que no tiene límites.

Este resultado parece demasiado pesimista:

• Primero, en una subasta de segundo precio, es una estrategia débilmente dominante para cada agente informar su verdadera valoración. Si asumimos que los agentes siguen sus estrategias dominantes, entonces el PoA es 1.
• Además, es una estrategia dominada para que cada agente informe cualquier valor por encima de su valoración real.

Por lo tanto, es común analizar el PoA bajo un supuesto de no sobreoferta: ningún agente puja por encima de su valuación real. Bajo este supuesto, el PoA de una subasta de un solo artículo es 1.

Subastas paralelas

En una subasta paralela (simultánea), los artículos se venden al mismo tiempo al mismo grupo de participantes. A diferencia de una subasta combinatoria, en la que los agentes pueden pujar por paquetes de artículos, aquí los agentes solo pueden pujar por artículos individuales independientemente de los demás. Es decir, una estrategia de un agente es un vector de ofertas, una oferta por artículo. El PoA depende del tipo de valoraciones de los compradores y del tipo de subasta utilizada para cada artículo individual.

Caso 1: compradores submodulares, subastas de segundo precio, información completa:

• Existe un equilibrio de Nash puro con un bienestar social óptimo. Por lo tanto, el PoS es 1.
• Es posible calcular en tiempo polinomial un equilibrio de Nash puro con bienestar social al menos la mitad del óptimo. Por lo tanto, el precio de la "estabilidad polinomial en el tiempo" es como mucho 2.
• El PoA no tiene límites, como ya se muestra en el ejemplo anterior de un solo elemento. Sin embargo, bajo una suposición fuerte de no sobreoferta (la suma de las ofertas de cualquier comprador para cualquier paquete es como máximo el valor de ese paquete para el comprador), el PoA es como máximo 2. El último resultado también se cumple cuando los compradores las valoraciones son fraccionariamente subaditivas.

Caso 2: compradores fraccionalmente subaditivos, subasta de 2º precio, información incompleta. Asumiendo fuerte-no-sobreoferta, cualquier equilibrio Bayes-Nash (mixto) alcanza en la expectativa al menos la mitad del bienestar óptimo; por lo tanto, el BPoA es como máximo 2. Este resultado no depende del prior común de los agentes.

Caso 3: compradores subaditivos, subastas de 2º precio. Bajo una suposición fuerte de no sobrepujar:

• Con información completa, el bienestar de cada equilibrio de Nash puro es al menos la mitad del óptimo, por lo que el PoA es como máximo 2.
• Con información incompleta, existen equilibrios de Bayes-Nash con un bienestar inferior a la mitad del óptimo, por lo que el BPoA es superior a 2.
• El BPoA es como máximo , donde es el número de elementos. Esta garantía también es válida para el equilibrio correlacionado grueso y, por lo tanto, para los casos especiales de equilibrio mixto de Nash y equilibrio correlacionado.
• Los dos límites superiores anteriores en el PoA se degradan con gracia cuando se relajan los supuestos de subaditividad y no sobreoferta. Por ejemplo: si asumimos que cada jugador sobrepuja por un factor constante como máximo, entonces el PoA crece por un factor constante como máximo.

Caso 4: Compradores generales (monótonos), subastas de primer precio, información completa:

• El conjunto de equilibrios de Nash puros del juego son exactamente los equilibrios walrasianos (equilibrios de precios) del mercado.
• Dado que tales equilibrios son socialmente óptimos (según el primer teorema del bienestar), el PoA de los equilibrios de Nash puros es 1. Desafortunadamente, tales equilibrios podrían no existir.
• Siempre existe un equilibrio de Nash mixto (cuando se elige la regla de desempate correcta). Sin embargo, no es necesariamente socialmente óptimo. El PoA puede ser tan alto como , e incluso el PoS puede ser tan alto como .
  • Este resultado también se extiende a las subastas de segundo precio, incluso con una suposición de sobreoferta débil.
• El PoA es como mucho .
• Cuando todas las valoraciones son subaditivas, el PoA es como máximo .
• Cuando todas las valoraciones son fraccionariamente subaditivas, el PoA es como máximo (en particular, para los compradores de XOS, el PoA es como máximo 2).
• Los últimos tres límites también son válidos para equilibrios de correlación gruesa; NO requieren una suposición de "no sobrepujar".

Caso 5: Compradores generales, subastas a 2º precio, información completa. Con valoraciones generales (que pueden tener complementariedades), el supuesto fuerte de no oferta excesiva es demasiado fuerte, ya que evita que los compradores ofrezcan valores altos en paquetes de artículos complementarios. Por ejemplo, si la valoración de un comprador es de $100 por un par de zapatos pero $1 por cada zapato individual, entonces la suposición fuerte de no sobrepujar le impide ofertar más de $1 por cada zapato, por lo que tiene pocas posibilidades de ganar el par.. Por lo tanto, se reemplaza con una oferta débil sin sobreoferta.supuesto, lo que significa que la condición de no sobrepujar se cumple solo para la cesta que finalmente gana el agente (es decir, la suma de las pujas del comprador a su cesta asignada es como máximo su valor para esta cesta específica). Bajo esta suposición débil de no sobrepujar:

• El conjunto de equilibrios de Nash puros del juego son exactamente los equilibrios de precios condicionales del mercado.
• Dado que tales equilibrios son socialmente óptimos a la mitad (alcanzan al menos la mitad del bienestar social máximo), el PoA de los equilibrios de Nash puros es como máximo 2. Desafortunadamente, es posible que tales equilibrios no existan.

Caso 6: Compradores generales, subastas a 1er precio, información incompleta. Para cualquier anterior común:

• El BPoA es como máximo .
• Cuando todas las valoraciones son fraccionariamente subaditivas, el BPoA es como máximo (en particular, para compradores XOS, el BPoA es como máximo 2, y para compradores subaditivos, es ).

Caso 7: Compradores subaditivos, información incompleta:

• Cuando los artículos se venden en subastas de primer precio, el BPoA es como máximo 2.
• Cuando los artículos se venden en subastas de segundo precio, el BPoA es como máximo 4. Esto es cierto tanto bajo el supuesto fuerte de no oferta excesiva (la suma de las ofertas de cualquier comprador a cualquier paquete es como máximo el valor de ese paquete para el comprador) y bajo el supuesto de que no hay oferta excesiva (la suma esperada de las ofertas ganadoras de cualquier comprador es como máximo el valor ganador esperado de ese comprador).

Subastas secuenciales

En una subasta secuencial, los artículos se venden en subastas consecutivas, una tras otra. El tipo de equilibrio común es el equilibrio perfecto en subjuegos en estrategias puras (SPEPS). Cuando los compradores tienen información completa (es decir, conocen la secuencia de subastas de antemano) y se vende un solo artículo en cada ronda, siempre existe un SPEPS.

El PoA de este SPEPS depende de las funciones de utilidad de los postores y del tipo de subasta utilizada para cada artículo individual.

Los primeros cinco resultados a continuación 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, dos compradores, subastas de 2º precio:

• Cuando al menos un comprador tiene una función de valoración cóncava (rendimientos decrecientes), el PoA 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.

Caso 2: compradores aditivos:

• Con las subastas de segundo precio, el PoA es ilimitado: ¡el bienestar en un SPEPS podría ser arbitrariamente pequeño!

Caso 3: compradores de demanda unitaria:

• Con subastas de primer precio, el PoA es como máximo 2: el bienestar en un SPEPS es siempre al menos la mitad del máximo (si se permiten estrategias mixtas, el PoA es como máximo 4).
• Con las subastas de segundo precio, el PoA vuelve a ser 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: compradores submodulares (tenga en cuenta que la demanda aditiva y la unidad son casos especiales de submodular):

• Tanto en las subastas de primer precio como en las de segundo precio, el PoA 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. Suponga que algunos postores tienen valoraciones aditivas mientras que otros tienen valoraciones de demanda unitaria. En una secuencia de subastas de primer precio, el PoA 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 con la eliminación iterativa de estrategias débilmente dominadas. Esto implica ineficiencia lineal para muchos escenarios naturales, incluyendo:

• compradores con valoraciones sustitutivas brutas,
• valoraciones capacitadas,
• valoraciones presupuestarias adicionales,
• valoraciones aditivas con fuertes restricciones presupuestarias en los pagos.

Caso 6: compradores de demanda unitaria, información incompleta, subastas de 1er precio: el BPoA es como máximo 3.

Subastas que emplean algoritmos codiciosos

Ver

Subastas generalizadas de segundo precio

Ver

Temas relacionados

Los estudios sobre PoA en las subastas han proporcionado información sobre otros escenarios que no están relacionados con las subastas, como los juegos de formación de redes.

Tabla de resumen

[Tabla parcial - contiene solo subastas paralelas - debe completarse]

Multi-subasta	Subasta única	Información	Valoraciones	suposiciones	PoA	Pos.	Comentarios
Paralela	2do precio	completo	submodular	fuerte-no-sobrepujar	2	puro: 1 [siempre existe]
Paralela	2do precio	bayesiano	XOS	fuerte-no-sobrepujar	2
Paralela	2do precio	completo	subaditivo	fuerte-no-sobrepujar	2
Paralela	2do precio	bayesiano	subaditivo	fuerte-no-sobrepujar	> 2, < 2 log(m)
Paralela	1er precio	completo	monótono	Ninguna	puro: 1 [cuando existe]		NE puro = NOSOTROS.
Paralela	1er precio	completo	monótono	Ninguna	mezclado:
Paralela	1er precio	bayesiano	monótono	Ninguna
Paralela	2do precio	completo	monótono	débil-no-sobrepujar	puro: 2 [cuando existe]		NE puro = WE condicional
Paralela	1er precio	bayesiano	subaditivo	Ninguna	2
Paralela	2do precio	bayesiano	subaditivo	débil/fuerte-sin sobreoferta	4