Subasta de Vickrey-Clarke-Groves

Tipo de subasta de artículos múltiples en sobre cerrado

Una subasta Vickrey-Clarke-Groves (VCG) es un tipo de subasta sobre sobre cerrado de varios artículos. Los postores presentan ofertas que informan sus valoraciones de los artículos, sin conocer las ofertas de los demás postores. El sistema de subasta asigna los artículos de una manera socialmente óptima : cobra a cada individuo el daño que causa a otros postores. ^[1] Da a los postores un incentivo para ofrecer sus valoraciones reales , al garantizar que la estrategia óptima para cada postor sea ofrecer sus valoraciones reales de los artículos; puede verse socavado por la colusión de los postores y, en particular, en algunas circunstancias, cuando un solo postor presenta múltiples ofertas con diferentes nombres. Es una generalización de una subasta Vickrey para múltiples artículos.

La subasta lleva el nombre de William Vickrey , ^[2] Edward H. Clarke , ^[3] y Theodore Groves ^[4] por sus artículos que generalizaron sucesivamente la idea.

La subasta VCG es un uso específico del mecanismo VCG más general . Mientras que la subasta VCG intenta realizar una asignación socialmente óptima de artículos, los mecanismos VCG permiten la selección de un resultado socialmente óptimo entre un conjunto de resultados posibles. Si es probable que se produzca colusión entre los postores, la VCG supera a la subasta generalizada de segundo precio tanto en los ingresos generados para el vendedor como en la eficiencia asignativa. ^[5]

Descripción intuitiva

Considere una subasta en la que se vende un conjunto de productos idénticos. Los postores pueden participar en la subasta anunciando el precio máximo que están dispuestos a pagar para recibir N productos. Cada comprador puede declarar más de una oferta, ya que su disposición a pagar por unidad puede ser diferente dependiendo del número total de unidades que reciba. Los postores no pueden ver las ofertas de otras personas en ningún momento ya que están selladas (solo visibles para el sistema de subasta). Una vez realizadas todas las pujas, se cierra la subasta.

Luego, todas las combinaciones posibles de ofertas son consideradas por el sistema de subastas, y se mantiene la que maximiza la suma total de ofertas, con la condición de que no supere la cantidad total de productos disponibles y que como máximo se pueda realizar una oferta de cada postor. ser usado. Los postores que hayan realizado una oferta exitosa recibirán la cantidad de producto especificada en su oferta. Sin embargo, el precio que pagan a cambio no es la cantidad que habían ofertado inicialmente, sino sólo el daño marginal que su oferta ha causado a otros postores (que es, como máximo, tan alto como su oferta original).

Este daño marginal causado a otros participantes (es decir, el precio final pagado por cada individuo con una oferta exitosa) se puede calcular como: (suma de las ofertas de la subasta de la mejor combinación de ofertas excluyendo al participante bajo consideración ) − (qué otros participantes ganadores los postores han ofertado en la (mejor) combinación actual de ofertas). Si la suma de las ofertas de la segunda mejor combinación de ofertas es la misma que la de la mejor combinación, entonces el precio pagado por los compradores será el mismo que su oferta inicial. En todos los demás casos, el precio pagado por los compradores será inferior.

Al final de la subasta, la utilidad total se maximiza ya que todos los bienes se han atribuido a las personas con la mayor disposición a pagar combinada. Si los agentes son completamente racionales y no hay colusión, podemos suponer que la disposición a pagar se ha informado con sinceridad, ya que solo se cobrará a cada participante el daño marginal a otros postores, lo que hace que la información veraz sea una estrategia débilmente dominante . Sin embargo, este tipo de subasta no maximizará los ingresos del vendedor a menos que la suma de las ofertas de la segunda mejor combinación de ofertas sea igual a la suma de las ofertas de la mejor combinación de ofertas.

Descripción formal

Notación

Para cualquier conjunto de artículos subastados y cualquier conjunto de postores , sea el valor social de la subasta VCG para una combinación de ofertas determinada. Es decir, cuánto valora cada persona los artículos que acaba de ganar, sumados entre todos. El valor del artículo es cero si no ganan. Para un postor y un artículo , sea la oferta del postor por el artículo . La notación significa el conjunto de elementos de A que no son elementos de B. ${\displaystyle M=\{t_{1},\ldots ,t_{m}\}}$ ${\displaystyle N=\{b_{1},\ldots ,b_{n}\}}$ ${\displaystyle V_{N}^{M}}$ ${\displaystyle b_{i}}$ ${\displaystyle t_{j}}$ ${\displaystyle v_{i}(t_{j})}$ ${\displaystyle A\setminus B}$

Asignación

Un postor cuya oferta por un artículo es una "sobrepuja", es decir , gana el artículo, pero paga , que es el coste social de su ganancia en el que incurre el resto de los agentes. ${\displaystyle b_{i}}$ ${\displaystyle t_{j}}$ ${\displaystyle v_{i}(t_{j})}$ ${\displaystyle V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}}$

Explicación

De hecho, el conjunto de postores distintos a es . Cuando el artículo está disponible, podrían alcanzar el bienestar. La obtención del artículo reduce el conjunto de artículos disponibles a , por lo que el bienestar alcanzable ahora es . La diferencia entre los dos niveles de bienestar es, por tanto, la pérdida de bienestar alcanzable sufrida por el resto de los postores, como se predijo, dado que el ganador obtuvo el artículo . Esta cantidad depende de las ofertas del resto de agentes y es desconocida para el agente . ${\displaystyle b_{i}}$ ${\displaystyle N\setminus \{b_{i}\}}$ ${\displaystyle t_{j}}$ ${\displaystyle V_{N\setminus \{b_{i}\}}^{M}.}$ ${\displaystyle b_{i}}$ ${\displaystyle M\setminus \{t_{j}\}}$ ${\displaystyle V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}}$ ${\displaystyle b_{i}}$ ${\displaystyle t_{j}}$ ${\displaystyle b_{i}}$

Utilidad del ganador

El postor ganador cuya oferta es el valor real del artículo obtiene la máxima utilidad . ${\displaystyle A}$ ${\displaystyle t_{j}}$ ${\displaystyle v_{i}(t_{j})=A,}$ ${\displaystyle A-\left(V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right).}$

Ejemplos

Dos artículos, tres postores

Supongamos que se subastan dos manzanas entre tres postores.

• El postor A quiere una manzana y está dispuesto a pagar 5 dólares por ella.
• El postor B quiere una manzana y está dispuesto a pagar 2 dólares por ella.
• El postor C quiere dos manzanas y está dispuesto a pagar $6 para tener ambas, pero no está interesado en comprar sólo una sin la otra.

Primero, el resultado de la subasta se determina maximizando las ofertas: las manzanas van al postor A y al postor B, ya que su oferta combinada de $5 + $2 = $7 es mayor que la oferta por dos manzanas del postor C, que está dispuesto a pagar sólo $6. Por lo tanto, después de la subasta, el valor logrado por el postor A es $5, por el postor B es $2 y por el postor C es $0 (ya que el postor C no obtiene nada). Tenga en cuenta que la determinación de los ganadores es esencialmente un problema de mochila .

A continuación, la fórmula para decidir los pagos da:

• Para el postor A : El pago por ganar requerido de A se determina de la siguiente manera: Primero, en una subasta que excluye al postor A, el resultado que maximiza el bienestar social asignaría ambas manzanas al postor C por un valor social total de $6. A continuación, el valor social total de la subasta original excluyendo el valor de A se calcula como $7 − $5 = $2. Finalmente, resta el segundo valor del primer valor. Por lo tanto, el pago requerido de A es $6 − $2 = $4.
• Para el postor B : similar a lo anterior, el mejor resultado para una subasta que excluye al postor B asigna ambas manzanas al postor C por $6. El valor social total de la subasta original menos la porción de B es $5. Por lo tanto, el pago requerido de B es $6 − $5 = $1.
• Finalmente, el pago para el postor C es (($5 + $2) − ($5 + $2)) = $0.

Después de la subasta, A está $1 mejor que antes (pagando $4 para ganar $5 de utilidad), B está $1 mejor que antes (pagando $1 para ganar $2 de utilidad) y C es neutral (no ha ganado nada).

Dos postores

Supongamos que hay dos postores, y , dos artículos, y , y a cada postor se le permite obtener un artículo. Dejamos ser la valoración del postor para el artículo . Supongamos , , y . Vemos que ambos preferirían recibir el artículo ; sin embargo, la asignación socialmente óptima le da un artículo al postor (por lo que su valor alcanzado es ) y un artículo al postor (por lo que su valor alcanzado es ). Por tanto, el valor total alcanzado es , que es óptimo. ${\displaystyle b_{1}}$ ${\displaystyle b_{2}}$ ${\displaystyle t_{1}}$ ${\displaystyle t_{2}}$ ${\displaystyle v_{i,j}}$ ${\displaystyle b_{i}}$ ${\displaystyle t_{j}}$ ${\displaystyle v_{1,1}=10}$ ${\displaystyle v_{1,2}=5}$ ${\displaystyle v_{2,1}=5}$ ${\displaystyle v_{2,2}=3}$ ${\displaystyle b_{1}}$ ${\displaystyle b_{2}}$ ${\displaystyle t_{1}}$ ${\displaystyle t_{1}}$ ${\displaystyle b_{1}}$ ${\displaystyle 10}$ ${\displaystyle t_{2}}$ ${\displaystyle b_{2}}$ ${\displaystyle 3}$ ${\displaystyle 13}$

Si la persona no estuviera en la subasta, aún sería asignada a y, por lo tanto, no podría ganar nada más. El resultado actual es ; por lo tanto se carga . ${\displaystyle b_{2}}$ ${\displaystyle b_{1}}$ ${\displaystyle t_{1}}$ ${\displaystyle b_{1}}$ ${\displaystyle 10}$ ${\displaystyle b_{2}}$ ${\displaystyle 10-10=0}$

Si la persona no estuviera en la subasta, sería asignada y tendría valoración . El resultado actual es 3; por lo tanto se carga . ${\displaystyle b_{1}}$ ${\displaystyle t_{1}}$ ${\displaystyle b_{2}}$ ${\displaystyle 5}$ ${\displaystyle b_{1}}$ ${\displaystyle 5-3=2}$

Ejemplo #3

Considere una subasta de casas entre postores, cada uno de los cuales recibirá una casa. , representa el valor que el jugador tiene para la casa . Los posibles resultados se caracterizan por emparejamientos bipartitos que emparejan casas con personas. Si conocemos los valores, entonces maximizar el bienestar social se reduce a calcular un emparejamiento bipartito de peso máximo. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\tilde {v}}_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$

Si no conocemos los valores, solicitamos ofertas y preguntamos a cada jugador cuánto desearía ofertar por la casa . Definir si el postor recibe casa en el casamiento . Ahora calcule , un emparejamiento bipartito de peso máximo con respecto a las ofertas, y calcule ${\displaystyle {\tilde {b}}_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle b_{i}(a)={\tilde {b}}_{ik}}$ ${\displaystyle i}$ ${\displaystyle k}$ ${\displaystyle a}$ ${\displaystyle a^{*}}$

${\displaystyle p_{i}=\left[\max _{a\in A}\sum _{j\neq i}b_{j}(a)\right]-\sum _{j\neq i}b_{j}(a^{*})}$.

El primer término es otra coincidencia bipartita de peso máximo y el segundo término se puede calcular fácilmente a partir de . ${\displaystyle a^{*}}$

Optimidad de una oferta veraz

La siguiente es una prueba de que ofrecer las valoraciones reales de los artículos subastados es óptimo. ^[6]

Para cada postor , sea su verdadera valoración de un artículo , y supongamos ( sin pérdida de generalidad ) que gana al presentar sus verdaderas valoraciones. Entonces, la utilidad neta obtenida viene dada por su propia valoración del artículo que ganaron, menos el precio que pagaron: ${\displaystyle b_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle t_{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle t_{i}}$ ${\displaystyle U_{i}}$ ${\displaystyle b_{i}}$

${\displaystyle {\begin{aligned}U_{i}&=v_{i}-\left(V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}\right)\\&=\sum _{j}v_{j}-\sum _{j\neq i}v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}-V_{N\setminus \{b_{i}\}}^{M}\\&=\sum _{j}v_{j}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}-V_{N\setminus \{b_{i}\}}^{M}\\&=\sum _{j}v_{j}-V_{N\setminus \{b_{i}\}.}^{M}\end{aligned}}}$

Como es independiente de , el mecanismo persigue la maximización de la utilidad neta junto con la maximización de la utilidad bruta corporativa para la oferta declarada . ${\displaystyle V_{N\setminus \{b_{i}\}}^{M}}$ ${\displaystyle v_{i}}$ ${\displaystyle \sum _{j}v_{j}}$ ${\displaystyle v_{i}}$

Para que quede más claro, formemos la diferencia entre la utilidad neta del artículo obtenido con una oferta veraz y la utilidad neta del postor con una oferta no veraz para el artículo obtenido con la utilidad verdadera . ${\displaystyle U_{i}-U_{j}=\left[v_{i}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}\right]-\left[v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right]}$ ${\displaystyle U_{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle t_{i}}$ ${\displaystyle U_{j}}$ ${\displaystyle b_{i}}$ ${\displaystyle v'_{i}}$ ${\displaystyle t_{i}}$ ${\displaystyle t_{j}}$ ${\displaystyle v_{j}}$

${\displaystyle \left[v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right]}$es la utilidad bruta corporativa obtenida con la subasta no veraz. Pero la asignación a es diferente de la asignación a quien obtiene la máxima (verdadera) utilidad corporativa bruta. Por lo tanto y qed ${\displaystyle t_{j}}$ ${\displaystyle b_{i}}$ ${\displaystyle t_{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle \left[v_{i}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}\right]-\left[v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right]\geq 0}$ ${\displaystyle U_{i}\geq U_{j}}$

Ver también

• Mecanismo de Vickrey-Clarke-Ggroves
• subasta vicrey
• Revelación de preferencia ^{[ se necesita desambiguación ]}

Referencias

1. von Ahn, Luis (13 de octubre de 2011). "Búsqueda patrocinada" (PDF) . 15–396: Notas del curso sobre la ciencia de la Web . Universidad de Carnegie mellon. Archivado desde el original (PDF) el 6 de marzo de 2015 . Consultado el 13 de abril de 2015 .
2. Vickrey, William (1961). "Contraespeculación, subastas y licitaciones competitivas en sobre cerrado". La Revista de Finanzas . 16 (1): 8–37. doi :10.1111/j.1540-6261.1961.tb02789.x.
3. Clarke, E. (1971). "Precios multiparte de bienes públicos". Elección pública . 11 (1): 17–33. doi :10.1007/bf01726210. S2CID  154860771.
4. Arboledas, T. (1973). "Incentivos en Equipos". Econométrica . 41 (4): 617–631. doi :10.2307/1914085. JSTOR  1914085.
5. Decarolis, Francesco; Goldmanis, Maris; Penta, Antonio (2017). "Agencias de marketing y pujas colusorias en subastas de publicidad online". Oficina Nacional de Investigación Económica . Serie de documentos de trabajo. doi :10.3386/w23962. S2CID  44056837.
6. Blum, Avrim (28 de febrero de 2013). "Algoritmos, juegos y redes - Conferencia 14" (PDF) . Consultado el 28 de diciembre de 2023 .