Mecanismo de Vickrey-Clarke-Groves

En el diseño de mecanismos , el mecanismo Vickrey - Clarke -Groves ( VCG ) es un mecanismo genérico y veraz para lograr una solución socialmente óptima siempre que haya transferencias monetarias disponibles. Generaliza la subasta Vickrey-Clarke-Groves en un mecanismo de propósito general para la elección social , que puede usarse para seleccionar cualquier resultado de un conjunto de resultados posibles. ^{[ 1 ] : 216-233} Sin embargo, el mecanismo VCG también tiene varios problemas que le impiden resolver completamente el problema de los bienes públicos , incluida su vulnerabilidad a la colusión ^{[ 2 ]} y el problema de que los participantes no paguen sus ofertas.

Hay un conjunto${\displaystyle X}$de posibles resultados.

Hay${\displaystyle n}$agentes, cada uno de los cuales tiene un conjunto de valoraciones de resultados. La valoración del agente${\displaystyle i}$se representa como una función:

${\displaystyle v_{i}:X\to \mathbb {R} _{+}}$

que expresa el valor que tiene para cada alternativa, en términos monetarios.

Se supone que los agentes tienen funciones de utilidad cuasilineales ; esto significa que, si el resultado es${\displaystyle x}$y además el agente recibe un pago${\displaystyle p_{i}}$(positivo o negativo), entonces la utilidad total del agente${\displaystyle i}$es:

${\displaystyle u_{i}:=v_{i}(x)+p_{i}}$

Nuestro objetivo es seleccionar un resultado que maximice la suma de los valores, es decir:

${\displaystyle x^{opt}(v)=\arg \max _{x\in X}\sum _{i=1}^{n}v_{i}(x)}$

En otras palabras, nuestra función de elección social es utilitaria .

La familia VCG es una familia de mecanismos que implementa la función de bienestar utilitarista. Un mecanismo típico de la familia VCG funciona de la siguiente manera:

1. Les pide a los agentes que informen su función de valor . Es decir, cada agente${\displaystyle i}$debería informar${\displaystyle v_{i}(x)}$para cada opción${\displaystyle x}$.

2. Basado en el vector de informes de los agentes${\displaystyle v}$, calcula${\displaystyle x^{*}=x^{opt}(v)}$como se indicó anteriormente.

3. Le conviene a cada agente.${\displaystyle i}$una suma de dinero igual al valor total de los demás agentes:

${\displaystyle p_{i}:=\sum _{j\neq i}v_{j}(x^{*})}$

4. Le conviene a cada agente.${\displaystyle i}$, una suma adicional, basada en una función arbitraria de los valores de los demás agentes:

${\displaystyle p_{i}+h_{i}(v_{-i})}$

dónde ${\displaystyle v_{-i}=(v_{1},\dots ,v_{i-1},v_{i+1},\dots ,v_{n})}$, eso es,${\displaystyle h_{i}}$es una función que depende únicamente de las valoraciones de los demás agentes.

Cada mecanismo de la familia VCG es un mecanismo veraz , es decir, un mecanismo en el que ofertar por la valoración real es una estrategia dominante .

La clave está en el paso 3. Al agente se le paga el valor total de los demás agentes; por lo tanto, sumado a su propio valor, el bienestar total del agente es exactamente igual al bienestar total de la sociedad. En consecuencia, los incentivos del agente están alineados con los de la sociedad y se le incentiva a ser honesto para ayudar al mecanismo a alcanzar su objetivo.

La función${\displaystyle h_{i}}$, en el paso 4, no afecta los incentivos del agente, ya que depende únicamente de las declaraciones de los demás agentes.

La función${\displaystyle h_{i}}$es un parámetro del mecanismo. Cada selección de${\displaystyle h_{i}}$produce un mecanismo diferente en la familia VCG.

Podríamos tomar, por ejemplo:

${\displaystyle h_{i}(v_{-i})=0}$,

Pero entonces tendríamos que pagar a los jugadores para que participen en la subasta. Preferiríamos que los jugadores aportaran dinero al mecanismo.

Una función alternativa es:

${\displaystyle h_{i}(v_{-i})=-\max _{x\in X}\sum _{j\neq i}v_{j}(x)}$

Se denomina regla del pivote de Clarke . Con la regla del pivote de Clarke, la cantidad total pagada por el jugador es:

(bienestar social de los demás si${\displaystyle i}$estaban ausentes) - (bienestar social de los demás cuando${\displaystyle i}$está presente).

Esta es precisamente la externalidad del jugador.${\displaystyle i}$. ^{[ 3 ]}

Cuando las valoraciones de todos los agentes son débilmente positivas, la regla del pivote de Clarke tiene dos propiedades importantes:

• Racionalidad individual : para cada jugador i ,${\displaystyle v_{i}(x)+p_{i}\geq 0}$Esto significa que todos los jugadores obtienen un beneficio al participar en la subasta. Nadie está obligado a pujar.
• No hay transferencias positivas: para cada jugador i ,${\displaystyle p_{i}\leq 0}$El mecanismo no tiene que pagar nada a los licitadores.

Esto convierte al mecanismo VCG en un juego en el que todos ganan : los jugadores obtienen los resultados que desean y pagan una cantidad menor a su ganancia. Por lo tanto, los jugadores obtienen una ganancia neta positiva y el mecanismo recibe un pago neto positivo.

En lugar de maximizar la suma de valores, podríamos querer maximizar una suma ponderada :

${\displaystyle x^{opt}(v)=\arg \max _{x\in X}\sum _{i=1}^{n}w_{i}v_{i}(x)}$

dónde${\displaystyle w_{i}}$es un peso asignado al agente${\displaystyle i}$.

El mecanismo VCG descrito anteriormente se puede generalizar fácilmente cambiando la función de precio en el paso 3 a:

${\displaystyle p_{i}:={1 \over w_{i}}\sum _{j\neq i}w_{j}v_{j}(x^{*})}$

El mecanismo VCG puede adaptarse a situaciones en las que el objetivo es minimizar la suma de los costos (en lugar de maximizar la suma de las ganancias). Los costos pueden representarse como valores negativos, de modo que la minimización de los costos equivale a la maximización de los valores.

Los pagos en el paso 3 son negativos: cada agente tiene que pagar el costo total incurrido por todos los demás agentes. Si los agentes son libres de elegir si participan o no, entonces debemos asegurarnos de que su pago neto no sea negativo (este requisito se llama racionalidad individual ). La regla pivote de Clarke se puede utilizar para este propósito: en el paso 4, cada agente${\displaystyle i}$se le paga el costo total que habrían incurrido otros agentes, si el agente${\displaystyle i}$no participaría. El pago neto al agente${\displaystyle i}$es su contribución marginal a la reducción del costo total.

Un mecanismo VCG implementa una función de elección social utilitaria , una función que maximiza una suma ponderada de valores (también llamada maximizador afín ). El teorema de Roberts demuestra que, si:

• Las funciones de valoración de los agentes no están restringidas (cada agente puede tener como función de valor cualquier función de${\displaystyle X}$a${\displaystyle \mathbb {R} }$), y -
• Hay al menos tres resultados posibles diferentes (${\displaystyle |X|\geq 3}$y al menos tres resultados diferentes de${\displaystyle X}$puede suceder),

Entonces, solo se pueden implementar funciones utilitarias ponderadas. ^{[ 1 ] : 228, cap. 12} Así que, con valoraciones no restringidas, las funciones de elección social implementadas por los mecanismos VCG son las únicas funciones que se pueden implementar de manera veraz.

Además, las funciones de precios de los mecanismos VCG también son únicas en el siguiente sentido. ^{[ 1 ] : 230–231} Si:

• Los dominios de las valoraciones de los agentes son conjuntos conexos (en particular, los agentes pueden tener preferencias de valor real y no solo preferencias enteras);
• Existe un mecanismo veraz que implementa un determinado${\displaystyle Outcome}$funcionar con ciertas funciones de pago${\displaystyle p_{1},\dots ,p_{n}}$;
• Existe otro mecanismo veraz que implementa lo mismo.${\displaystyle Outcome}$función con diferentes funciones de pago${\displaystyle p'_{1},\dots ,p'_{n}}$;

Entonces, existen funciones${\displaystyle h_{1},\dots ,h_{n}}$de tal manera que, para todos${\displaystyle i}$:

${\displaystyle p'_{i}(v_{i},v_{-i})=p_{i}(v_{i},v_{-i})+h_{i}(v_{-i})}$

Es decir, las funciones de precio de los dos mecanismos difieren únicamente en una función que no depende de la valoración del agente.${\displaystyle v_{i}}$(solo en función de las valoraciones de los demás agentes).

Esto significa que los mecanismos VCG son los únicos mecanismos veraces que maximizan el bienestar social utilitarista .

Un mecanismo VCG debe calcular el resultado óptimo, basándose en los informes de los agentes (paso 2 anterior). En algunos casos, este cálculo es computacionalmente difícil. Por ejemplo, en las subastas combinatorias , calcular la asignación óptima es NP-difícil . ^{[ 1 ] : 270–273, cap. 11}

A veces existen algoritmos de aproximación para el problema de optimización , pero el uso de dicha aproximación podría hacer que el mecanismo no sea veraz. ^{[ 4 ]}

• Diseño de mecanismos algorítmicos
• Compatibilidad de incentivos
• Votación cuadrática