A prueba de estrategias

En el diseño de mecanismos , un mecanismo a prueba de estrategias (SP) es una forma de juego en la 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 su valor para algún elemento), y el espacio de estrategias 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 revelar la información verdadera es una estrategia débilmente dominante para cada jugador. ^{[ 1 ] : 244} Un mecanismo 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 SP es inmune a las manipulaciones de jugadores individuales (pero no de coaliciones). Por el contrario, en un mecanismo a prueba de estrategias grupales , ningún grupo de personas puede confabularse para falsear sus preferencias de manera que beneficie a todos sus miembros. En un mecanismo a prueba de estrategias grupales fuerte, ningún grupo de personas puede confabularse para falsear sus preferencias de manera que beneficie al menos a un miembro del grupo sin perjudicar a los demás. ^{[ 2 ]}

Ejemplos típicos de mecanismos SP son:

• una votación mayoritaria entre dos alternativas;
• una subasta de segundo precio cuando los participantes tienen una utilidad cuasilineal ;
• un mecanismo VCG cuando los participantes tienen utilidad cuasilineal

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

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

Hay${\displaystyle n}$agentes que tienen diferentes valoraciones para cada resultado. La valoración del agente${\displaystyle i}$se representa como una función:

${\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${\displaystyle x}$y además el agente recibe un pago${\displaystyle p_{i}}$(positivo o negativo), entonces la utilidad total del agente${\displaystyle i}$es:

${\displaystyle u_{i}:=v_{i}(x)+p_{i}}$

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

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

Un mecanismo es un par de funciones:

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

Un mecanismo se denomina a prueba de estrategia si, para cada jugador${\displaystyle i}$y para cada vector de valores de los demás jugadores${\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})}$

Resulta útil contar con condiciones sencillas para comprobar si un mecanismo determinado es SP o no. Esta subsección muestra dos condiciones sencillas 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.${\displaystyle i}$: ^{[ 1 ] : 226}

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

${\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${\displaystyle Payment_{i}(v_{i},v_{-i})>Payment_{i}(v_{i}',v_{-i})}$luego un agente con valoración${\displaystyle v_{i}'}$prefiere informar${\displaystyle v_{i}}$, ya que le da el mismo resultado y un pago mayor; de manera similar, si${\displaystyle Payment_{i}(v_{i},v_{-i})<Payment_{i}(v_{i}',v_{-i})}$luego un agente con valoración${\displaystyle v_{i}}$prefiere informar${\displaystyle v_{i}'}$.

Como corolario, existe una función de "precio de venta",${\displaystyle Price_{i}}$, que toma como entrada un resultado${\displaystyle x\in X}$y un vector de valoración para los demás agentes.${\displaystyle v_{-i}}$y devuelve el pago al agente${\displaystyle i}$Por cada${\displaystyle v_{i},v_{-i}}$, si:

${\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.${\displaystyle i}$, dadas las valoraciones de los demás agentes. Formalmente:

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

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

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

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

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

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

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

Según la propiedad 1, la utilidad del agente al jugar con veracidad es:

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

y la utilidad del agente cuando juega de forma deshonesta 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 tanto, para el agente, actuar con veracidad es una estrategia dominante.

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

En este contexto, es fácil caracterizar los mecanismos veraces. Comencemos con algunas definiciones.

Un mecanismo se denomina normalizado si cada puja perdedora paga 0.

Un mecanismo se denomina monótono si, cuando un jugador sube su apuesta, sus posibilidades de ganar aumentan (débilmente).

En un mecanismo monótono, para cada jugador i y cada combinación de pujas de los demás 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 veraz 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 puja ganadora paga el valor crítico.

Existen diversas maneras de extender la noción de veracidad a mecanismos aleatorios. Estas son, de más a menos: ^{[ 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 los pesos pueden depender de la entrada.
• Veracidad con dominancia estocástica fuerte (veracidad SD fuerte) : El vector de probabilidades que un agente recibe al ser veraz tiene dominancia estocástica 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 máximas prioridades es al menos igual de alta Y... la probabilidad de obtener una de las m máximas prioridades es al menos igual de alta.
• Veracidad lexicográfica (lex-veracidad) : El vector de probabilidades que un agente recibe al ser veraz tiene dominancia lexicográfica sobre el vector de probabilidades que obtiene al 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 máximas prioridades es mayor) O ... (la probabilidad de obtener la primera prioridad m -1 es igual y la probabilidad de obtener una de las m máximas prioridades es mayor) O (todas las probabilidades son iguales).
• Veracidad de dominancia estocástica débil (veracidad SD débil) : El vector de probabilidades que un agente recibe al ser veraz no está dominado estocásticamente de primer orden por el vector de probabilidades que obtiene al informar erróneamente.

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

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

La inmunidad a los nombres falsos implica que ninguno de los jugadores tiene incentivos para realizar ofertas con nombres falsos. Este concepto es más estricto que el de inmunidad a las estrategias. En particular, la subasta Vickrey-Clarke-Groves (VCG) no es inmune a los nombres falsos. ^{[ 4 ]}

La resistencia a la suplantación de identidad es significativamente diferente de la resistencia a la manipulación mediante estrategias grupales, ya que presupone que un individuo por sí solo puede simular ciertos comportamientos que normalmente requieren la coordinación colusoria de múltiples individuos.

La invulnerabilidad a las estrategias obvias (OSP, por sus siglas en inglés) es un fortalecimiento de la invulnerabilidad a las estrategias que refleja la robustez de esta última frente a agentes cognitivamente limitados. ^{[ 5 ]}

La subasta de segundo precio con ofertas selladas es a prueba de manipulación, pero no obviamente a prueba de manipulación, ya que los postores deben confiar en que sus ofertas permanezcan selladas. ^{[ 6 ] [ 7 ]} En contraste, la subasta de reloj ascendente es obviamente a prueba de manipulación, ^{[ 5 ]} aunque para agentes completamente racionales ambas subastas son equivalentes. Otros ejemplos de mecanismos a prueba de manipulación, pero no obviamente a prueba de manipulación, incluyen:

• Votación mayoritaria entre dos alternativas;
• Aceptación diferida ^{[ 8 ]}
• Ciclos de negociación más importantes

• Compatibilidad de incentivos
• Resistencia evidente a las estrategias : un fortalecimiento de la resistencia a las estrategias.
• racionalidad individual
• Criterio de participación : un jugador no puede perder por jugar (es decir, un jugador no tiene ningún incentivo para evitar jugar).
• A prueba de estrategias grupales

• Parkes, David C. (2004), Sobre el diseño de mecanismos aprendibles, en: Tumer, Kagan y David Wolpert (Eds.): Colectivos y el diseño de sistemas complejos, Nueva York uaO, pp.  107–133.
• Sobre la resistencia asintótica a la manipulación estratégica de las reglas clásicas de elección social. Un artículo de Arkadii Slinko sobre la resistencia a la manipulación estratégica en los sistemas de votación.