En el diseño de mecanismos , una Vickrey- Clarke -Groves ( VCG ) mecanismo es un genérico mecanismo veraz para lograr una solución socialmente óptima. Es una generalización de una subasta de Vickrey-Clarke-Groves . Una subasta de VCG realiza una tarea específica: dividir artículos entre personas. Un mecanismo de 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 posibles resultados.
Existen agentes que tienen diferentes valoraciones para cada resultado. La valoración del agente se representa como una función:
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:
Nuestro objetivo es seleccionar un resultado que maximice la suma de valores, es decir:
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 de su función de valor. Es decir, cada agente debería informar para cada opción .
2. Basado en el vector de informe de los agentes , calcula como anteriormente.
3. Paga, a cada agente , una suma de dinero igual a los valores totales de los otros agentes:
4. Paga, a cada agente , una suma adicional, basada en una función arbitraria de los valores de los otros agentes:
dónde , es decir, es una función que depende únicamente de las valoraciones de los demás agentes.
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 otros 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 otros agentes.
La regla de pivote de Clarke
La función es un parámetro del mecanismo. Cada selección de produce un mecanismo diferente en la familia VCG.
Podríamos tomar, por ejemplo:
- ,
pero luego tendríamos que pagar a los jugadores para que participen en la subasta. Preferiríamos que los jugadores dieran dinero al mecanismo.
Una función alternativa es:
Se llama regla de pivote de Clarke . Con la regla de pivote de Clarke, la cantidad total pagada por el jugador es:
- (bienestar social de otros si estaban ausentes) - (bienestar social de los demás cuando está presente).
Esta es exactamente la externalidad del jugador.. [2]
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 ,. Significa que todos los jugadores obtienen una utilidad positiva al participar en la subasta. Nadie está obligado a pujar.
- Sin transferencias positivas: para cada jugador i ,. El mecanismo no necesita pagar nada a los postores.
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. Entonces, los jugadores permanecen 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 deseemos maximizar una suma ponderada:
dónde es un peso asignado al agente .
El mecanismo VCG de arriba se puede generalizar fácilmente cambiando la función de precio en el paso 3 a:
Minimización de costos
El mecanismo de 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 es equivalente 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 tienen la libertad de elegir si participar o no, debemos asegurarnos de que su pago neto no sea negativo (este requisito se denomina racionalidad individual ). La regla pivote de Clarke se puede utilizar para este propósito: en el paso 4, cada agente se paga el costo total en el que habrían incurrido otros agentes, si el agente no participaría. El pago neto al agente es su contribución marginal a la reducción del costo total.
Aplicaciones
Subastas
La subasta Vickrey-Clarke-Groves es una aplicación del mecanismo VCG para maximizar el bienestar. Aquí,es 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.
Un caso especial muy conocido es el de la subasta de Vickrey . Aquí, solo hay un elemento 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). Con todo, el ganador paga la segunda oferta más alta y los perdedores pagan 0.
También se puede utilizar un mecanismo VCG 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á equilibrado en el presupuesto: 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 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 solo si son fundamentales, es decir, sin su declaración el valor total es menor que C y con su declaración el valor total es más que C . Este plan fiscal es compatible en incentivos, pero de nuevo no es el presupuesto equilibrado - la cantidad total de impuestos recaudados por lo general es 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 en 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. Las 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 la ruta 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 de la ruta más corta . 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.
El mecanismo VCG se puede utilizar para resolver este problema. Aquí,es el conjunto de todos los caminos posibles; el objetivo es seleccionar un camino con un costo total mínimo.
El valor de un agente, , es menos el tiempo que pasó 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 dedicaron al mensaje (tenga en cuenta 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 convertir el tiempo en dinero). Esto significa que, junto con su propio tiempo dedicado, cada agente realmente pierde el tiempo total que le tomó al mensaje llegar a su destino, por lo que el agente está incentivado para ayudar al mecanismo a lograr el tiempo de transmisión más corto.
La regla 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 habría tardado el mensaje en llegar a su destino si el agente hubiera no ha estado presente. Obviamente, este tiempo es débilmente 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 tiene 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 de 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 prueba que, si:
- Las funciones de valoración de los agentes son irrestrictas (cada agente puede tener como función de valor cualquier función de a ), y -
- Hay al menos tres posibles resultados diferentes ( y al menos tres resultados diferentes de puede pasar),
entonces solo se pueden implementar funciones utilitarias ponderadas. [1] : 228, cap.12 Entonces, con las valoraciones sin restricciones, 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 de valor real y no solo preferencias integrales);
- Existe un mecanismo veraz que implementa un cierto funcionar con determinadas funciones de pago ;
- Hay otro mecanismo veraz que implementa el mismo función con diferentes funciones de pago ;
Entonces, existen funciones tal que, para todos :
Es decir, las funciones de precio de los dos mecanismos difieren solo por una función que no depende de la valoración del agente. (solo sobre las valoraciones de los demás agentes).
Esto significa que los mecanismos de VCG son los únicos mecanismos veraces que maximizan el bienestar social utilitario .
Problemas computacionales
Un mecanismo de 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 , el cálculo de la asignación óptima es NP-difícil .
A veces hay 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
Referencias
- ↑ a b c d Vazirani, Vijay V .; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
- ^ Avrim Blum (28 de febrero de 2013). "Algoritmos, juegos y redes - Conferencia 14" (PDF) . Consultado el 28 de diciembre de 2015 .
- ^ a b c Nisan, Noam; Ronen, Amir (2001). "Diseño de mecanismos algorítmicos". Juegos y comportamiento económico . 35 (1–2): 166–196. doi : 10.1006 / game.1999.0790 .