Mecanismo de Vickrey-Clarke-Ggroves

Método de toma de decisiones que maximiza la utilidad.

En el diseño de mecanismos , un mecanismo de Vickrey- Clarke -Groves ( VCG ) es un mecanismo genérico veraz 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 artículos 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}$

Hay 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\longrightarrow 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 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 utilitario. Un mecanismo típico de la familia VCG funciona de la siguiente manera:

1. Pide a los agentes que informen su función de valor. Es decir, cada agente debe informar sobre cada opción . ${\displaystyle i}$ ${\displaystyle v_{i}(x)}$ ${\displaystyle x}$

2. Según 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, basada en 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 demás 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 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 se incentiva al agente 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}}$

La regla del pivote de Clarke

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 llama regla del pivote de Clarke . Con la regla del pivote de Clarke, el importe total pagado por el jugador es:

(bienestar social de los demás si estuviera ausente) - (bienestar social de los demás cuando esté 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 del pivote de Clarke tiene dos propiedades importantes:

• Racionalidad individual : para cada jugador i ,. 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}$
• Sin 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 reciben 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 VCG ponderado

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

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

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

El mecanismo VCG anterior 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 costos

El mecanismo VCG se puede adaptar a situaciones en las que el objetivo es minimizar la suma de costos (en lugar de maximizar la suma de ganancias). Los costos se pueden representar como valores negativos, de modo que la minimización del costo 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 de pivote de Clarke se puede utilizar para este propósito: en el paso 4, a cada agente se le paga el costo total en el que habrían incurrido otros agentes, si el agente no hubiera participado. 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 Vickrey-Clarke-Groves es una aplicación del mecanismo VCG para maximizar el bienestar. Aquí está el conjunto de todas las posibles asignaciones de artículos a los agentes. Cada agente asigna un valor monetario personal a cada paquete 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 Vickrey . Aquí, solo hay un artículo y el conjunto contiene posibles resultados: vender el artículo a uno de los agentes o no venderlo en absoluto. En el paso 3, al agente ganador se le paga 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 hubieran participado). En total, el ganador paga la segunda oferta más alta y los perdedores pagan 0. ${\displaystyle X}$ ${\displaystyle n+1}$ ${\displaystyle n}$

También se puede utilizar un mecanismo VCG en una subasta doble . Es la forma más general de doble subasta compatible con incentivos, ya que puede manejar una subasta combinatoria con funciones de valor arbitrarias en paquetes. Desafortunadamente, no hay equilibrio presupuestario: 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 tiene que subsidiar el comercio.

Proyecto publico

El gobierno quiere decidir si emprender un determinado proyecto. El costo del proyecto es C . Cada ciudadano obtiene un valor diferente del proyecto. El proyecto debe emprenderse si la suma de los valores de todos los ciudadanos es mayor que el costo. Aquí, el mecanismo VCG con la regla pivote de Clarke significa que un ciudadano paga un impuesto distinto de cero por ese proyecto si y sólo si es fundamental, 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 tributario es compatible con los incentivos, pero nuevamente no tiene equilibrio presupuestario: el monto total de impuestos recaudados suele ser menor que C. ^{[1] : 221}

Caminos más rápidos

El problema del camino más rápido 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 en 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 se necesitan para transmitir el mensaje. Nuestro objetivo es enviar el mensaje lo más rápido posible, por eso queremos encontrar el camino con el menor costo total.

Si conocemos el tiempo de transmisión de cada computadora (el costo de cada borde), 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, un ordenador podría decirnos que su tiempo de transmisión es muy largo, para que no le molestemos con nuestros mensajes.

El mecanismo VCG se puede utilizar para resolver este problema. Aquí está el conjunto de todos los caminos posibles; el objetivo es seleccionar un camino con un costo total mínimo. ${\displaystyle X}$ ${\displaystyle x\in X}$

El valor de un agente, , es menos el tiempo que dedicó al 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 demás agentes dedicaron al mensaje (tenga en cuenta que el valor se mide en unidades de tiempo. Suponemos que es posible pagar a los ordenadores en unidades de tiempo). , o que existe una forma estándar de convertir tiempo en dinero). Esto significa que, junto con su propio tiempo invertido, cada agente en realidad pierde el tiempo total que le tomó al mensaje llegar a su destino, por lo que el agente está incentivado a ayudar al mecanismo a lograr el tiempo de transmisión más corto. ${\displaystyle v_{i}(x)}$ ${\displaystyle i\in x}$ ${\displaystyle i\notin x}$

La regla de pivote de Clarke se puede utilizar para hacer que el mecanismo sea individualmente racional: después de pagarnos el costo, cada agente recibe de nosotros un pago positivo, que es igual al tiempo que le habría tomado al mensaje llegar a su destino si el agente no hubiera estado presente. Obviamente, este tiempo es ligeramente mayor que el tiempo requerido cuando el agente está presente, por lo que la ganancia neta de cada agente es débilmente positiva. Intuitivamente, a cada agente se le paga según su contribución marginal a la transmisión.

Otros problemas de gráficos se pueden resolver de manera similar, por ejemplo, árbol de expansión mínimo o coincidencia máxima . Una solución similar se aplica al caso más general en el que cada agente posee algún subconjunto de aristas. ^[3]

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

Unicidad

Un mecanismo VCG implementa una función utilitaria de elección social, 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 suceder al menos tres resultados diferentes ), ${\displaystyle |X|\geq 3}$ ${\displaystyle X}$

entonces sólo se pueden implementar funciones utilitarias ponderadas. ^{[1] : 228, capítulo 12} Entonces, con valoraciones irrestrictas, las funciones de elección social implementadas por los mecanismos VCG son las únicas funciones que pueden implementarse 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 con 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 todos : ${\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 sólo por 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 las subastas combinatorias , calcular la asignación óptima es NP-difícil . ^{[1] : 270–273, capítulo 11}

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

Ver también

• Diseño de mecanismo algorítmico.
• 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. Nisán, 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/juego.1999.0790.