Estrategia a prueba de errores

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 otros 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 estrategia 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 llama 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 los jugadores individuales (pero no de las coaliciones). En cambio, en un mecanismo de grupo a prueba de estrategias , ningún grupo de personas puede coludirse para informar erróneamente sobre 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 coludirse para informar erróneamente sobre sus preferencias de una manera que beneficie al menos a un miembro del grupo sin perjudicar a ninguno de los miembros restantes. ^[2]

Ejemplos

Ejemplos típicos de mecanismos SP son:

• un voto mayoritario entre dos alternativas;
• una subasta de segundo precio cuando los participantes tienen una utilidad cuasilineal ;
• Un mecanismo VCG cuando los participantes tienen una 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

SP en enrutamiento de red

SP también es aplicable en el enrutamiento de redes . ^{[ cita requerida ]} Considere una red como un gráfico donde cada borde (es decir, enlace) tiene un costo asociado de transmisión , conocido de forma privada por el propietario del enlace. El propietario de un enlace desea ser compensado por retransmitir mensajes. Como remitente de un mensaje en la red, uno quiere encontrar la ruta de menor costo. Hay métodos eficientes para hacerlo, incluso en redes grandes. Sin embargo, hay un problema: se desconocen los costos de cada enlace. Un enfoque ingenuo sería preguntarle al propietario de cada enlace el costo, usar 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. Podemos terminar pagando mucho más que el costo real. Se puede demostrar que dadas ciertas suposiciones sobre la red y los jugadores (propietarios de enlaces), una variante del mecanismo VCG es SP. ^{[ cita requerida ]}

Definiciones formales

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

Existen agentes que tienen distintas valoraciones 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 cada alternativa, en términos monetarios.

Se supone que los agentes tienen funciones de utilidad cuasililineales ; 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 . Por lo tanto . ${\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 valores 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 valores 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 denomina a prueba de estrategias si, para cada jugador y para cada vector de valores 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

Resulta útil contar con condiciones simples para comprobar si un mecanismo determinado es SP o no. En esta subsección se muestran dos condiciones simples que son 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 manera similar, si entonces un agente con valoración prefiere informar . ${\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 "precio", , que toma como entrada un resultado y un vector de valoración para los otros agentes , y devuelve el pago para el agente Para 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 se aplica a 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 da 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: Fijar 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 verazmente.

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

Por la propiedad 1, la utilidad del agente cuando juega honestamente 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, una estrategia dominante para el agente es actuar con veracidad.

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 ser honestos. 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 requerida ]} ${\displaystyle Outcome}$

La propiedad de monotonía es necesaria para la seguridad de las estrategias. ^{[ cita requerida ]}

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 valor positivo determinado por "ganar" y un valor 0 por "perder". Un ejemplo sencillo 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}$

En este contexto, es fácil caracterizar los mecanismos de verdad. Empecemos con algunas definiciones.

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

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

Para un mecanismo monótono, para cada jugador i y cada combinación de ofertas de los otros jugadores, hay un valor crítico en el cual 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 oferta ganadora paga el valor crítico.

Veracidad de los mecanismos aleatorios

Existen diversas formas de extender la noción de veracidad a los mecanismos aleatorios. Son, de mayor a menor: ^{[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 de dominancia estocástica fuerte (veracidad de SD fuerte) : el vector de probabilidades que un agente recibe por ser veraz tiene dominancia estocástica de primer orden sobre el vector de probabilidades que obtiene por informar erróneamente. Es decir: la probabilidad de obtener la máxima prioridad es al menos tan alta Y la probabilidad de obtener una de las dos máximas prioridades es al menos tan alta Y... la probabilidad de obtener una de las m máximas prioridades es al menos tan 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 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 DE fuerte, implica Lex implica DE débil, y todas las implicaciones son estrictas. ^{[3] : Teoría 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 tiende a 0 cuando el número de postores aumenta, entonces el mecanismo se denomina veraz con alta probabilidad . Este concepto es más débil que el de veracidad total, pero sigue siendo útil en algunos casos; véase, por ejemplo, la estimación por consenso . ${\displaystyle \epsilon }$

A prueba de nombres falsos

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

La prueba de nombres falsos significa que no hay incentivos para que ninguno de los jugadores haga ofertas con nombres falsos. Este concepto es más fuerte que el de prueba de estrategia. En particular, la subasta Vickrey-Clarke-Groves (VCG) no es prueba de nombres falsos. ^[4]

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

Véase también

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

Lectura adicional

• 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, págs. 107–133.
• Sobre la prueba asintótica de estrategias en las reglas clásicas de elección social Un artículo de Arkadii Slinko sobre la prueba de estrategias 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. "Estrategia grupal a prueba de errores 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 quinta conferencia sobre innovaciones en informática teórica . ITCS '14. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 105–120. doi :10.1145/2554797.2554810. ISBN 978-1-4503-2698-8.S2CID2428592  .​
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.