El principio de revelación es un resultado fundamental en el diseño de mecanismos , la teoría de la elección social y la teoría de juegos, que muestra que siempre es posible diseñar una implementación resistente a la estrategia de un mecanismo de toma de decisiones sociales (como un sistema electoral o un mercado ). [1] Puede verse como una especie de imagen especular del teorema de Gibbard . El principio de revelación dice que si una función de elección social puede implementarse utilizando algún mecanismo no veraz (uno en el que los jugadores tienen un incentivo para ser deshonestos), la misma función puede implementarse mediante un mecanismo veraz que tenga el mismo resultado de equilibrio (recompensas). . [2] : 224–225
El principio de revelación muestra que, si bien es imposible diseñar un sistema que siempre sea invulnerable a cualquier estrategia si no sabemos qué estrategia usarían los jugadores, es posible diseñar un sistema que sea resistente a las estrategias para cualquier solución dada. concepto (cuando se conocen las estrategias de los jugadores). [3] [4]
La idea detrás del principio de revelación es que, si sabemos qué estrategia usarán los jugadores en un juego, podemos simplemente pedirles a todos que envíen sus verdaderos pagos o funciones de utilidad ; luego, tomamos esas preferencias y calculamos la estrategia óptima de cada votante antes de ejecutarla para ellos. Este procedimiento significa que un informe honesto de las preferencias es ahora la mejor estrategia posible, porque garantiza que el mecanismo aplicará la estrategia óptima para el jugador.
Ejemplos
Considere el siguiente ejemplo. Hay un determinado elemento que Alice valora y Bob valora como . El gobierno debe decidir quién recibirá ese artículo y en qué términos.
- Una función de elección social es una función que asigna un conjunto de preferencias individuales a un resultado social óptimo. Un ejemplo de función es la regla utilitaria , que dice "dale el artículo a la persona que más lo valore". Denotamos una función de elección social por Soc y su resultado recomendado dado un conjunto de preferencias por Soc(Prefs) .
- Un mecanismo es una regla que relaciona un conjunto de acciones individuales con un resultado social. Un mecanismo Mech induce un juego que denotamos por Game(Mech) .
- Se dice que un mecanismo Mech implementa una función de elección social Soc si, para cada combinación de preferencias individuales, hay un equilibrio de Nash en Game(Mech) en el que el resultado es Soc(Prefs) . Dos mecanismos de ejemplo son:
- "Cada individuo dice un número entre 1 y 10. El artículo se le da al individuo que dice el número más bajo; si ambos dicen el mismo número, entonces el artículo se le da a Alice". Este mecanismo NO implementa la función utilitaria, ya que para cada individuo que quiere el artículo, es una estrategia dominante decir "1" independientemente de su verdadero valor. Esto significa que, en equilibrio, el artículo siempre se le da a Alice, incluso si Bob lo valora más.
- La subasta de oferta cerrada al primer precio es un mecanismo que implementa la función utilitaria. Por ejemplo, si , entonces cualquier perfil de acción en el que Bob oferta más que Alice y ambas ofertas están en el rango es un equilibrio de Nash en el que el artículo va a Bob. Además, si las valoraciones de Alice y Bob son variables aleatorias extraídas independientemente de la misma distribución, entonces existe un equilibrio bayesiano de Nash en el que el artículo va al postor con el valor más alto.
- Un mecanismo directo es un mecanismo en el que el conjunto de acciones disponibles para cada jugador es solo el conjunto de posibles preferencias del jugador.
- Se dice que un Mech de mecanismo directo es compatible con incentivos bayesianos de Nash (BNIC) si existe un equilibrio de juego bayesiano de Nash (Mech) en el que todos los jugadores revelan sus verdaderas preferencias. Algunos ejemplos de mecanismos directos son:
- "Cada individuo dice cuánto valora el artículo. El artículo se le da al individuo que dijo el valor más alto. En caso de empate, el artículo se le da a Alice". Este mecanismo no es BNIC, ya que un jugador que quiere el artículo sale ganando si dice el valor más alto posible, independientemente de su valor real.
- La subasta de oferta cerrada de primer precio tampoco es BNIC, ya que el ganador siempre sale mejor ofertando el valor más bajo que esté ligeramente por encima de la oferta del perdedor.
- Sin embargo, si se conoce la distribución de las valoraciones de los jugadores, entonces existe una variante que es el BNIC e implementa la función utilitaria.
- Además, se sabe que el segundo precio de subasta es el BNIC (incluso es IC en un sentido más estricto: IC de estrategia dominante). Además, implementa la función utilitaria.
Prueba
Supongamos que tenemos un mecanismo arbitrario Mech que implementa Soc .
Construimos un mecanismo directo Mech' que sea veraz e implemente Soc .
Mech' simplemente simula las estrategias de equilibrio de los jugadores en Game( Mech ). es decir
- Mech' pide a los jugadores que informen de sus valoraciones.
- A partir de las valoraciones informadas, Mech' calcula, para cada jugador, su estrategia de equilibrio en Mech .
- Mech' devuelve el resultado devuelto por Mech .
Informar las valoraciones verdaderas en Mech' es como jugar las estrategias de equilibrio en Mech . Por lo tanto, informar las valoraciones verdaderas es un equilibrio de Nash en Mech' , como se desea. Además, los pagos de equilibrio son los mismos, como se desea.
Encontrar soluciones
En el diseño de mecanismos , el principio de revelación es importante para encontrar soluciones. El investigador sólo necesita observar el conjunto de equilibrios caracterizados por la compatibilidad de incentivos . Es decir, si el diseñador del mecanismo quiere implementar algún resultado o propiedad, puede restringir su búsqueda a mecanismos en los que los agentes estén dispuestos a revelar su información privada al diseñador del mecanismo que tiene ese resultado o propiedad. Si no existe tal mecanismo directo y veraz, ningún mecanismo puede implementar este resultado por contraposición . Al reducir el área necesaria para buscar, el problema de encontrar un mecanismo se vuelve mucho más fácil.
Variantes
El principio se presenta en varias versiones correspondientes a diferentes tipos de compatibilidad de incentivos :
El principio de revelación también funciona para equilibrios correlacionados : [ cita necesaria ] para cada dispositivo de coordinación arbitrario , también conocido como correlación, existe otro dispositivo directo para el cual el espacio de estados es igual al espacio de acción de cada jugador. [ jerga ] Luego la coordinación se realiza informando directamente a cada jugador de su acción. [ se necesita aclaración ]
Ver también
Referencias
- ^ ab Gibbard, A. 1973. Manipulación de los esquemas de votación: un resultado general. Econométrica 41, 587–601.
- ^ 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.
- ^ ab Dasgupta, P., Hammond, P. y Maskin, E. 1979. La implementación de reglas de elección social: algunos resultados sobre la compatibilidad de incentivos. Revista de estudios económicos 46, 185–216.
- ^ ab Myerson, R. 1979. La compatibilidad de incentivos y el problema de la negociación. Econométrica 47, 61–73.
- ^ Holmstrom, B. 1977. Sobre incentivos y control en las organizaciones. Doctor. tesis, Universidad de Stanford.