Subasta de Vickrey–Clarke–Groves

Ajustar Compartir Imprimir Citar

Una subasta de Vickrey-Clarke-Groves (VCG) es un tipo de subasta de oferta sellada de varios artículos. Los oferentes presentan ofertas que informan sus valoraciones por los artículos, sin conocer las ofertas de los otros oferentes. El sistema de subastas asigna los artículos de una manera socialmente óptima: cobra a cada individuo el daño que causa a otros postores. Brinda a los postores un incentivo para ofertar sus verdaderas valoraciones, asegurando que la estrategia óptima para cada postor sea ofertar sus verdaderas valoraciones de los artículos; puede verse socavado por la colusión de los postores y, en particular, en algunas circunstancias, por un solo postor que hace varias ofertas con diferentes nombres. Es una generalización de una subasta de Vickrey para varios artículos.

La subasta lleva el nombre de William Vickrey, Edward H. Clarke y Theodore Groves 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 de VCG intenta hacer una asignación de artículos socialmente óptima, los mecanismos de VCG permiten la selección de un resultado socialmente óptimo de un conjunto de posibles resultados. 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 producidos para el vendedor como en la eficiencia de asignación.

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 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 realizadas todas las pujas, se cierra la subasta.

Todas las combinaciones posibles de ofertas son entonces consideradas por el sistema de subastas, y se mantiene la que maximiza la suma total de ofertas, con la condición de que no exceda la cantidad total de productos disponibles y que como máximo una oferta de cada postor pueda ser usado. Los postores que han realizado una oferta exitosa reciben la cantidad de producto especificada en su oferta. El precio que pagan a cambio, sin embargo, no es la cantidad que ofrecieron inicialmente, sino solo el daño marginal que su oferta ha causado a otros postores (que es, como mucho, 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 ganadora) puede calcularse como: (suma de las ofertas de la subasta de la mejor combinación de ofertas excluyendo al participante en consideración) − (qué otras ofertas ganadoras 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 igual a 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 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 totalmente racionales y en ausencia de colusión, podemos suponer que la disposición a pagar se ha informado con veracidad, 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 $M={t_{1},ldots,t_{m}}$ y cualquier conjunto de postores $N={b_{1},ldots,b_{n}}$ , $V_{N}^{M}$ sea el valor social de la subasta de 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 ganan. Para un postor $bi}$ y un artículo $t_{j}$ , deje que la oferta del postor por el artículo sea $v_{{i}}(t_{{j}})$ . La notación $Asetminus B$ significa el conjunto de elementos de A que no son elementos de B.Asignación

Un pujador $bi}$ cuya puja por un artículo $t_{j}$ es una "sobrepuja", es decir $v_{{i}}(t_{{j}})$ , gana el artículo, pero paga $V_{Nsetminus {b_{i}}}^{M}-V_{Nsetminus {b_{i}}}^{Msetminus {t_{j}}}$ , que es el coste social de su adjudicación en el que incurren el resto de agentes.Explicación

De hecho, el conjunto de postores distintos de $bi}$ es $Nsetminus {b_{i}}$ . Cuando el artículo $t_{j}$ está disponible, pueden alcanzar el bienestar. Sin embargo, $V_{Nsetminus {b_{i}}}^{M}.$ la obtención del artículo $bi}$ reduce el conjunto de artículos disponibles a $Msetminus {t_{j}}$ , por lo que el bienestar alcanzable es ahora $V_{Nsetminus {b_{i}}}^{Msetminus {t_{j}}}$ . La diferencia entre los dos niveles de bienestar es, por tanto, la pérdida de bienestar alcanzable que sufren el resto de los postores, como se preveía, dado que el ganador $bi}$ se quedó con el artículo $t_{j}$ . Esta cantidad depende de las ofertas del resto de agentes y es desconocida para el agente $bi}$ .Utilidad del ganador

El postor ganador cuya oferta es el valor real del artículo, obtiene la máxima utilidad

Ejemplos

Dos artículos, tres postores

Suponga que se subastan dos manzanas entre tres postores.

El postor A quiere una manzana y está dispuesto a pagar $5 por esa manzana.
El postor B quiere una manzana y está dispuesto a pagar $2 por ella.
El postor C quiere dos manzanas y está dispuesto a pagar $6 para tener las dos, pero no está interesado en comprar solo 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 solo $6. Así, después de la subasta, el valor alcanzado por el postor A es de $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 de maximización del bienestar social asignaría ambas manzanas al postor C por un valor social total de $6. Luego, el valor social total de la subasta original excluyendo el valor de A se calcula como $7 − $5 = $2. Finalmente, reste el segundo valor del primer valor. Por 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 de $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 (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).

Dos postores

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

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

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

Ejemplo #3

Considere una subasta de $norte$ casas para los $norte$ postores, cada uno de los cuales recibirá una casa. ${tilde {v}}_{ij}$ , representa el valor que $i$ tiene el jugador por la casa $j$ . 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.

Si no conocemos los valores, entonces solicitamos ofertas ${ tilde {b}}_{ij}$ , preguntando a cada jugador $i$ cuánto desea ofertar por la casa $j$ . Definir $b_{i}(a)={tilde {b}}_{ik}$ si el postor $i$ recibe casa $k$ en la casación $a$ . Ahora calcule $un^{*}$ , una coincidencia bipartita de peso máximo con respecto a las ofertas, y calcule $p_{i}=left[max _{ain A}sum _{jneq i}b_{j}(a)right]-sum _{jneq i}b_{j} (un^{*})$ .

El primer término es otra coincidencia bipartita de ponderación máxima, y el segundo término se puede calcular fácilmente a partir de $un^{*}$ .

Optimalidad de la licitación veraz

La siguiente es una prueba de que ofrecer las valoraciones verdaderas de uno para los artículos subastados es óptimo.

Para cada postor $bi}$ , $v_{i}$ sea su verdadera valoración de un artículo $t_{yo}$ , y supongamos (sin pérdida de generalidad) que $bi}$ gana $t_{yo}$ al presentar sus verdaderas valoraciones. Luego, la utilidad neta $tu_{i}$ obtenida por $bi}$ está dada por su propia valoración del artículo que han ganado, menos el precio que han pagado: ${displaystyle {begin{aligned}U_{i}&=v_{i}-left(V_{Nsetminus {b_{i}}}^{M}-V_{Nsetminus {b_ {i}}}^{Msetminus {t_{i}}}right)\&=sum _{j}v_{j}-sum _{jneq i}v_{j }+V_{Nsetminus {b_{i}}}^{Msetminus {t_{i}}}-V_{Nsetminus {b_{i}}}^{M} &=sum _{j}v_{j}-V_{Nsetminus {b_{i}}}^{Msetminus {t_{i}}}+V_{Nsetminus { b_{i}}}^{Msetminus {t_{i}}}-V_{Nsetminus {b_{i}}}^{M}\&=sum _{j} v_{j}-V_{Nsetminus {b_{i}}.}^{M}end{alineado}}}$

Como $V_{Nsetminus {b_{i}}}^{M}$ es independiente de $v_{i}$ , el mecanismo persigue la maximización de la utilidad neta junto con la maximización de la utilidad bruta corporativa ${ estilo de visualización suma _ {j} v_ {j}}$ para la oferta declarada $v_{i}$ .

Para que quede más claro, formemos la diferencia $U_{i}-U_{j}=left[v_{i}+V_{Nsetminus {b_{i}}}^{Msetminus {t_{i}}}right]- left[v_{j}+V_{Nsetminus {b_{i}}}^{Msetminus {t_{j}}}right]$ entre la utilidad neta $tu_{i}$ del artículo obtenido $bi}$ bajo una oferta veraz y la utilidad neta del postor bajo una oferta no veraz para el artículo obtenido sobre la utilidad verdadera. $v_{i}$ $t_{yo}$ $U_{j}$ $bi}$ $v'_{i}$ $t_{yo}$ $t_{j}$ $v_{j}$

$left[v_{j}+V_{Nsetminus {b_{i}}}^{Msetminus {t_{j}}}right]$ es la utilidad bruta corporativa obtenida con la licitación no veraz. Pero la asignación $t_{j}$ a la que se asigna $bi}$ es diferente de la asignación $t_{yo}$ a $bi}$ la que se obtiene la utilidad corporativa bruta máxima (verdadera). Por lo tanto $left[v_{i}+V_{Nsetminus {b_{i}}}^{Msetminus {t_{i}}}right]-left[v_{j}+V_{ Nsetminus {b_{i}}}^{Msetminus {t_{j}}}right]geq 0$ y $U_{i}geq U_{j}$ qed