Principio de revelación

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 con algún mecanismo no honesto (uno en el que los jugadores tienen un incentivo para mentir), la misma función puede implementarse mediante un mecanismo compatible con los incentivos (que promueva la honestidad) con el mismo resultado de equilibrio (recompensas). ^[2]^{: 224–225}

El principio de revelación muestra que, si bien el teorema de Gibbard prueba que es imposible diseñar un sistema que siempre será completamente invulnerable a la estrategia (si no sabemos cómo se comportarán los jugadores), es posible diseñar un sistema que fomente la honestidad dado un concepto de solución (si el equilibrio correspondiente es único). ^[3]^[4]

La idea detrás del principio de revelación es que, si sabemos qué estrategia utilizarán los jugadores en un juego, podemos simplemente pedirles a todos los jugadores que nos envíen sus verdaderas ganancias o funciones de utilidad ; luego, tomamos esas preferencias y calculamos la estrategia óptima de cada votante antes de ejecutarla por ellos. Este procedimiento significa que un informe honesto de las preferencias es ahora la mejor estrategia posible, porque garantiza que el mecanismo jugará la estrategia óptima para el jugador.

Ejemplos

Consideremos el siguiente ejemplo. Hay un artículo que Alice valora como y Bob como . El gobierno debe decidir quién recibirá ese artículo y en qué condiciones. $v_{A}$ $Estilo de visualización vB$

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 "dar 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 asigna un conjunto de acciones individuales a un resultado social. Un mecanismo Mech induce un juego que denotamos como 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, existe 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 objeto se le da al individuo que dice el número más bajo; si ambos dicen el mismo número, entonces el objeto se le da a Alice". Este mecanismo NO implementa la función utilitaria, ya que para cada individuo que quiere el objeto, es una estrategia dominante decir "1" independientemente de su valor real. Esto significa que en equilibrio el objeto siempre se le da a Alice, incluso si Bob lo valora más.
- La subasta de oferta sellada 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 ofrece más que Alice y ambas ofertas están dentro del 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 hay un equilibrio de Nash bayesiano en el que el artículo va al postor con el valor más alto. $v_{B}>v_{A}$ $(v_{A},v_{B})$
Un mecanismo directo es un mecanismo en el que el conjunto de acciones disponibles para cada jugador es simplemente el conjunto de posibles preferencias del jugador.
Se dice que un mecanismo directo es compatible con los incentivos bayesianos de Nash (BNIC) si existe un equilibrio bayesiano de Nash de Game(Mech) en el que todos los jugadores revelan sus verdaderas preferencias. Algunos ejemplos de mecanismos directos son:
- "Cada individuo dice cuánto valora el objeto. El objeto se le da al individuo que dijo el valor más alto. En caso de empate, el objeto se le da a Alice". Este mecanismo no es BNIC, ya que un jugador que quiere el objeto está en mejor posición si dice el valor más alto posible, independientemente de su valor real.
- La subasta con oferta sellada al primer precio tampoco es BNIC, ya que el ganador siempre obtiene mejores resultados si ofrece el valor más bajo que sea ligeramente superior a la oferta del perdedor.
- Sin embargo, si se conoce la distribución de las valoraciones de los jugadores, entonces existe una variante que es BNIC e implementa la función utilitaria.
- Además, se sabe que la subasta de segundo precio es BNIC (es incluso IC en un sentido más fuerte: 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 es veraz e implementa Soc .

'Mech' simplemente simula las estrategias de equilibrio de los jugadores en el juego ( Mech ). es decir

Mech' pide a los jugadores que informen sus valoraciones.
Basándose en las valoraciones reportadas, 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 con 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 solo 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 tenga ese resultado o propiedad. Si no existe un mecanismo directo y veraz, ningún mecanismo puede implementar este resultado por contraposición . Al limitar el área que se necesita buscar, el problema de encontrar un mecanismo se vuelve mucho más fácil.

Variantes

El principio se presenta en diferentes formas, correspondientes a diferentes tipos de compatibilidad de incentivos :

El principio de revelación de la estrategia dominante dice que toda función de elección social que pueda implementarse en estrategias dominantes puede implementarse mediante un mecanismo compatible con incentivos de la estrategia dominante (DSIC) . Esta variante fue introducida por primera vez por Allan Gibbard . ^[1]
El principio de revelación bayesiano-Nash dice que cada función de elección social que se puede implementar en el equilibrio bayesiano-Nash ( juego bayesiano , es decir, juego de información incompleta) se puede implementar mediante un mecanismo de compatibilidad de incentivos bayesiano-Nash (BNIC) . Este concepto de solución más amplio fue introducido por Dasgupta, Hammond y Maskin ; ^[3] Holmström ; ^[5] y Myerson . ^[4]

El principio de revelación también funciona para los equilibrios correlacionados : ^{[ cita requerida ]} para cada dispositivo de coordinación arbitrario , también conocido como correlacionador, 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. ^{[ aclaración necesaria ]}

Véase también

Referencias

^ ab Gibbard, A. 1973. Manipulación de esquemas de votación: un resultado general. Econometrica 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 compatibilidad de incentivos. Review of Economic Studies 46, 185–216.
^ ab Myerson, R. 1979. Compatibilidad de incentivos y el problema de la negociación. Econometrica 47, 61–73.
^ Holmstrom, B. 1977. Sobre incentivos y control en las organizaciones. Tesis doctoral, Universidad de Stanford.

[:0-1] Gibbard, A. 1973. Manipulación de esquemas de votación: un resultado general. Econometrica 41, 587–601.

[AGT-2] 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.

[:1-3] Dasgupta, P., Hammond, P. y Maskin, E. 1979. La implementación de reglas de elección social: algunos resultados sobre compatibilidad de incentivos. Review of Economic Studies 46, 185–216.

[:2-4] Myerson, R. 1979. Compatibilidad de incentivos y el problema de la negociación. Econometrica 47, 61–73.

[5] Holmstrom, B. 1977. Sobre incentivos y control en las organizaciones. Tesis doctoral, Universidad de Stanford.