Subasta de Vickrey – Clarke – Groves - Vickrey–Clarke–Groves auction

Una subasta de Vickrey-Clarke-Groves (VCG) es un tipo de subasta de oferta sellada 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 subastas asigna los artículos de una manera socialmente óptima : cobra a cada individuo el daño que causan a otros postores. Ofrece a los licitadores un incentivo para ofertar sus valoraciones reales , al garantizar que la estrategia óptima para cada licitador sea ofertar sus valoraciones reales de los artículos; puede verse socavada por la colusión de licitadores y, en particular, en algunas circunstancias, por un solo licitador que realiza múltiples 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 socialmente óptima de artículos, los mecanismos de 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, el VCG supera a la subasta generalizada de segundo precio tanto por los ingresos generados por el vendedor como por 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 por 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 posibles combinaciones de ofertas son luego 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. 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 consideración ) - (qué otro ganador los licitadores han ofertado en la combinación actual (mejor) 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, 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 con veracidad, ya que solo se cobrará a cada participante el daño marginal a otros postores, lo que hace que los informes veraces sean 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 de VCG para una combinación de oferta determinada. Es decir, cuánto valora cada persona los artículos que acaba de ganar, sumados a 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 que 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 "sobreoferta", es decir , gana el artículo, pero paga , que es el costo social de su ganancia 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} \}} }$

Explicación

De hecho, el conjunto de licitadores distintos de es . Cuando el artículo está disponible, podrían alcanzar el bienestar . Sin embargo, ganar el artículo 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 lo tanto, la pérdida de bienestar alcanzable que sufren 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} \}} \ derecha).}$

Ejemplos de

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 dólares por ella.
El postor C quiere dos manzanas y está dispuesto a pagar $ 6 por 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. Por lo tanto, después de la subasta, el valor alcanzado por el postor A es de $ 5, por el postor B es de $ 2 y por el postor C es de $ 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. A continuación, 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 lo tanto, el pago requerido de A es $ 6 - $ 2 = $ 4.
Para el postor B : similar al 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 (pagando $ 4 para ganar $ 5 de utilidad), B $ 1 mejor que antes (pagando $ 1 para ganar $ 2 de utilidad) y C es neutral (no ha ganado nada).

Dos postores

Suponga que hay dos postores, y , dos artículos, y , y cada postor puede obtener un artículo. Dejamos ser la valoración del postor para el artículo . Suponga , , , y . Vemos que ambos y preferirían recibir el artículo ; sin embargo, la asignación socialmente óptima le da 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 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, la persona todavía estaría asignada y , por lo tanto, la persona no puede 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; de ahí que se cargue . ${\ Displaystyle b_ {1}}$ ${\ Displaystyle t_ {1}}$ ${\ Displaystyle b_ {2}}$ ${\ Displaystyle 5}$ ${\ Displaystyle b_ {1}}$ ${\ Displaystyle 5-3 = 2}$

Ejemplo # 3

Una subasta de artículos múltiples con postores, casas y valores , que representa el valor que el jugador tiene para la casa . Los posibles resultados se caracterizan por emparejamientos bipartitos , emparejando casas con personas. Si conocemos los valores, entonces maximizar el bienestar social se reduce a calcular una correspondencia bipartita de peso máximo. ${\ Displaystyle n}$ ${\ Displaystyle n}$ ${\ Displaystyle {\ tilde {v}} _ {ij}}$ ${\ Displaystyle i}$ ${\ Displaystyle j}$

Si no conocemos los valores, entonces solicitamos ofertas , preguntando a cada jugador cuánto desearían ofertar por la casa . Defina si el postor recibe casa en el emparejamiento . 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 ^ {*}}$

Optimidad de las ofertas veraces

La siguiente es una prueba de que la oferta de las valoraciones reales de los artículos subastados es óptima.

Para cada postor , sea su verdadera valoración de un artículo , y suponga ( 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 han ganado, menos el precio que han pagado: ${\ Displaystyle b_ {i}}$ ${\ Displaystyle v_ {i}}$ ${\ Displaystyle t_ {i}}$ ${\ Displaystyle b_ {i}}$ ${\ Displaystyle t_ {i}}$ ${\ Displaystyle U_ {i}}$ ${\ Displaystyle b_ {i}}$

{\ Displaystyle {\ begin {alineado} 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 {alineado}}}

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 hacerlo más claro, establezcamos la diferencia entre la utilidad neta del artículo obtenido en una subasta veraz y la utilidad neta del postor en una licitación no veraz para el artículo obtenido en la utilidad verdadera . ${\ Displaystyle U_ {i} -U_ {j} = \ left [v_ {i} + V_ {N \ setminus \ {b_ {i} \}} ^ {M \ setminus \ {t_ {i} \}} \ derecha] - \ izquierda [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 licitación no veraz. Pero la asignación que se asigna a es diferente de la asignación que se asigna a la que obtiene la utilidad corporativa bruta máxima (verdadera). De ahí 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}}$

Languages

In other projects