Algoritmo del dilema del prisionero

Question

Después de ver El Caballero Oscuro quedé bastante cautivado con el concepto del Dilema del Prisionero.Allá debe ser un algoritmo que maximice la propia ganancia dada una situación.

Para aquellos que encuentren esto extraño: http://en.wikipedia.org/wiki/Prisoner%27s_dilemma

Cosas muy, muy interesantes.

Editar:La pregunta es, qué ¿Cuál es, si lo hay, el algoritmo más eficiente que existe para el dilema del prisionero?

Answer 1

Dado que solo hay una elección que hacer, y en ausencia de entradas modificables, su algoritmo será:

cooperate = true;

...o...

cooperate = false

Es más interesante encontrar una estrategia para el dilema del prisionero iterado, que es algo que mucha gente ha hecho.Por ejemplo http://www.iteated-prisoners-dilemma.net/

Incluso entonces no es "resoluble", ya que el otro jugador no es predecible.

Answer 2

La página de Wikipedia parece dar todas las respuestas...Para el antiguo dilema del prisionero, la solución más óptima para cada prisionero (no para ambos) es traicionar.

Para el dilema del prisionero repetido, es mejor permanecer en silencio en el primer intento, y luego hacer lo que el otro prisionero hizo en el último intento.

Answer 3

El objetivo del dilema es que la solución óptima (ambos prisioneros permanecen callados) es peligrosa porque parte del problema está fuera de tu control.Entonces, elegir la solución subóptima parece maximizar su ganancia, pero sigue siendo subóptima.

No veo cómo un algoritmo podría proporcionar una solución cuando parte del problema es lo desconocido.

Answer 4

recomiendo leer La evolución de la cooperación de Axelrod.Este es un experimento informático de estrategias competitivas para el dilema del prisionero iterado.La última vez que oí hablar de esto, la estrategia de ojo por ojo salió primero.Puede que haya cambiado.

Answer 5

Para la versión única del juego, la mejor estrategia es siempre desertar, ya que no hay posibilidad de represalias.

Se vuelve más interesante para una versión iterada ya que los jugadores pueden responder a las elecciones previas de sus oponentes.

Si sabemos de antemano exactamente cuántas rondas habrá, entonces la "mejor" estrategia lógica sigue siendo desertar siempre.Esto se debe a que siempre tiene sentido desertar en el último turno, ya que no hay posibilidad de represalias.Por supuesto, nuestro oponente racional lo sabrá y siempre desertará en el último turno.Esto hace que sea sensato para nosotros desertar en el penúltimo turno, ya que de todos modos no hay posibilidad de cooperación en el turno final.Siguiendo esta lógica hasta su conclusión natural, deberíamos desertar en todo momento.

Cuando se desconoce el número total de rondas, las cosas se vuelven más interesantes.Una buena estrategia para el juego debería intentar predecir lo que hará un oponente.investigué usando algoritmos evolutivos y aprendizaje automático simple con modelado de oponentes para generar estrategias de juego para mi maestría.Si eres en realidad interesado, puedes leer mi tesis.

Según lo recomendado por Yuval, probablemente el mejor lugar para comenzar sea El libro fundamental de Axelrod.Si eres en serio en serio interesado en estas cosas, había un Seguimiento del 20 aniversario eso incluía muchos de los trabajos más recientes sobre IPD (el dilema del prisionero iterado) realizados por otros investigadores.

Además, recomendé ampliamente el libro de William Poundstone. El dilema del prisionero, que es en parte una biografía de John von Neumann y en parte una introducción a la teoría de juegos.

Answer 6

Bueno, según tengo entendido, el reconocimiento de patrones también es una gran parte.Encontrar el hábito del otro prisionero: con qué frecuencia se queda callado y cuándo habla.También tienes que hacer una referencia cruzada con tus propias elecciones para determinar qué hiciste para que él reaccionara de cierta manera.

Creo que es un poco más complejo de lo que explica wiki.No se trata sólo de lo que hizo el prisionero en el último intento, sino de todo lo anterior que se extiende hasta el infinito.

Answer 7

No lo hay, ya que no se puede predecir categóricamente el comportamiento del segundo prisionero.

Hay todo tipo de "soluciones" que parten de suposiciones subyacentes pero muy restrictivas sobre el comportamiento del segundo prisionero, pero tienen poco que decir sobre el problema no restringido (eso es lo que lo convierte en un dilema tan convincente).

Mi opinión, dado que no se puede confiar en el comportamiento del segundo prisionero, es que todo se reduce a:¿Eres optimista o cínico?¿Los dos prisioneros van a permanecer juntos (honor entre ladrones), o se van a delatar a la primera oportunidad para salvar su propia garganta...?

Answer 8

Además, en un juego de prisioneros iterado, la estrategia óptima variará según las otras estrategias en juego.

En una serie contra un jugador que SIEMPRE deserta, siempre desertar es la mejor estrategia.Cuando se juega contra un jugador que podría cooperar, probablemente sea mejor una estrategia que tome represalias, pero que ocasionalmente perdone.

Debo añadir que esto sólo se aplica en un juego de duración desconocida.Cualquier juego de duración conocida es idéntico al juego de una sola ronda.

Answer 9

Intentar encontrar una solución óptima para el dilema del prisionero es como tratar de encontrar una para Ro-Sham-Bo (piedra, papel y tijera). Lo mejor que puedes hacer es modelar a tu oponente e intentar explotar patrones.

En los primeros días de la teoría de juegos y la informática, John von Neumann y la Rand Corporation gastaron grandes cantidades de sudor cerebral tratando de encontrar un algoritmo óptimo para resolver el dilema del prisionero sin éxito y, finalmente, demostraron matemáticamente que no existía. solucion optima.

Answer 10

Ah, sí.Esto me hizo recordar este viejo artículo sobre El dilema del prisionero en el desarrollo de software

Para una mirada de competencia de PD algorítmica aquí

Este fue bueno también

Answer 11

El objetivo del dilema del prisionero es que la estrategia óptima es traicionar al otro prisionero.O(1)

Answer 12

Matemáticamente, las otras publicaciones responden a la pregunta, pero en realidad puede haber opciones adicionales.Por absurdas que sean estas opciones, generarán posibilidades de resultados adicionales y pueden generar mayores posibilidades de ganancias personales.Por ejemplo, en el caso de Batman, arruinaría la trama, pero podría simplemente haber matado al Joker, arruinando así cualquier efecto adicional que el Joker tendría en el resultado.Al dejar vivir al Joker, Batman, sin saberlo, le permite al Joker la única "victoria" que necesita.

Answer 13

El juego se vuelve mucho más interesante cuando das un paso atrás y consideras todo el torneo.Por ejemplo, hace unos años, un equipo del Reino Unido ganó un torneo de PD que presentó varias inscripciones.Uno de ellos era el "amo" y los otros eran "esclavos".Todos comenzarían ejecutando una secuencia específica de acciones que permitirían a amos y esclavos reconocerse entre sí.Una vez reconocido, el maestro desertaría y el esclavo cooperaría durante el resto de las iteraciones.Así, el amo ganó el torneo pero a costa de los esclavos.

La estrategia tenía sentido desde el punto de vista económico, ya que había un premio monetario para el primer lugar pero el coste de entrada era bajo.

En términos más generales, al escribir un programa para un torneo TD es necesario tener una visión más amplia:

1. ¿Cómo se entregan los premios?
2. ¿Puedes conspirar con otros concursantes?
3. ¿Cuales son los costos de entrada?sanciones?

De lo contrario, sí, la estrategia dominante es desertar del PD de una sola vez.Axelrod, como otros mencionaron, demostró que el ojo por ojo era sólido en una serie de torneos, pero en estos torneos nadie pensó en conspirar con otros concursantes.