A prueba de estrategias

En el diseño de mecanismos , un mecanismo a prueba de estrategias (SP) es un juego en el que cada jugador tiene una estrategia débilmente dominante , de modo que ningún jugador puede ganar "espiando" a los demás jugadores para saber qué van a jugar. Cuando los jugadores tienen información privada (por ejemplo, su tipo o el valor de algún elemento), y el espacio estratégico de cada jugador consiste en los posibles valores de información (por ejemplo, posibles tipos o valores), un mecanismo veraz es un juego en el que se revela la verdadera información. La información es una estrategia débilmente dominante para cada jugador. ^{[1] : 244} Un mecanismo de SP también se denomina compatible con incentivos de estrategia dominante (DSIC) , ^{[1] : 415} para distinguirlo de otros tipos de compatibilidad de incentivos .

Un mecanismo de SP es inmune a las manipulaciones de actores individuales (pero no de coaliciones). Por el contrario, en un mecanismo grupal a prueba de estrategias , ningún grupo de personas puede confabularse para informar erróneamente sus preferencias de una manera que beneficie a todos los miembros. En un mecanismo de grupo fuerte a prueba de estrategias, ningún grupo de personas puede confabularse para informar erróneamente sus preferencias de manera que mejore la situación de al menos un miembro del grupo sin empeorar la situación de ninguno de los miembros restantes. ^[2]

Ejemplos

Ejemplos típicos de mecanismos de SP son:

• una mayoría de votos entre dos alternativas;
• una subasta de segundo precio ;
• un mecanismo VCG

Ejemplos típicos de mecanismos que no son SP son:

• cualquier elección determinista no dictatorial entre tres o más alternativas;
• una subasta de primer precio

SP en enrutamiento de red

SP también es aplicable en el enrutamiento de red . ^{[ cita necesaria ]} Considere una red como un gráfico donde cada borde (es decir, enlace) tiene un costo de transmisión asociado , conocido de forma privada por el propietario del enlace. El propietario de un enlace desea recibir una compensación por transmitir mensajes. Como remitente de un mensaje en la red, uno quiere encontrar el camino menos costoso. Existen métodos eficaces para hacerlo, incluso en redes grandes. Sin embargo, existe un problema: se desconocen los costes de cada enlace. Un enfoque ingenuo sería preguntarle al propietario de cada enlace el costo, utilizar estos costos declarados para encontrar la ruta de menor costo y pagar a todos los enlaces en la ruta sus costos declarados. Sin embargo, se puede demostrar que este esquema de pago no es SP, es decir, los propietarios de algunos enlaces pueden beneficiarse mintiendo sobre el costo. Es posible que terminemos pagando mucho más que el costo real. Se puede demostrar que, dados ciertos supuestos sobre la red y los jugadores (propietarios de enlaces), una variante del mecanismo VCG es SP. ^{[ cita necesaria ]}

Definiciones formales

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

Hay agentes que tienen valoraciones diferentes para cada resultado. 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}}$

El vector de todas las funciones de valor se denota por . ${\displaystyle v}$

Para cada agente , el vector de todas las funciones de valor de los otros agentes se denota por . Entonces . ${\displaystyle i}$ ${\displaystyle v_{-i}}$ ${\displaystyle v\equiv (v_{i},v_{-i})}$

Un mecanismo es un par de funciones:

• Una función que toma como entrada el vector de valor y devuelve un resultado (también se llama función de elección social ); ${\displaystyle Outcome}$ ${\displaystyle v}$ ${\displaystyle x\in X}$
• Una función que toma como entrada el vector de valor y devuelve un vector de pagos, que determina cuánto debe recibir cada jugador (un pago negativo significa que el jugador debe pagar una cantidad positiva). ${\displaystyle Payment}$ ${\displaystyle v}$ ${\displaystyle (p_{1},\dots ,p_{n})}$

Un mecanismo se llama a prueba de estrategias si, para cada jugador y para cada vector de valor de los demás jugadores : ${\displaystyle i}$ ${\displaystyle v_{-i}}$

${\displaystyle v_{i}(Outcome(v_{i},v_{-i}))+Payment_{i}(v_{i},v_{-i})\geq v_{i}(Outcome(v_{i}',v_{-i}))+Payment_{i}(v_{i}',v_{-i})}$

Caracterización

Es útil tener condiciones simples para verificar si un mecanismo determinado es SP o no. Esta subsección muestra dos condiciones simples que son a la vez necesarias y suficientes.

Si un mecanismo con transferencias monetarias es SP, entonces debe satisfacer las dos condiciones siguientes, para cada agente : ^{[1] : 226} ${\displaystyle i}$

1. El pago al agente es una función del resultado elegido y de las valoraciones de los otros agentes , pero no una función directa de la propia valoración del agente . Formalmente, existe una función de precio , que toma como entrada un resultado y un vector de valoración para los otros agentes , y devuelve el pago para el agente , de modo que para cada , si: ${\displaystyle i}$ ${\displaystyle v_{-i}}$ ${\displaystyle v_{i}}$ ${\displaystyle Price_{i}}$ ${\displaystyle x\in X}$ ${\displaystyle v_{-i}}$ ${\displaystyle i}$ ${\displaystyle v_{i},v_{i}',v_{-i}}$

${\displaystyle Outcome(v_{i},v_{-i})=Outcome(v_{i}',v_{-i})}$

entonces:

${\displaystyle Payment_{i}(v_{i},v_{-i})=Payment_{i}(v_{i}',v_{-i})}$

PRUEBA: Si entonces un agente con valoración prefiere informar , ya que le da el mismo resultado y un pago mayor; de igual manera, si luego un agente con valoración prefiere denunciar . ${\displaystyle Payment_{i}(v_{i},v_{-i})>Payment_{i}(v_{i}',v_{-i})}$ ${\displaystyle v_{i}'}$ ${\displaystyle v_{i}}$ ${\displaystyle Payment_{i}(v_{i},v_{-i})<Payment_{i}(v_{i}',v_{-i})}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i}'}$

Como corolario, existe una función de "etiqueta de precio", que toma como entrada un resultado y un vector de valoración para los otros agentes , y devuelve el pago del agente por cada , si: ${\displaystyle Price_{i}}$ ${\displaystyle x\in X}$ ${\displaystyle v_{-i}}$ ${\displaystyle i}$ ${\displaystyle v_{i},v_{-i}}$

${\displaystyle Outcome(v_{i},v_{-i})=x}$

entonces:

${\displaystyle Payment_{i}(v_{i},v_{-i})=Price_{i}(x,v_{-i})}$

2. El resultado seleccionado es óptimo para el agente , dadas las valoraciones de los demás agentes. Formalmente: ${\displaystyle i}$

${\displaystyle Outcome(v_{i},v_{-i})\in \arg \max _{x}[v_{i}(x)+Price_{i}(x,v_{-i})]}$

donde la maximización es sobre todos los resultados en el rango de . ${\displaystyle Outcome(\cdot ,v_{-i})}$

PRUEBA: Si hay otro resultado tal que , entonces un agente con valoración prefiere informar , ya que le proporciona una utilidad total mayor. ${\displaystyle x'=Outcome(v_{i}',v_{-i})}$ ${\displaystyle v_{i}(x')+Price_{i}(x',v_{-i})>v_{i}(x)+Price_{i}(x,v_{-i})}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i}'}$

Las condiciones 1 y 2 no sólo son necesarias sino también suficientes: cualquier mecanismo que satisfaga las condiciones 1 y 2 es SP.

PRUEBA: Arreglar un agente y valoraciones . Denotar: ${\displaystyle i}$ ${\displaystyle v_{i},v_{i}',v_{-i}}$

${\displaystyle x:=Outcome(v_{i},v_{-i})}$- el resultado cuando el agente actúa con sinceridad.

${\displaystyle x':=Outcome(v_{i}',v_{-i})}$- el resultado cuando el agente actúa con mentira.

Por la propiedad 1, la utilidad del agente al jugar con verdad es:

${\displaystyle u_{i}(v_{i})=v_{i}(x)+Price_{i}(x,v_{-i})}$

y la utilidad del agente cuando juega con mentira es:

${\displaystyle u_{i}(v_{i}')=v_{i}(x')+Price_{i}(x',v_{-i})}$

Por propiedad 2:

${\displaystyle u_{i}(v_{i})\geq u_{i}(v_{i}')}$

por lo que es una estrategia dominante para el agente actuar con sinceridad.

Caracterización de la función de resultado.

El objetivo real de un mecanismo es su función; la función de pago es sólo una herramienta para inducir a los jugadores a decir la verdad. Por lo tanto, es útil saber, dada una determinada función de resultado, si se puede implementar utilizando un mecanismo SP o no (esta propiedad también se denomina implementabilidad ). ^{[ cita necesaria ]} ${\displaystyle Outcome}$

La propiedad de monotonicidad es necesaria para la eficacia estratégica. ^{[ cita necesaria ]}

Mecanismos veraces en dominios de un solo parámetro.

Un dominio de un solo parámetro es un juego en el que cada jugador obtiene un determinado valor positivo por "ganar" y un valor 0 por "perder". Un ejemplo simple es una subasta de un solo artículo, en la que es el valor que el jugador asigna al artículo. ${\displaystyle i}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle i}$

Para este escenario, es fácil caracterizar mecanismos veraces. Comience con algunas definiciones.

Un mecanismo se llama normalizado si cada oferta perdedora paga 0.

Un mecanismo se llama monótono si, cuando un jugador aumenta su oferta, aumentan (débilmente) sus posibilidades de ganar.

Para un mecanismo monótono, para cada jugador i y cada combinación de ofertas de los otros jugadores, existe un valor crítico en el que el jugador pasa de perder a ganar.

Un mecanismo normalizado en un dominio de un solo parámetro es verdadero si se cumplen las dos condiciones siguientes: ^{[1] : 229–230}

1. La función de asignación es monótona en cada una de las ofertas, y:
2. Cada oferta ganadora paga el valor crítico.

Veracidad de los mecanismos aleatorios.

Hay varias formas de extender la noción de veracidad a mecanismos aleatorios. Son, del más fuerte al más débil: ^{[3] : 6–8}

• Veracidad universal : para cada aleatorización del algoritmo, el mecanismo resultante es veraz. En otras palabras: un mecanismo universalmente veraz es una aleatorización sobre mecanismos veraces deterministas, donde las ponderaciones pueden depender de los insumos.
• Veracidad de dominio estocástico fuerte (fuerte-SD-veracidad) : el vector de probabilidades que recibe un agente al ser veraz tiene un dominio estocástico de primer orden sobre el vector de probabilidades que obtiene al informar erróneamente. Es decir: la probabilidad de obtener la máxima prioridad es al menos igual de alta Y la probabilidad de obtener una de las dos prioridades principales es al menos igual de alta Y... la probabilidad de obtener una de las m prioridades principales es al menos igual de alta .
• Veracidad lexicográfica (lex-truthfulness) : El vector de probabilidades que recibe un agente por ser veraz tiene dominio lexicográfico sobre el vector de probabilidades que obtiene por informar erróneamente. Es decir: la probabilidad de obtener la máxima prioridad es mayor O (la probabilidad de obtener la máxima prioridad es igual y la probabilidad de obtener una de las dos principales prioridades es mayor) O ... (la probabilidad de obtener la primera m - 1 prioridad de prioridades es igual y la probabilidad de obtener una de las m prioridades principales es mayor) O (todas las probabilidades son iguales).
• Veracidad de dominio estocástico débil (veracidad SD débil) : el vector de probabilidades que recibe un agente al ser veraz no está dominado estocásticamente de primer orden por el vector de probabilidades que obtiene al informar erróneamente.

Universal implica SD fuerte implica Lex implica SD débil, y todas las implicaciones son estrictas. ^{[3] : Thm.3.4}

Veracidad con alta probabilidad.

Para cada constante , un mecanismo aleatorio se llama veraz con probabilidad si para cada agente y para cada vector de ofertas, la probabilidad de que el agente se beneficie al ofertar de manera no veraz es como máximo , donde la probabilidad se toma sobre la aleatoriedad del mecanismo. ^{[1] : 349} ${\displaystyle \epsilon >0}$ ${\displaystyle 1-\epsilon }$ ${\displaystyle \epsilon }$

Si la constante llega a 0 cuando aumenta el número de postores, entonces el mecanismo se considera veraz con alta probabilidad . Esta noción es más débil que la total veracidad, pero sigue siendo útil en algunos casos; véase, por ejemplo, estimación de consenso . ${\displaystyle \epsilon }$

A prueba de nombres falsos

Un nuevo tipo de fraude que se ha vuelto común con la abundancia de subastas por Internet son las ofertas con nombres falsos: ofertas presentadas por un solo postor utilizando múltiples identificadores, como múltiples direcciones de correo electrónico.

La protección contra nombres falsos significa que no hay ningún incentivo para que ninguno de los jugadores haga ofertas por nombres falsos. Ésta es una noción más fuerte que la de la resistencia a la estrategia. En particular, la subasta Vickrey-Clarke-Groves (VCG) no es una prueba de nombres falsos. ^[4]

La protección contra nombres falsos es muy diferente de la protección contra estrategias grupales porque supone que un individuo por sí solo puede simular ciertos comportamientos que normalmente requieren la coordinación colusoria de múltiples individuos. ^{[ cita requerida ] [ se necesita más explicación ]}

Ver también

• Compatibilidad de incentivos
• Racionalidad individual
• Criterio de participación : un jugador no puede perder jugando (es decir, un jugador no tiene incentivos para evitar jugar).

Otras lecturas

• Parkes, David C. (2004), On Learnable Mechanism Design, en: Tumer, Kagan y David Wolpert (Eds.): Collectives and the Design of Complex Systems, Nueva York uaO, págs.
• Sobre la prueba de estrategia asintótica de las reglas clásicas de elección social Un artículo de Arkadii Slinko sobre la prueba de estrategia en los sistemas de votación.

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. "A prueba de estrategia de grupo y elección social entre dos alternativas" (PDF) . Archivado desde el original (PDF) el 12 de febrero de 2020.
3. Chakrabarty, Deeparnab; Swamy, Chaitanya (12 de enero de 2014). "Maximización del bienestar y veracidad en el diseño de mecanismos con preferencias ordinales". Actas de la V conferencia sobre Innovaciones en informática teórica . ITC '14. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 105-120. doi :10.1145/2554797.2554810. ISBN 978-1-4503-2698-8. S2CID  2428592.
4. Yokoo, M.; Sakurai, Y.; Matsubara, S. (2004). "El efecto de las ofertas con nombres falsos en subastas combinatorias: nuevo fraude en subastas por Internet". Juegos y comportamiento económico . 46 : 174–188. CiteSeerX 10.1.1.18.6796 . doi :10.1016/S0899-8256(03)00045-9.