Libros: “El dilema del prisionero”. (William Poundstone)

Publicado: 06/06/2009 en libros
Etiquetas:, ,

Otro libro recomendable: “El dilema del prisionero. Jhon von Neumann, la teoría de juegos y la bomba“. William Poundstone.

Además de la teoría de juegos, el libro ‘es’ también una biografía de John von Neumann, uno de los matemáticos que ‘aceptó’ el famoso reto de Hilbert (axiomatizar las matemáticas), que finalmente zanjó Gödel.

La teoría de juegos estudia la pugna entre unos oponentes que piensan y que pueden ser capaces de engañar. Presupone que las jugadoras son totalmente racionales. (No es por tanto una teoría ‘psicológica’, sino matemática).

Von Neumann formuló el ‘Teorema Minimax‘, según el cual “siempre existe una forma racional de actuar en juegos de dos participantes si los intereses que los gobiernan son completamente opuestos”.

El Teorema Minimax demuestra que para cualquier juego de suma cero (lo que uno gana lo pierde el otro), finito, y con dos jugadoras, existe una solución racional bien como una estrategia pura bien como una estrategia mixta. Así pues, lo que el teorema establece es que siempre existe una solución racional para un conflicto definido con exactitud entre dos personas cuyos intereses son totalmente opuestos. Una solución racional en el sentido de que ambos participantes pueden convencerse a sí mismos de que no podrían hacer nada mejor, dada la propia naturaleza del conflicto.

Dilema del prisionero:

Una de las formulaciones posibles sería esta: dos presos en dos celdas separadas e incomunicados entre sí; a cada uno se le ofrece la posibilidad de delatar al otro; si ninguno se delata mutuamente, ambos son condenados a 1 año; si ambos se delatan, ambos son condenados a 2 años; si uno delata y el otro no, el primero queda libre y el otro es condenado a 3 años.

La pregunta es, … ¿cual es la mejor estrategia posible?

La respuesta no es fácil (todavía no se ha resuelto el problema y probablemente no tenga solución, ya que nos encontramos ante una paradoja). Jugando ‘una sola partida’ es igual de difícil justificar como un resultado racional tanto la cooperación como la deserción mutua. Ante una sola partida, la mejor estrategia parece ser la de desertar. No obstante, si el juego se hace iterativo (jugando muchas partidas) se pueden elegir distintas estrategias y al parecer, la más efectiva es la de hacer la primera jugada a cooperar, y luego responder en función de la jugada del adversario, castigando sus deserciones desertando en la siguiente jugada y volviendo a cooperar (estrategia denominada ‘donde las dan las toman’)

Hay más juegos/dilemas similares:

  • El juego/dilema de la ‘gallina’: avanzar con dos coches hacia un precipicio y el primero que frene pierde.
  • La subasta del dolar: se pone un dolar a subasta con la peculiaridad de que al final, tanto el ganador de la puja como el segundo de la puja deben pagar.
  • Juego de la “Lotería del número más grande” (ideado por Douglas R. Hofstadter, … el de GEB). Consiste en lo siguiente: se sortea un millón de dolares (1M$); gana el que envíe el número más grande; pero el premio consiste en 1M$/numero_ganador.

La teoría de juegos, impulsada por von Neumann, se desarrollo fundamentalmente en la RAND Corporation, una especia de think tank creado por los yankis en plena segunda guerra mundial, y que entre otras cosas desarrollaron el método de análisis DAFO. Y el libro tiene un capítulo entero dedicada a esta peculiar organización, que se auto-definía como “algo más que una agrupación de personas; es una institución social dotada de inteligencia y sentido del humor.”

Anuncios
comentarios
  1. hector00 dice:

    es interesante analizarlo porque veo que se pueden agregar otras situaciones como los juegos con informacion perfecta donde al hacerse cada jugada personal se conoce los resultados de jugadas anteriores, ademas es posible que los presos apliquen diferentes estrategias, sin conocer lo que esta por hacer el otro pero si denominamos a los presos del ejemplo A y B respectivamente y a las soluciones 1 y 2 entonces tenemos que es posible que tengamos una probabilidad del 50 y 50, pero si utilizan estrategias mixtas como mentir, en una parte y decir la verdad en otra entonces tenemos que esa posibilidad puede jugar en favor de uno u otro, creo que es posible y necesito mas tiempo para asimilarlo :)

    • txema dice:

      El libro ofrece un análisis muy detallado de las distintas estrategias posibles y sus resultados, tanto para el dilema del prisionero como para otros juegos.

  2. txema dice:

    The Emerging Revolution in Game Theory

    The discovery of a winning strategy for Prisoner’s Dilemma is forcing game theorists to rethink their discipline. Their conclusion? Winning isn’t everything.

    http://www.technologyreview.com/view/428920/the-emerging-revolution-in-game-theory/

    The world of game theory is currently on fire. In May, Freeman Dyson at Princeton University and William Press at the University of Texas announced that they had discovered a previously unknown strategy for the game of prisoner’s dilemma which guarantees one player a better outcome than the other.

    That’s a monumental surprise. Theorists have studied Prisoner’s Dilemma for decades, using it as a model for the emergence of co-operation in nature. This work has had a profound impact on disciplines such as economics, evolutionary biology and, of course, game theory itself. The new result will have impact in all these areas and more.

    The game is this: imagine Alice and Bob have committed a crime and are arrested. The police offer each one a deal–snitch and you go free while your friend does 6 months in jail. If both Alice and Bob snitch, they both get 3 months in jail. If they both remain silent, they both get one month in jail for a lesser offence.

    What should Alice and Bob do?

    If they co-operate, they both spend only one month in jail. Nevertheless, in a single game, the best strategy is to snitch because it guarantees that you don’t get the maximum jail term.

    However, the game gets more interesting when played in repeated rounds because players who have been betrayed in one round have the chance to get their own back in the next iteration.

    Until now, everyone thought the best strategy in iterative prisoner’s dilemma was to copy your opponents behaviour in the previous round. This tit-for-tat approach guarantees that you both spend the same time in jail.

    That conclusion was based on decades of computer simulations and a certain blind faith in the symmetry of the solution.

    So the news that there are other strategies that allow one player to not only beat the other but to determine their time in jail is nothing short of revolutionary.

    The new approach is called the zero determinant strategy (because it involves the process of setting a mathematical object called a determinant to zero).

    It turns out that the tit-for-tat approach is a special case of the zero determinant strategy: the player using this strategy determines that the other player’s time in jail is equal to theirs. But there are a whole set of other strategies that make the other player spend far more time in jail (or far less if you’re feeling generous).

    The one caveat is that the other player must be unaware that they are being manipulated. If they discover the ruse, they can play a strategy that results in the maximum jail time for both players: ie both suffer.

    Game theorists call this the Ultimatum Game. It’s equivalent to giving Alice £100 and asking her to divide it between her and Bob. Bob can accept the division or refuse it if he thinks the division is unfair, in which case both players get nothing. The refusal is Bob’s way of punishing Alice for her greed.

    The interesting thing here is that when both players are aware of the zero determinant ruse, the prisoner’s dilemma turns into a different game.

    Press and Dyson’s discovery has sent game theorists scurrying to work out the implications. They’ve been using prisoner’s dilemma to gain insight into everything from Cold War politics and climate change negotiations to psychology and, of course, the evolutionary origin of co-operation itself.

    Today, we see one of the first paper’s to study these implications in detail. Christoph Adami and Arend Hintze from Michigan State University in East Lansing investigate whether the zero determinant strategies are evolutionary stable.

    That’s an interesting question. It asks the following: if an entire population of individuals all play zero determinant strategies, could another strategy spread through the population and take over? If not, zero determinant strategies are evolutionary stable.

    Adami and Hintze show that zero determinant strategies are not evolutionary stable. The reason is that they do not perform well against each other and that leaves the door open for other strategies to sneak in and take over.

    Zero determinant strategies are not stable in another way. Adami and Hintze show that if the player’s strategies evolve, the changes that occur between one generation and the next ensure that the new strategy is generally not zero determinant. So the strategy cannot survive.

    However, there is one scenario in which Adami and Hintze say the new strategy should be stable. That’s when the zero determinant players can work out whether other players are using the same strategy or not. In that case, they can avoid the loses that occur when playing against their own while exploiting ignorant players.

    So to be stable, zero determinant strategies require additional information about their opponents.This information gives them a clear advantage but probably only a temporary one. “Such an advantage is bound to be short-lived as opposing strategies evolve to counteract the recognition,” they say.

    In other words, the other players ought to develop a kind of camouflage that prevents them being spotted and exploited.

    That may explain why nobody’s found examples of zero determinant strategies in nature: in most cases they won’t be stable and even if they are, the situation is likely to be short lived. As Adami and Hintze put it in the title of their paper: winning isn’t everything.

    That’s not to say there aren’t examples out there ready to be found. On the contrary. “This type of evolutionary arms race has been, and will be, observed throughout the biosphere,” say Adami and Hintze.

    Of course, this is just the beginning of an entirely new approach to game theory that has profound implications. Suggestions for where it might have the most impact in the comments section please.

    Ref: arxiv.org/abs/1208.2666: Winning isn’t everything: Evolutionary stability of Zero Determinant strategies

    TRSF: Read the Best New Science Fiction inspired by today’s emerging technologies.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s