Mecanismo de Vickrey-Clarke-Groves

Método de toma de decisiones que maximiza la utilidad

En el diseño de mecanismos , un mecanismo Vickrey– Clarke –Groves ( VCG ) es un mecanismo veraz genérico para lograr una solución socialmente óptima. Es una generalización de una subasta Vickrey–Clarke–Groves . Una subasta VCG realiza una tarea específica: dividir elementos entre personas. Un mecanismo VCG es más general: se puede utilizar para seleccionar cualquier resultado de un conjunto de resultados posibles. ^{[1] : 216–233}

Notación

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

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

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

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

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

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

Nuestro objetivo es seleccionar un resultado que maximice la suma de 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 .

Familia de soluciones

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. Se solicita a los agentes que informen su función de valor, es decir, cada agente debe informar para cada opción . ${\displaystyle i}$ ${\displaystyle v_{i}(x)}$ ${\displaystyle x}$

2. Con base en el vector de informe de los agentes , se calcula como se indica arriba. ${\displaystyle v}$ ${\displaystyle x^{*}=x^{opt}(v)}$

3. Paga a cada agente una suma de dinero igual a los valores totales de los demás agentes: ${\displaystyle i}$

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

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

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

donde , es decir, es una función que depende únicamente de las valoraciones de los otros agentes. ${\displaystyle v_{-i}=(v_{1},\dots ,v_{i-1},v_{i+1},\dots ,v_{n})}$ ${\displaystyle h_{i}}$

Veracidad

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

El truco está en el paso 3. Al agente se le paga el valor total de los demás agentes; por lo tanto, junto con su propio valor, el bienestar total del agente es exactamente igual al bienestar total de la sociedad. Por lo tanto, los incentivos del agente están alineados con los de la sociedad y el agente se ve incentivado a ser veraz para ayudar al mecanismo a lograr su objetivo.

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

ElClarkeregla de pivote

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

Podríamos tomar, por ejemplo:

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

Pero entonces tendríamos que pagar a los jugadores para que participaran en la subasta. Preferiríamos que los jugadores dieran 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 de pivote de Clarke . Con la regla de pivote de Clarke, la cantidad total pagada por el jugador es:

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

Ésta es exactamente la externalidad del jugador . ^[2] ${\displaystyle i}$

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

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

Esto hace que el mecanismo VCG sea un juego en el que todos ganan : los jugadores obtienen los resultados que desean y pagan una cantidad menor que su ganancia. De modo que los jugadores se quedan con una ganancia neta positiva y el mecanismo obtiene un pago neto positivo.

Mecanismo de VCG ponderado

En lugar de maximizar la suma de valores, es posible que queramos maximizar una suma ponderada:

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

donde es un peso asignado al agente . ${\displaystyle w_{i}}$ ${\displaystyle i}$

El mecanismo VCG mencionado 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^{*})}$

Minimización de costes

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 sea equivalente a la maximización de los valores.

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

Aplicaciones

Subastas

La subasta de Vickrey-Clarke-Groves es una aplicación del mecanismo VCG para maximizar el bienestar. Aquí, se encuentra el conjunto de todas las posibles asignaciones de artículos a los agentes. Cada agente asigna un valor monetario personal a cada conjunto de artículos y el objetivo es maximizar la suma de los valores de todos los agentes. ${\displaystyle X}$

Un caso especial muy conocido es la subasta de Vickrey . En ella, solo hay un artículo y el conjunto contiene posibles resultados: vender el artículo a uno de los agentes o no venderlo. En el paso 3, el agente ganador recibe 0 (ya que el valor total de los demás es 0) y los perdedores reciben un pago igual al valor declarado del ganador. En el paso 4, el ganador paga la segunda oferta más alta (el valor total de los demás si no hubiera participado) y los perdedores pagan el valor declarado del ganador (el valor total de los demás si no hubiera participado). En total, el ganador paga la segunda oferta más alta y los perdedores pagan 0. ${\displaystyle X}$ ${\displaystyle n+1}$ ${\displaystyle n}$

Un mecanismo VCG también puede utilizarse en una subasta doble . Es la forma más general de subasta doble compatible con incentivos, ya que puede manejar una subasta combinatoria con funciones de valor arbitrarias en paquetes. Desafortunadamente, no está equilibrada en términos presupuestarios: el valor total pagado por los compradores es menor que el valor total recibido por los vendedores. Por lo tanto, para que funcione, el subastador debe subsidiar el comercio.

Proyecto público

El gobierno quiere decidir si emprende o no un determinado proyecto. El coste del proyecto es C . Cada ciudadano obtiene un valor diferente del proyecto. El proyecto debería emprenderse si la suma de los valores de todos los ciudadanos es mayor que el coste. En este caso, el mecanismo VCG con la regla de pivote de Clarke significa que un ciudadano paga un impuesto distinto de cero por ese proyecto si y solo si es pivote, es decir, sin su declaración el valor total es menor que C y con su declaración el valor total es mayor que C . Este esquema impositivo es compatible con los incentivos, pero nuevamente no está equilibrado con el presupuesto: la cantidad total de impuestos recaudados suele ser menor que C . ^{[1] : 221}

Caminos más rápidos

El problema de la ruta más rápida es un problema de minimización de costos. ^[3] El objetivo es enviar un mensaje entre dos puntos de una red de comunicación, que se modela como un gráfico. Cada computadora de la red se modela como un borde en el gráfico. Diferentes computadoras tienen diferentes velocidades de transmisión, por lo que cada borde de la red tiene un costo numérico igual a la cantidad de milisegundos que tarda en transmitir el mensaje. Nuestro objetivo es enviar el mensaje lo más rápido posible, por lo que queremos encontrar la ruta con el menor costo total.

Si conocemos el tiempo de transmisión de cada computadora (el costo de cada arista), entonces podemos usar un algoritmo estándar para resolver el problema del camino más corto . Si no conocemos los tiempos de transmisión, entonces tenemos que pedirle a cada computadora que nos diga su tiempo de transmisión. Pero las computadoras tienen sus propios intereses egoístas, por lo que es posible que no nos digan la verdad. Por ejemplo, una computadora podría decirnos que su tiempo de transmisión es muy grande, para que no la molestemos con nuestros mensajes.

Para resolver este problema se puede utilizar el mecanismo VCG, en el que se encuentra el conjunto de todos los caminos posibles; el objetivo es seleccionar el camino con el menor costo total. ${\displaystyle X}$ ${\displaystyle x\in X}$

El valor de un agente, , es menos el tiempo que ha empleado en el mensaje: es negativo si y es cero si . El pago en el paso 3 es negativo: cada agente debe pagarnos el tiempo total que los otros agentes emplearon en el mensaje (nótese que el valor se mide en unidades de tiempo. Suponemos que es posible pagar a las computadoras en unidades de tiempo, o que existe una forma estándar de traducir el tiempo a dinero). Esto significa que, junto con su propio tiempo empleado, cada agente en realidad pierde el tiempo total que tardó el mensaje en llegar a su destino, por lo que el agente se ve incentivado a ayudar al mecanismo a lograr el menor tiempo de transmisión. ${\displaystyle v_{i}(x)}$ ${\displaystyle i\in x}$ ${\displaystyle i\notin x}$

La regla del pivote de Clarke puede utilizarse para hacer que el mecanismo sea racional a nivel individual: después de pagarnos el coste, cada agente recibe de nosotros un pago positivo, que es igual al tiempo que habría tardado el mensaje en llegar a su destino si el agente no hubiera estado presente. Obviamente, este tiempo es ligeramente mayor que el tiempo necesario cuando el agente está presente, por lo que la ganancia neta de cada agente es ligeramente positiva. Intuitivamente, cada agente recibe un pago de acuerdo con su contribución marginal a la transmisión.

Otros problemas de grafos se pueden resolver de manera similar, por ejemplo, árbol de expansión mínima o coincidencia máxima . Una solución similar se aplica al caso más general donde cada agente contiene algún subconjunto de los bordes. ^[3]

Para ver otro ejemplo, donde el mecanismo VCG proporciona una aproximación subóptima, consulte Programación de trabajos veraz .

Unicidad

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 tienen restricciones (cada agente puede tener como función de valor cualquier función desde hasta ), y - ${\displaystyle X}$ ${\displaystyle \mathbb {R} }$
• Hay al menos tres resultados posibles diferentes ( y pueden ocurrir al menos tres resultados diferentes ), ${\displaystyle |X|\geq 3}$ ${\displaystyle X}$

Entonces, sólo se pueden implementar funciones utilitarias ponderadas. ^{[1] : 228, cap.12} Por lo tanto, con valoraciones sin restricciones, 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 precio 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 conectados (en particular, los agentes pueden tener preferencias de valores reales y no sólo preferencias integrales);
• Existe un mecanismo veraz que implementa una determinada función con determinadas funciones de pago ; ${\displaystyle Outcome}$ ${\displaystyle p_{1},\dots ,p_{n}}$
• Existe otro mecanismo veraz que implementa la misma función con diferentes funciones de pago ; ${\displaystyle Outcome}$ ${\displaystyle p'_{1},\dots ,p'_{n}}$

Entonces, existen funciones tales que, para todo : ${\displaystyle h_{1},\dots ,h_{n}}$ ${\displaystyle i}$

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

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

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

Problemas computacionales

Un mecanismo VCG tiene que 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 subastas combinatorias , calcular la asignación óptima es NP-hard . ^{[1] : 270–273, cap.11}

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

Véase también

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

Referencias

1. Vazirani, Vijay V .; Nisán, Noam ; Jardín rugoso, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
2. Avrim Blum (28 de febrero de 2013). "Algoritmos, juegos y redes - Conferencia 14" (PDF) . Consultado el 28 de diciembre de 2015 .
3. Nisan, Noam; Ronen, Amir (2001). "Diseño de mecanismos algorítmicos". Juegos y comportamiento económico . 35 (1–2): 166–196. CiteSeerX 10.1.1.16.7473 . doi :10.1006/game.1999.0790.