Subasta Vickrey-Clarke-Groves

Una subasta Vickrey–Clarke–Groves (VCG) es un tipo de subasta de oferta sellada de múltiples artículos. Los postores presentan ofertas que informan sus valoraciones de los artículos, sin conocer las ofertas de los otros 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 ofertar sus verdaderas valoraciones , al garantizar que la estrategia óptima para cada postor sea ofertar sus verdaderas valoraciones de los artículos; puede verse socavada por la colusión de los postores y, en particular, en algunas circunstancias, por un solo postor que realiza 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 hacer una asignación socialmente óptima de los artículos, los mecanismos VCG permiten la selección de un resultado socialmente óptimo de un conjunto de resultados posibles. Si es probable que se produzca una colusión entre los postores, la VCG supera a la subasta generalizada de segundo precio tanto en los ingresos producidos para el vendedor como en la eficiencia de asignación. ^[5]

Consideremos 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 según el 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 subastas). Una vez que se realizan todas las ofertas, la subasta se cierra.

El sistema de subasta considera todas las combinaciones posibles de ofertas y se queda con la que maximiza la suma total de las ofertas, con la condición de que no exceda la cantidad total de productos disponibles y que se pueda utilizar como máximo una oferta de cada postor. Los postores que han realizado una oferta exitosa reciben entonces 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 solo 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 en cuestión ) − (lo que otros postores ganadores 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á menor.

Al final de la subasta, la utilidad total se ha maximizado 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 en ausencia de colusión, podemos suponer que la disposición a pagar se ha informado verazmente ya que solo el daño marginal a otros postores se cobrará a cada participante, lo que hace que la información veraz sea una estrategia débilmente dominante . Este tipo de subasta, sin embargo, 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.

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 dada. 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 gana. 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}$

Un postor cuya oferta por un artículo es una "sobreoferta", es decir , gana el artículo, pero paga , que es el costo social de su victoria en el que incurren 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}\}}}$

De hecho, el conjunto de postores distintos de es . Cuando el artículo está disponible, podrían alcanzar el bienestar La obtención del artículo por reduce el conjunto de artículos disponibles a , por lo que el bienestar alcanzable es ahora . 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 los 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}}$

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).}$

Supongamos que se subastan dos manzanas entre tres postores.

• El postor A quiere una manzana y está dispuesto a pagar $5 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 solo una sin la otra.

En primer lugar, el resultado de la subasta se determina maximizando las pujas: las manzanas van al postor A y al postor B, ya que su puja combinada de $5 + $2 = $7 es mayor que la puja por dos manzanas del postor C, que está dispuesto a pagar solo $6. Por lo tanto, después de la subasta, el valor obtenido 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). Nótese 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 que se le exige a A por ganar 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, se resta el segundo valor del primer valor. Por lo tanto, el pago que se le exige a A es $6 − $2 = $4.
• Para el postor B : De manera 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 parte de B es $5. Por lo tanto, el pago requerido a 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 (paga $4 para ganar $5 de utilidad), B está $1 mejor que antes (paga $1 para ganar $2 de utilidad) y C es neutral (no ha ganado nada).

Supongamos que hay dos postores, y , dos artículos, y , y que cada postor puede obtener un artículo. Sea la valoración del postor para el artículo . Supongamos que , , , y . Vemos que tanto como preferirían recibir el artículo ; sin embargo, la asignación socialmente óptima da el artículo al postor (por lo que su valor obtenido es ) y el artículo al postor (por lo que su valor obtenido es ). Por lo tanto, el valor obtenido total 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, la persona seguiría estando asignada a , y por lo tanto la persona no podría ganar nada más. El resultado actual es ; por lo tanto, se le cobra . ${\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, se le asignaría a y tendría una valoración de . El resultado actual es 3; por lo tanto, se le cobra . ${\displaystyle b_{1}}$${\displaystyle t_{1}}$${\displaystyle b_{2}}$${\displaystyle 5}$${\displaystyle b_{1}}$${\displaystyle 5-3=2}$

Consideremos una subasta de casas entre postores, cada uno de los cuales recibirá una casa. , representa el valor que el jugador tiene por la casa . Los resultados posibles 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, entonces solicitamos ofertas y preguntamos a cada jugador cuánto desearía ofertar por la casa . Defina si el postor recibe la casa en la coincidencia . Ahora calcule , una coincidencia bipartita 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^{*}}$

Lo que sigue es una prueba de que es óptimo ofertar las valoraciones reales de los artículos subastados. ^[6]

Para cada postor , sea su verdadera valoración de un artículo y supongamos ( sin pérdida de generalidad ) que gana tras presentar sus verdaderas valoraciones. Entonces, la utilidad neta obtenida por está dada por su propia valoración del artículo que ha ganado, menos el precio que ha pagado: ${\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 , la maximización de la utilidad neta es perseguida por el mecanismo 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 hacerlo más claro, formulemos la diferencia entre la utilidad neta del artículo obtenido mediante una oferta por debajo de la verdadera , y la utilidad neta del postor mediante una oferta no verdadera para el artículo obtenido mediante una 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 corporativa bruta obtenida con la licitación falsa. Pero la asignación a es diferente de la asignación a la que 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}}$

• Mecanismo de Vickrey-Clarke-Groves
• Subasta de Vickrey
• Revelación de preferencias